Prove using mathematical induction

Question

Sequence $b_1, b_2,...$ where $b_1=b_2=1$ and for every natural number $k$ bigger than $2$, $b_k = b_{k-1}+b_{k-2}$.
Prove using mathematical induction that, for every $k \in \mathbb N, b_k \le (\frac{7}{4})^{k-1} $

I started with if $k=3$, $k_3=1+1=2$ and $(\frac{7}{4})^{k-1} =(\frac{7}{4})^2=3 \frac{1}{16}$, $2<3 \frac{1}{16}$. This is the induction base?

Step: Let us assume that S(m) is true, $b_m \le (\frac{7}{4})^{m-1}$ for every m $\in$ {3, ..., k}.
We have to show that $b_{k+1} \le (\frac{7}{4})^k$. Using assumption and $b_{k+1} = b_{k}+b_{k-1}$ I got $$b_k+b_{k-1}\le (\frac{7}{4})^{k+1}+(\frac{7}{4})^{k}$$ I don't know what to do next.

Answer 1

I don't know what to do next.

$ \left(\dfrac{7}{4}\right)^{k+1}+\left(\dfrac{7}{4}\right)^{k}=\left(\dfrac74\right)^k\left(\dfrac74+1\right)=\left(\dfrac74\right)^k\left(\dfrac{11}4\right)=\left(\dfrac74\right)^k\left(\dfrac{44}{16}\right)$

$<\left(\dfrac74\right)^k\left(\dfrac{49}{16}\right)=\left(\dfrac74\right)^k\left(\dfrac{7}{4}\right)^2=\left(\dfrac74\right)^{k+2}$

Answer 2

I started with if $k=3$, $k_3=1+1=2$ and $(\frac{7}{4})^{k-1} =(\frac{7}{4})^2=3 \frac{1}{16}$, $2<3 \frac{1}{16}$. This is the induction base?

No. Since the series starts with $b_1$, you should start with $1$, not $3$. That is, for your base, show that $b_k \leq (\frac{7}{4})^{k-1}$ for $k=1$ ... and since the recursive definition of the series refers to two previous terms, you should also include the case $k=2$ in your base.

For your step you then show that for some arbitrary $k \geq 3$: if the claim is true for $k-2$ and for $k-1$, then it is true for $k$