f(n) = 2, for n=0.
f(n) = 2f(n-1)-n+1, for n>=1.
prove f(n)=(2^n)+n+1
for n=0 -> f(n)=2.
for n=k -> f(n)=(2^k)-k+1.
for n=k+1 -> f(n)=(2^k+1)+k+2.
Thats where i'm stuck. What am I supposed to do next?
Hi
Your notation does not seem to be really appropriate
I suggest
You need to prove that
therefore it is true for n=0
Suppose that it is true for n=k. This means that . You need to prove that
You know that and that
Substitute in the expression of to prove that
If you write a few terms, it appears
Prove using induction that this is so.
If this is true, then the following will also be true...
Therefore, if we can prove that really equals
then we only need to prove it works for the first term, since a mathematical chain reaction has been set up..
We attempt to prove it from f(n)=2f(n-1)-n+1.
f(n+1)=2f(n)-(n+1)+1=2f(n)-n.
The question is....
Is ?
Is ?
true
f(0)=1+0+1=2
f(1)=2+1+1=4=2(2)-1+1 true