Thread: mathematical induction proof

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

Originally Posted by blank

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?

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