1

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.

Community
  • 1
Guy001
  • 11
  • 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
  • See https://math.stackexchange.com/a/1538834/589 – lhf Oct 11 '18 at 11:35

1 Answers1

0

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$.

Michael Rozenberg
  • 194,933