5
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ This one is good, clean, "forward." $\endgroup$ Jan 8 '16 at 19:53
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Still posting on SE, even after you've been recaptured... $\endgroup$
    – Shane
    Jan 8 '16 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.