Proof by Induction for a recursive sequence and a formula

Question

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?

Answer 1

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.

Answer 2

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.