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

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.

## marked as duplicate by Andrés E. Caicedo, Gerry Myerson, Jyrki Lahtonen, Jack D'Aurizio combinatorics StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Oct 11 '18 at 17:57

• both (a) and (b) follow by simply induction on $n$. In (a) at some point you replace $11/4$ by $(7/4)^2$ and in (b) just observe that for a of size $2xn$ you can tile with either 1 domino put horizontally at the bottom, or with 2 dominoes put vertically at the bottom; that will reduce the problem to size $n-1$ and $n-2$ respectively. – Hayk Oct 11 '18 at 11:21
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$$.