Printable View
Question:Prove by mathematical induction that if Un+2= 3Un+1 - 2Un for all positive integers n, and U1 = 1 , U2 = 3 , then Un = 2n - 1.
How to deal with relations that includes 3 terms in mathematical induction?
This is how far I got:
Un = 2n - 1
let n=1,
LHS: U1=1
RHS: 2-1=1
RHS=LHS
Assume when n=k, the equation is true: Uk = 2k -1
Proof that Uk+1=2k+1-1
UK+1= 3Uk -2Uk-1
=3( 2k - 1) -2Uk-1 Then I couldn't proceed with the k-1 there. Can anyone help?
Suppose that this true for eachQuote:
Originally Posted by tsyet12
.
Look at
.
How can u use substitution Uk-1 = 2k-1 - 1 ?
The thing we are going to proof by induction is Un=2n-1 . A number is substitute to check if any number fulfills the equation. And if yes, we assume that there are a set of numbers that fulfills the equation and let it be k. Hence , Uk=2k -1 is deduced and usable in further calculations. Then we proceed to proving that "k+1" or "k-1" also fulfills the equation, and if yes, the equation is correct, proven by induction.
But, in the process of proving Uk+1, you substitute Uk-1 (which wasn't deduced or proven). Is that valid? And, isn't that assuming that the equation is already correct?
If you assume that Uk=2k-1 and Uk-1=2k-1 -1 at the same time, isn't that already assuming the equation correct?
Surely you know about strong induction?Quote:
Originally Posted by tsyet12
That was the point of saying it holds for
Given some property of numbers P, regular induction proves P(1), on the basis of P(1) it proves P(2), on the basis of P(2) it proves P(3), and in general it uses P(k) to prove P(k + 1). Eventually you can prove P(n) for every n, so you may consider "for all n, P(n)" proved.
Strong induction also proves P(1), and on the basis of P(1) it proves P(2). Then it uses both P(1) and P(2) to prove P(3), it uses P(1), P(2) and P(3) to prove P(4), and in general it uses all of P(1), ..., P(k) to prove P(k + 1). In particular, when proving P(k + 1) you may use not only P(k), but P(k - 1) (as long as k > 1). Eventually you again can prove P(n) for every n. Note that strong induction makes the induction step easier because you have more assumptions to prove P(k + 1).
It is important that if you started with P(1), then in proving P(k + 1) you may use P(k - 1) only when k > 1 (otherwise, P(k - 1) becomes P(0), which you have not proved). How then do we prove P(k + 1) for k = 1, i.e., P(2)? It has to be proved separately, not as a part of the induction step. Thus, strong induction may have more than one base case. But even base cases can be considered as induction steps if the rule is to prove P(k) from all P(j) where 1 ≤ j < k. In particular, P(1) is proved without assumptions since there is no j such that 1 ≤ j < 1.
See also Wikipedia.
Ok, thanks, you guys.I understand now! Appreciate it very much ^^