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!

Letfbe defined recursively by:

Initial condition:f(0)=1

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

For the functionfabove, prove that for alln,f(n)=2^{n+1}-1.

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

SOLUTION:

Proof by induction:

1) Basis step:

Prove thatf(0)=2^{n+1}-1

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

because 1=1

2) Inductive step:

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

We need to use this hypothesis to prove thatf(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 (2f(n)+1) WAS FOUND)

thenf(n+1)=2f(n)+1 (via Recursive definition off)

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

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

=2^{n+1}-1

# END OF PROOF