Proving recursive function via mathematical induction (EASY, but need a boost)

This was a sample problem discussed in class that I already have the solution to, but I am having trouble understanding the highlighted section. Please be very detailed with your explanation. Thank you in advance!

Let *f* be defined recursively by:

Initial condition: *f(0)*=1

Recursive step: *f(n)*=2*f*(n-1)+1

For the function *f *above, prove that for all *n*, *f(n)*=2^{n+1}-1.

----------------------------------------------------------------

SOLUTION:

Proof by induction:

1) Basis step:

Prove that *f(0)*=2^{n+1}-1

*f(0)*=2^{0+1}-1 is true

because 1=1

2) Inductive step:

Inductive hypothesis: Assume that for some *n>=*0, *f(n)*=2^{n+1}-1.

We need to use this hypothesis to prove that *f(n+1)*=2^{n+2}-1.

Proof: Assume that the inductive hypothesis is true,

(I DO NOT UNDERSTAND HOW THE RIGHT SIDE OF THE BELOW EQUATION (2*f(n)*+1) WAS FOUND)

then *f(n+1)*=2*f(n)*+1 (via Recursive definition of *f*)

=2(2^{n+1}-1)+1 (via Inductive hypothesis)

=2^{n+2}-2+1

=2^{n+1}-1

# END OF PROOF

Re: Proving recursive function via mathematical induction (EASY, but need a boost)

After having shown the base case is true, I would state the induction hypothesis $\displaystyle P_n$:

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

Using the recursive definition, we may state:

$\displaystyle f(n+1)=2f(n)+1$

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

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

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

We have derived $\displaystyle P_{n+1}$ from $\displaystyle P_n$, thereby completing the proof by induction.

Re: Proving recursive function via mathematical induction (EASY, but need a boost)

You compose the functions on each side of the equation of the recursive step with g(k)=k+1 and obtain the second equation in red with k instead of n.

Re: Proving recursive function via mathematical induction (EASY, but need a boost)

Sorry for the late reply. Thank you!