1
$\begingroup$

Using double counting,

Answer 1: Consider two boards, a $(1 \times n)$-board and $(1 \times (n-1))$-board. There are ${F_{n+1}}$ ways to tile the first board and ${F_n}$ ways to tile the other. So there are $ {F_n}{F_{n+1}}$ ways to tile both the boards together.

I don't know how to do the second argument. Please help!

$\endgroup$
0
2
$\begingroup$

Consider the representative Fibonacci tiling below. The vertical side has height $F_n$ and the overall width is $F_n+F_{n-1}=F_{n+1}$. Thus the area shown is $F_nF_{n+1}$ which is the sum of all the squares, i.e.,

$$F_nF_{n+1}=\sum_{k=0}^nF_k^2$$

as was to be shown.

Fibonacci area demo

$\endgroup$
1
$\begingroup$

HINT: for $k,n \geq 2$, $$F_kF_n = F_{n+k-1} + F_{n-2}F_{k-2}$$

$\endgroup$
1
  • $\begingroup$ Sorry I don't see how I can use this with tiling $\endgroup$ Sep 27 '17 at 2:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.