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

• Nov 11th 2012, 05:30 PM
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)=2f(n-1)+1

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

----------------------------------------------------------------
SOLUTION:

Proof by induction:
1) Basis step:
Prove that f(0)=2n+1-1
f(0)=20+1-1 is true
because 1=1
2) Inductive step:
Inductive hypothesis: Assume that for some n>=0, f(n)=2n+1-1.
We need to use this hypothesis to prove that f(n+1)=2n+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)
then f(n+1)=2f(n)+1 (via Recursive definition of f)
=2(2n+1-1)+1 (via Inductive hypothesis)
=2n+2-2+1
=2n+1-1

# END OF PROOF
• Nov 11th 2012, 07:49 PM
MarkFL
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.
• Nov 12th 2012, 02:42 PM
ModusPonens
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.
• Jan 10th 2013, 04:42 PM