2

Prove: $a_n < 2^n$ for all $n\ge 1$

$a_n = a_{n-1} + a_{n-2} + a_{n-3},\quad n\ge4$

$a_1=1 , a_2=2 , a_3=3$

Kayleigh
  • 21

1 Answers1

1

I will assume that you can provide a proper induction basis, so I'll leave that to you.

Using strong induction, our induction hypothesis becomes:

  • Suppose that $a_k<2^k$, for all $k\leq n$.

In the induction step we look at $a_{n+1}$. We write it out using our recursive formula and see that: $$a_{n+1}=a_n+a_{n-1}+a_{n-2}.$$ Now by the induction hypothesis we know that:

  • $a_n<2^n$,
  • $a_{n-1}<2^{n-1}$, and
  • $a_{n-2}<2^{n-2}$.

So $a_{n+1}<2^n+2^{n-1}+2^{n-2}$. Some basic airithmetic will lead to the final statement now.

gebruiker
  • 6,154
  • I know this was a long time ago, but I don't think $2^{n+1} = 2^n + 2^{n-1} + 2^{n-2}$ if you could finalize the proof I'll greatly appreciate it – ph-quiett Aug 15 '19 at 06:04
  • @ph-quiett I never claimed that $2^{n+1}=2^n+2^{n-1}+2^{n-2}$. Please read carefully what needs to be proven. – gebruiker Aug 22 '19 at 11:39