# Is my inductive proof correct?

Trying this again.

Given $f(n) = 2f(n-1) + 1$ with $f(0) = 0$, I guess that $f(n) = 2^n-1$.

Base case: $f(0) = 2^0 - 1 = 1 - 1 = 0$, true.

Inductive step: Suppose $f(n) = 2^n-1$ for some $n \geq 0$. I will show that $f(n+1) = 2^{n+1}-1$.

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

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

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

This completes the proof.

My questions:

1. Is this proof correct? Awkward? Backwards?

2. It would help me to get the terminology right. Which piece is the inductive hypothesis? Or the "ansatz"?

• This one is good, clean, "forward." Jan 8 '16 at 19:53

As far as terminology, the inductive hypothesis is the thing you assume is true at some $n$, and is used to prove the statement for $n + 1$. So your inductive hypothesis is that $f(n) = 2^n - 1$.
The ansatz is the educated guess that the solution is $2^n - 1$, likely based on some experimentation. The ansatz then became your induction hypothesis (as it is wont to do).
Looks good to me. The inductive hypothesis is the step where you assume $f(n)=2^n-1$. We assume the inductive hypothesis because we have shown the existence of such an $n$ in our base case.