# A proof by strong induction that $a_n\le3^n$ where $a_n=a_{n-1}+a_{n-2}+a_{n-3}$

I am not sure whether this is right. Can anyone verify, whether this proof is valid? Thanks!

Define a sequence $\{a_n\}_{n\ge0}$ as follows: $$a_0=1,\qquad,a_1=3,\qquad,a_2=9,\qquad,a_n=a_{n-1}+a_{n-2}+a_{n-3}\text{ for }n\ge3.$$ Prove that for any positive integer $n$, $a_n\le3^n$.

Proof. Let $P(n)$: $a_n\le 3^n$, $n$ is a non-negative integer.

(i) Base case:

• Consider when $n=0$. LHS$=a_0=1$, RHS=$3^0=1$ $\therefore$ LHS$\le$RHS, then $P(0)$ holds.
• Consider when $n=1$. LHS$=a_1=3$, RHS=$3^1=3$ $\therefore$ LHS$\le$RHS, then $P(1)$ holds.
• Consider when $n=1$. LHS$=a_2=9$, RHS=$3^2=9$ $\therefore$ LHS$\le$RHS, then $P(2)$ holds.

(ii) Inductive case:
Assume $P(i)$ is true for $0 \le i \le k$, $k\ge2$.

(iii) Inductive conclusion: Consider $n=k+1$. \begin{align*} \mathrm{LHS}=a_{k+1}&=a_k+a_{k-1}+a_{k-2} \qquad\text{(by definition, since k\ge 2)}\\ &\le 3^k+3^{k-1}+3^{k-2} \qquad\text{(by Induction Hypothesis)}\\ &=3^k(3^{-1}+3^{-2}+3^{-3})\\ &=3^k\left(\frac13+\frac19+\frac1{27}\right)\\ &=\frac{13}{27} 3^k\\ &\le 3^{k+1} = \mathrm{RHS} \end{align*} Therefore, by the Principle of Strong Induction, $P(n)$ is true for all non-negative positive integers $n$.

• I have added text version. It has some advantages - for example images are no help when searching and also you can easily edit the text, for an image you would have to do a new scan/photo. But I do appreciate that you have provided a picture in good quality and very readable (very nice handwriting.) I also appreciate that you have included your own solution. +1 from me. Sep 28, 2014 at 6:53