Question:Prove by mathematical induction that if U_{n+2}= 3U_{n+1} - 2U_{n} for all positive integers n, and U_{1 }= 1 , U_{2} = 3 , then U_{n }= 2^{n} - 1.
How to deal with relations that includes 3 terms in mathematical induction?
This is how far I got:
U_{n }= 2^{n} - 1
let n=1,
LHS: U_{1}=1
RHS: 2-1=1
RHS=LHS
Assume when n=k, the equation is true: U_{k} = 2^{k }-1
Proof that U_{k+1}=2^{k+1}-1
U_{K+1}= 3U_{k} -2U_{k-1 } =3( 2^{k} - 1) -2U_{k-1} Then I couldn't proceed with the k-1 there. Can anyone help?
How can u use substitution U_{k-1 }= 2^{k-1 }- 1 ?
The thing we are going to proof by induction is U_{n}=2^{n}-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 , U_{k}=2^{k} -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 U_{k+1, }you substitute U_{k-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 U_{k}=2^{k}-1 and U_{k}_{-1}=2^{k-1} -1 at the same time, isn't that already assuming the equation correct?
Surely you know about strong induction?
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.