Strong Induction

Error

There was an error loading the page.

Contributors

Feedback

From users who are members of Discrete Mathematics :

Daniel Mansfield

said

Needs to be tested

6 years, 2 months ago

History

○

Daniel Mansfield 6 years, 2 months ago

Published this.

○

Daniel Mansfield 6 years, 2 months ago

Gave some feedback: Needs to be tested

○

Daniel Mansfield 6 years, 2 months ago

Created this.

There is only one version of this question that you have access to.

There are 2 other versions that do you not have access to.

Question statement

Strong induction is the name given to induction that makes more assumptions in the inductive step. Consider the sequence of numbers $u_0, u_1, u_2, \cdots$ defined by

$\begin{align*} u_0 & = \var{A+B} \\ u_1 & = \var{A*root1 + B*root2} \\ u_n & = \var{root1 + root2} u_{n-1} - \var{root1*root2}u_{n-2} \text{ for } n \geq 2. \end{align*}$

Prove by strong induction that $f(n) = \simplify{{A}*{root1}^n + {B}*{root2}^n} = u_n$ .

Give any introductory information the student needs.

			Name	Type	Generated Value

A	integer	-2
B	integer	6
root1	integer	5
root2	integer	4
k	integer	16

Automatically regenerate variables?

Name

Data type

Value

xxxxxxxxxx
 
random(-5..6 except [-1,0,1])

JME function reference

Description

Describe what this variable represents, and list any assumptions made about its value.

Can an exam override the value of this variable?

Generated value: `integer`

-2

→ Used by:

Statement
Advice
"Part a)" - prompt
"Part a)" → "Gap 0." - Minimum accepted value
"Part a)" → "Gap 0." - Maximum accepted value
"Part a)" → "Gap 1." - Minimum accepted value
"Part a)" → "Gap 1." - Maximum accepted value
"Part b)" → "Gap 0." - Correct answer
"Part b)" → "Gap 1." - Correct answer

Parts

Part a) Gap-fill
1. Gap Gap 0. Number entry
  Add
2. Gap Gap 1. Number entry
  Add
Part b) Gap-fill
1. Gap Gap 0. Mathematical expression
  Add
2. Gap Gap 1. Mathematical expression
  Add
Information only

Gap-fill

Ask the student a question, and give any hints about how they should answer this part.

Since the general term is defined by the two terms preceding it, the first two terms $u_0$ and $u_1$ are both base cases.

Prove the base cases:

$f(0) = \var{A}\times\var{root1}^0 + \var{B}\times\var{root2}^0 =$ Gap 0.

$f(1) = \var{A}\times\var{root1}^1 + \var{B}\times\var{root2}^1 =$ Gap 1..

Advice

Proof by induction always has a base case and inductive step. In part a we are asked to show

$f(0) = \var{A}\times\var{root1}^0 + \var{B}\times\var{root2}^0 = \var{A + B} = u_0$ ,

$f(1) = \var{A}\times\var{root1}^1 + \var{B}\times\var{root2}^1 = \var{root1*A + root2*B} = u_1.$

In part b we fix $n$ and assume that $f(k) = u_k$ for $2 \leq k \leq n$ . That is, assume

$u_k = \var{A}\times\var{root1}^k + \var{B}\times\var{root2}^k.$

In strong induction you usually assume all of the previous cases hold ( $f(k)=u_k$ is true for all $2\leq k\leq n$ ). This works generally, but here we end up using only the assumptions that $u_n = f(n)$ and $u_{n-1}=f(n-1)$ .

$u_{n+1}$	$= \var{root1 + root2} u_{n} - \var{root1*root2}u_{n-1}$
	$= \var{root1 + root2} (\var{A}\times\var{root1}^n + \var{B}\times\var{root2}^n) - \var{root1*root2}(\var{A}\times\var{root1}^{n-1} + \var{B}\times\var{root2}^{n-1})$
	$= (\var{root1 + root2}\times\var{A}\times\var{root1} - \var{root1root2}\times\var{A})\var{root1}^{n-1} + (\var{root1 + root2}\times\var{B}\times\var{root2} - \var{root1root2}\times\var{B})\var{root2}^{n-1}$
	$= \simplify{({root1}+{root2}){A}{root1} - {root1}{root2}{A}}\times\var{root1}^{n-1} + \simplify{({root1}+{root2}){B}{root2} - {root1}{root2}{B}}\times\var{root2}^{n-1}$
	$= \simplify{(({root1}+{root2}){A}{root1} - {root1}{root2}{A})/{root1}^2}\times\var{root1}^{n+1} + \simplify{(({root1}+{root2}){B}{root2} - {root1}{root2}{B})/{root2}^2}\times\var{root2}^{n+1}$

Hence $f(n) = u_n$ for all $n = 0,1,\cdots$ by induction.

Give a worked solution to the whole question.

Use this tab to check that this question works as expected.

There was an error which means the tests can't run:

Part	Test	Passed?
Gap-fill
Gap-fill		Hasn't run yet
Number entry
Number entry		Hasn't run yet
Number entry
Number entry		Hasn't run yet
Gap-fill
Gap-fill		Hasn't run yet
Mathematical expression
Mathematical expression		Hasn't run yet
Mathematical expression
Mathematical expression		Hasn't run yet
Information only

This question is used in the following exam:

Week 5: quantifiers and induction by Daniel Mansfield in Discrete Mathematics.

Loading...

Error

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Daniel Mansfield 6 years, 2 months ago

Daniel Mansfield 6 years, 2 months ago

Daniel Mansfield 6 years, 2 months ago

Error in variable testing condition

Error

Warning

Generated value: `integer`

Parts

Gap-fill

Loading...

Error

Strong Induction

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Daniel Mansfield 6 years, 2 months ago

Daniel Mansfield 6 years, 2 months ago

Daniel Mansfield 6 years, 2 months ago

Error in variable testing condition

Error

Warning

Generated value: integer

Parts

Gap-fill

Generated value: `integer`