7
$\begingroup$

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?

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ +1, great answer. Just as an aside to this fine answer, I'm not sure what your background is @Chris, but what you've observed here falls under the more general problem of solving linear recurrence relations. Here is a nice resource which describes how you can generally solve recurrence relations of this kind: eecs.yorku.ca/course_archive/2008-09/S/1019/Website_files/…. You can find many more like this by simply searching "solving linear recurrence relations." $\endgroup$ – Alex Wertheim Oct 23 '13 at 1:37
  • $\begingroup$ You had an oops with your arithmetic when you distributed the 2. But anyway, thank you very much, I can't believe it was so simple or that you could represent things that way. The challenge comes when trying to figure out what side to prove and which side I can manipulate to look like the other side. $\endgroup$ – Chris Oct 23 '13 at 1:48
0
$\begingroup$

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.

$\endgroup$

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.