So I have a homework assignment that has brought me great strain over the past 2 days. No video or online example have been able to help me with this issue either and I don't know where to turn.
I’m given
$a_0=0$
$a_n=2a_{n-1}+1$
After writing the first 6 terms of the series: 0, 1, 3, 7, 15, 31, 63 I come up with an alternate formula of
$a_n=2^n-1$
I then have to prove these formulas are the same using Induction in 3 parts:
- Proving the base case
- Stating my Inductive Hypothesis
- Showing the Inductive Step
I have done Inductive proofs before but I don’t know how to show cases or do manipulations on a recursive formula. I don’t know how to represent when n = k then n = k + 1 or showing the approach by using n = k – 1 then n = k.
Any ideas?
2 Answers
For the setup, we need to assume that $a_n = 2^n - 1$ for some $n$, and then show that the formula holds for $n + 1$ instead. That is, we need to show that $$a_{n + 1} = 2^{n + 1} - 1$$
Let's just compute directly:
\begin{align*} a_{n + 1} &= 2a_n + 1 \hspace{1.55in}\text{// recursion relation} \\ &= 2 \cdot (2^n - 1) + 1 \hspace{1in} \text{// induction hypothesis} \\ &= 2^{n + 1} - 2 + 1 \hspace{1.15in} \text{// arithmetic} \\ &= 2^{n + 1} - 1 \end{align*}
which is exactly what we wanted to be true.
Proving the base case should be rather simple.
For the inductive hypothesis, we'll assume that for $k\geq1$, $$a_{k-1}=2^{k-1}-1$$ From this you need to prove that $a_k=2^k-1$. It shouldn't be too tough to get it from here just by following the recurrence relation.
