elementary number theory - Prove true by using induction

Define a sequence ($t_i$) where $i ∈ N$ recursively by $t_1 = t_2 = t_3 = 1$ and, for all $n \ge 3$, $t_{n+1} = t_n + t_{n-1} + t_{n−2}.$ Prove that $t_n < 2^n$
for all $n ∈ N.$

I'm having trouble making advancements because I am stuck on the base cases and inductive step; do I assume that there will be $3$ base cases that are all less than $2^1$?

Answer

The required claim holds for $n\in\{1,\,2,\,3\}$. If it holds for $n=k$, for $n=k+1$ and for $n=k+2$, $t_{k+3}<2^k+2^{k+1}+2^{k+2}=7\times 2^k<2^{k+3}$.