Prove $F_{n+1} ≤ (\frac74)^n $, where $F_n$ are Fibonacci numbers

Question

Let $F_n$ be the $n$-th Fibonacci number, defined recursively by $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n−1} + F_{n−2}$ for $n ≥ 2$.

Prove the following by induction (or strong induction):

$(a)$ For all $n ≥ 0$, $F_{n+1} ≤ \left(\dfrac74\right)^n$.

$(b)$ Let $G_n$ be the number of tilings of a $2 × n$ grid using domino pieces (i.e. $2 × 1$ or $1 × 2$ pieces). Then prove $G_n = F_{n+1}$.

For question $(a)$, I've done the proof but the result I kept getting was $$\left(\frac74\right)^{k+1}\left(\frac{11}7\right)≤\left(\frac74\right)^{k+1}$$ which is wrong.

Answer 1

The base is obvious.

Let $F_{n}\leq\left(\frac{7}{4}\right)^{n-1}$ and $F_{n+1}\leq\left(\frac{7}{4}\right)^{n}$.

Thus, $$F_{n+2}=F_{n+1}+F_n\leq\left(\frac{7}{4}\right)^{n}+\left(\frac{7}{4}\right)^{n-1}$$ and it's enough to prove that $$\left(\frac{7}{4}\right)^{n}+\left(\frac{7}{4}\right)^{n-1}\leq\left(\frac{7}{4}\right)^{n+1}$$ or $$\frac{7}{4}+1\leq\frac{49}{16},$$ which is $44\leq49$, which is true.

$(b)$ is true because by the definition of $G$ we obtain: $G_{n+2}=G_{n+1}+G_{n}$, $G_1=1$ and $G_2=2$.