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

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