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

enter image description here enter image description here

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$.

  • 2
    $\begingroup$ 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. $\endgroup$ Sep 28, 2014 at 6:53

1 Answer 1


Nice write-up; looks great! Perhaps a slightly slicker way of doing the induction step (and probably what the problem intended you to do) is to observe that: \begin{align*} 3^k + 3^{k-1} + 3^{k-2} &< 3^k + (3)3^{k-1} + (3^2)3^{k-2} \\ &= 3^k + 3^k + 3^k \\ &= 3(3^k) \\ &= 3^{k+1} \end{align*}


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .