2

We have a sequence of $a_n = a_{n-3}+a_{n-2}+a_{n-1} \text{ where } a_{1} = a_{2} =a_{3} = 1$ for all $n\ge 4$. Prove $a_n < 2^n$ is true for all positive integers $n$.

What I have done so far is starting with the inductive hypothesis because this is strong induction. So far my inductive hypothesis is: Consider $P(k)$ is true for all $a_k < 2^k$ where $k$ is a positive integer. Now show that $a_{k+1} < 2^{k+1}.$

This is what I have done so far: $$a_{k+1} < 2^{k+1} \implies a_{k+1} < 2^k \cdot 2 \implies 2 \cdot \underbrace{a_k < 2^k}_{IH} \cdot 2 \\ \text{So we see: } a_k < 2^k < 2^{k+1}$$

Now I am stuck because I don't know how to show $a_{k+1} < a_k$.

If my way of solving this looks wrong please let me know.

DippyDog
  • 313
  • 1
    $a_{k+1} < a_k$ is not true, since the sequence actually increases. In the induction step you should use the recursion equation: $a_{k+1} = a_k+a_{k-1}+a_{k-2}$. What bounds do you have for $a_k$, $a_{k-1}$, $a_{k-2}$? – hgmath Feb 26 '21 at 16:33
  • Ahhh, that was my mistake. I meant to write it the other way around... – DippyDog Feb 26 '21 at 16:36
  • 1
    You meant so say that "Consider $P(n)$ is true for all $n\le k$..."? – Shubham Johri Feb 26 '21 at 16:37

2 Answers2

5

We show that $P_n : a_n < 2^n$ is true.

  • for $n=1$, it's ok.
  • for $n >1$, suppose $P_1,...,P_{n-1}$. We see that $$ a_n = a_{n-3}+a_{n-2}+a_{n-1} \le 2^{n-3}+2^{n-2} + 2^{n-1}=2^n(\frac{1}{2^3}+\frac{1}{2^2}+\frac{1}{2})<2^n $$ So $P_n$ is true.

Here are some comments about your proof:

The way you stated your inductive hypothesis is odd (to me). Also here we know that $a_n$ is defined by induction so using strong induction is a good idea. It seems to me that you got kind of lost when applying the hypothesis. You started your proof from the result not the hypothesis...

Michelle
  • 1,784
  • 7
  • 20
3

Our statement is true for $n=1,2,3$. Suppose $P(k):a_k<2^k$ is true for all $k< n\ge4$. Then$$a_n=a_{n-1}+a_{n-2}+a_{n-3}<2^{n-1}+2^{n-2}+2^{n-3}=2^{n-1}(1+1/2+1/4)<2^{n-1}\cdot2$$

Shubham Johri
  • 17,659