If $F_n$ is the Fibonacci sequence, show that $F_n < \left(\frac 74\right)^n$ for $n\geq 1.$ Recall that the Fibonacci sequence is defined by $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n−1} + F_{n−2}$ for $n ≥ 2$. Prove that:
$$\forall \,\, n ≥ 1 ,\,\, F_n < \left(\frac 74\right)^n$$ 
In this question I understand how to do the basis step.
In the induction step I know that you have to assume that n=k but I am having trouble figuring out on how to do that. Could someone please explain how to do this question.
 A: Use strong induction 
It's sufficient to show
$$(7/4)^m+(7/4)^{m+1}<(7/4)^{m+2}$$
$$\iff1+(7/4)<(7/4)^2$$
$$\iff4^2+7\cdot4<7^2$$
A: The proof will be by strong induction on n.  There are two steps you need to prove here since it is an induction argument.  You will have two base cases since it is strong induction.
First show the base cases by showing this inequailty is true for n=1 and n=2. 
Then for the inductive step, assume the inequality is true for $F_{n-1}$ and $F_{n-2}$ (known as the inductive hypothesis) then show it is true for $F_{n}$.
$F_{n}$
=$F_{n-1}$+$F_{n-2}$ (by definition of Fibonacci numbers.)
<$(7/4)^{n-1}$+$(7/4)^{n-2}$ (by the inductive hypotheses)
=$(7/4)^{n-2}((7/4)+1)$ (arithmetic, factor $(7/4)^{n-2}$ from both terms)
=$(7/4)^{n-2} ((28/16)+16/16)$ (arithmetic, why?  I wanted to compare to $7/4^2$=49/16 so I wanted a denominator of 16)
=$(7/4)^{n-2}(42/16)$
<$(7/4)^{n}$. (since 42/16<49/16)
So by the principle of mathematical induction, this inequality is true.
Hope this makes sense now.
A: There's something called Strong Induction. 
The base cases are for $F_k$ such that $k=0,1$. 
For the inductive step, assume that $\exists~ n$ such that $F_{n-1}<\frac{7^n}{4^n}$ and $F_{n-1}<\frac{7^{n-1}}{4^{n-1}}$
It's now quite easy to show that 
$$\begin{align*}
F_{n+1}&=F_n+F_{n-1}\\
&<\frac{7^n}{4^n} + \frac{7^{n-1}}{4^{n-1}}\\
&<\frac{7^{n+1}}{4^{n-1}}
\end{align*}$$
for all $n\geq 1$
A: The proposition that you're trying to prove is that $F_n<(\frac{7}{4})^n$
For $n = 0$, this is trivial; $0 < (\frac{7}{4})^0$
For $n = 1$, we have $1 < (\frac{7}{4})^1$
For your induction step, you assume that for all k < n, $F_k<(\frac{7}{4})^k$
So $F_{n-2}<(\frac{7}{4})^{n-2}$ and $F_{n-1}<(\frac{7}{4})^{n-1}$
$F_{n} = $
$F_{n-2}+ F_{n-1}$ <
$(\frac{7}{4})^{n-2} + (\frac{7}{4})^{n-1}$ =
$(\frac{7}{4})^{n-2} + \frac 7 4 (\frac{7}{4})^{n-2} = $
$\frac 4 4(\frac{7}{4})^{n-2} + \frac 7 4 (\frac{7}{4})^{n-2} $=
$\frac {11} 4 (\frac{7}{4})^{n-2}$=
$\frac {44} {16} (\frac{7}{4})^{n-2}$<
$\frac {49} {16} (\frac{7}{4})^{n-2}$=
$ (\frac{7}{4})^{n}$
A: Method 1: Base case:
$$F_1=1<\frac74; F_2=1<\frac74.$$
Inductive hypothesis:
$$F_{n-1}<\left(\frac74\right)^{n-1}; F_n<\left(\frac74\right)^n.$$
Inductive step:
$$F_{n+1}=F_{n-1}+F_n<\left(\frac74\right)^{n-1}+\left(\frac74\right)^n=\left(\frac74\right)^n\left(\frac47+1\right)<\left(\frac74\right)^{n+1}.$$
Method 2: Prove $F_n=\frac{\phi^n-\psi^n}{\sqrt{5}}<\left(\frac74\right)^n$.
Base case: $F_1=1<\frac74$.
Inductive hypothesis: the above estimate.
Inductive step:
$$F_{n+1}=\frac{\phi^n\cdot \frac{1+\sqrt{5}}{2}-\psi^n\cdot \frac{1-\sqrt{5}}{2}}{\sqrt{5}}=$$
$$\left(\frac12+\frac{\sqrt{5}}{2}\right)\cdot \frac{\phi^n-\psi^n}{\sqrt{5}}+2\left(\frac{1-\sqrt{5}}{2}\right)^n<$$
$$\left(\frac12+\frac{\sqrt{5}}{2}+2\right)\cdot \left(\frac74\right)^n<\left(\frac74\right)^{n+1}.$$
