Show that $4^nx_n < 7^n$ for all positive integers $n$

Question

I am working on an induction proof for my discrete mathematics class. Here is the problem:

Define $x_1 = 1$ and $x_2 = 2$ and $x_{n+2} = x_{n+1} + x_n$ for $n \geq 1$. Prove that $4^nx_n < 7^n$ for all positive integers $n$.

Here is what I have so far:

Base Case: n=1

$4^nx_n = 4^1*1 = 4 < 7 = 7^1$

Inductive Hypothesis

There is some $k$ such that $4^kx_k < 7^k$ for $k \geq 1$. We want to show $4^{k+1}x_{k+1} < 7^{k+1}$.

Then, $4^{k+1}x_{k+1} = 4^{k+1}(x_{k}+x_{k-1}) = 4(4^{k}x_{k}+4^{k}x_{k-1}) < 4(7^k+4^{k}x_{k-1})$.

I have no idea where to go from here. Can anyone give a hint or suggest a direction to head from here? All help is appreciated. Thanks!

Answer 1

Here's a continuation: $$4(7^k+4^{k}x_{k-1})< 4\cdot7^k+4^2\cdot 7^{k-1}< 4\cdot7^k+21\cdot 7^{k-1}=4\cdot7^k+3\cdot 7^k=7^{k+1}.$$

Answer 2

\begin{eqnarray*} 4^{k+1}x_{k+1} = 4^{k+1} (x_k+x_{k-1}) < 4 \times 7^{k} +16 \times 7^{k-1} = (28+16) 7^{k-1}< 7^{k+1}. \end{eqnarray*}

Answer 3

$$x_{k+2}<(7/4)^{k+1}+(7/4)^k$$ will definitely be $$<(7/4)^{k+2}$$

If $$(7/4)+1<(7/4)^2$$

$$\iff 7\cdot4+4^2<7^2$$ which is true