# Proof by induction that x_n < 2^n

Define $x_1=x_2=x_3=1$ and $$x_{n+1}=x_n+x_{n-1}+x_{n-2}$$ for $n≥3$. Prove that $$x_n<2^n \qquad ∀n\in\mathbb N$$

I have shown the base case and supposed the result in the inductive case. Then, using the inductive hypothesis I said that $x_k<2^k, x_{k-1}<2^{k-1}, x_{k-2}<2^{k-2}$ and hence $$x_{k+1}=x_k+x_{k-1}+x_{k-2}<2^k+(2^k/2)+(2^k/4)$$ This gives $x_{k+1}<\frac{7}{4}\cdot2^k$, whereas to prove by POI, I obviously wanted $x_{k+1}<2\cdot2^k$.

Have I made an arithmetic/algebraic error or am I going about the proof the wrong way? Thanks.

• Tip: surround all your math with $$. That will make it look right. – Johanna Nov 10 '14 at 15:01 ## 1 Answer By the induction assumption$$x_{n+1}<2^n+2^{n-1}+2^{n-2}=2^n\left(1+\frac{1}{2}+\frac{1}{4}\right)<2^n\cdot2=2^{n+1}

• Ahh yes of course! Thanks – MathsUndergrad Nov 10 '14 at 14:58
• You are welcome, you actually had it already. – Jimmy R. Nov 10 '14 at 15:00