1. ## 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?

2. Hi

Your notation does not seem to be really appropriate
I suggest
$u_0=2$
$u_{n+1}=2 \:u_n - n$

You need to prove that $u_n = 2^n+n+1$

$2^0+0+1 = 2 = u_0$ therefore it is true for n=0

Suppose that it is true for n=k. This means that $u_k = 2^k+k+1$. You need to prove that $u_{k+1} = 2^{k+1}+k+2$

You know that $u_{k+1} = 2 \:u_k - k$ and that $u_k = 2^k+k+1$
Substitute $u_k = 2^k+k+1$ in the expression of $u_{k+1}$ to prove that $u_{k+1} = 2^{k+1}+k+2$

3. 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?
$f(0)=2$
$f(n)=2f(n-1)-n+1,\ for\ n\ge1$

If you write a few terms, it appears $f(n)=2^n+n+1$

Prove using induction that this is so.

$f(n)=2^n+n+1$

If this is true, then the following will also be true...

$f(n+1)=2^{n+1}+(n+1)+1=(2)2^n+(n+1)+1=2^n+2^n+(n+1 )+1$

$=[2^n+n+1]+2^n+1=f(n)+2^n+1$

Therefore, if we can prove that $f(n+1)$ really equals $f(n)+2^n+1$

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 $2f(n)-n=f(n)+2^n+1$ ?

Is $2f(n)-f(n)=2^n+n+1$ ?

$f(n)=2^n+n+1$

true

f(0)=1+0+1=2
f(1)=2+1+1=4=2(2)-1+1 true