8
$\begingroup$

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

$\endgroup$
  • 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$ – Martin Sleziak Sep 28 '14 at 6:53
2
$\begingroup$

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*}

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