Is my inductive proof correct?

Question

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"?

Answer 1

The proof is fine.

---

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).

Answer 2

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.