# Let $a_n$ be defined inductively by $a_1 = 1, a_2 = 2, a_3 = 3$, and $a_n = a_{n−1} + a_{n−2} + a_{n−3}$ for all $n \ge 4$. Show that $a_n < 2^n$.

Suppose that the numbers $a_n$ are defined inductively by $a_1 = 1, a_2 = 2, a_3 = 3$, and $a_n = a_{n−1} + a_{n−2} + a_{n−3}$ for all $n \geq 4$. Use the Second Principle of Finite Induction to show that $a_n < 2^n$ for every positive integer $n$.

Source: David Burton's Elementary Number Theory, p. 8, question 13 of "Problems 1.1".

• Can you show your attempt? – wythagoras May 3 '15 at 15:46
• Hint: Try the Second Principle of Finite Induction.... – N. S. May 3 '15 at 15:50
• That is given in the problem statement. – wythagoras May 3 '15 at 15:50
• ${111}_2 < {1000}_2$. – user21467 May 3 '15 at 15:54

## 2 Answers

For $a_1, a_2, a_3$ it is trivial.

Now assume that $a_{k} < 2^k$, $a_{k+1} < 2^{k+1}$, $a_{k+2} < 2^{k+2}$.

Therefore $$a_{k+3} = a_k+a_{k+1}+a_{k+2} < 2^k + 2^{k+1} + 2^{k+2} = 7\cdot2^k < 2^{k+3}$$

That completes the induction and thereby the proof, QED.

You don't seem to get the idea of induction. The normal induction is:

• Show that it holds for $n=1$
• Show that it if it holds for $n=k$ (called the induction hypothesis), then it holds for $n=k+1$.

In this case we use induction with three hypotheses:

• Show that it holds for $n=1$, $n=2$ and $n=3$.
• Show that it if it holds for $n=k$, $n=k+1$ and $n=k+2$ (called the induction hypothesis), then it holds for $n=k+3$.

Hint: Consider instead the sequence defined by the same initial values and $\displaystyle a_n = \sum_{k=0}^{n-1} a_k$ for $n \geq 4$.