Given a series $b_0,b_1,...$, where $b_0=1,b_1 = 2,b_2 = 3$ and $b_n=b_{n-3}+b_{n-2}+b_{n-1}$, show $b_n \leq 3^n$ for $n>2$.

Question

I have a series $b_0, b_1...$, where $b_0 = 1$, $b_1 = 2$, $b_2 = 3$ and $b_n = b_{n-3} + b_{n-2}+b_{n-1}$. I have to show, that when $n > 2$ and $n \in \Bbb Z$, then $b_n \leq 3^n$.

I'm using mathematical induction.

Base case $n = 3$

$b_3= b_0 + b_1 + b_2 = 1 + 2 +3 = 6\\ b_3 \leq 3^3 \rightarrow 6 \leq 27$

So I presume that $b_k \leq 3^k$ is true and I should show that $b_{k+1} \leq 3^{k+1}$ is also true, but this is where I get stuck and don't know how to do it.

How should I show this?

Answer 1

Take $b_{k+1}$ with the assumption that the claim holds for all $b_j$ when $j\le k$. Now, by definition, $b_{k+1}=b_k+b_{k-1}+b_{k-2}$. The induction hypothesis tells us that $b_n\le 3^n$ for $n\le k$, so $b_{k+1} \le 3^k+3^{k-1}+3^{k-2}<3^k+3^k+3^k=3\cdot3^k=3^{k+1}$.

Answer 2

If you stick with weak induction, your inductive hypothesis should be$$b_{3n}\le3^{3n}\land b_{3n+1}\le3^{3n+1}\land b_{3n+2}\le3^{3n+2},$$which is true if $n=0$. So you just need to show$$b_{3k}\le3^{3k}\land b_{3k+1}\le3^{3k+1}\land b_{3k+2}\le3^{3k+2}\implies b_{3k+3}\le3^{3k+3}\land b_{3k+4}\le3^{3k+4}\land b_{3k+5}\le3^{3k+5}.$$

Answer 3

You have to use a strong induction which assumes the assertion for all $k=3,\ldots,n$. Then estimate $b_{n+1}$.

This variant is necessary, because you have a recursion over three predecessors and you must know something about all of them.

Answer 4

You have to assume it is true for the 3 previous cases. If $b_k \le 3^k$ for $k = n-1, n-2, n-3$ then

$\begin{array}\\ b_n &=b_{n-1}+b_{n-2}+b_{n-3}\\ &\le 3^{n-1}+3^{n-2}+3^{n-3}\\ &=3^n(3^{-1}+3^{-2}+3^{-3})\\ &=3^n\dfrac{9+3+1}{27}\\ &=3^n\dfrac{13}{27}\\ &\lt 3^n\\ \end{array} $