Fibonacci numbers as weighted averages of powers of 5 — a bijective/combinatorial proof

Question

A straightforward use of the binomial formula shows that the nonrecursive formula for the Fibonacci numbers,
$$
F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right),
$$
is equivalent to
$$
F_n=\frac{1}{2^{n-1}}\sum_k{\binom{n}{2k+1}5^k}=\frac{\sum_k{\binom{n}{2k+1}5^k}}{\sum_k{\binom{n}{2k+1}}}.
$$
However, I don't think I've seen a bijective proof of that identity, or perhaps, its division-free version,
$$
2^{n-1}F_n=\sum_k{\binom{n}{2k+1}5^k}.
$$
Most likely, I am simply unaware of an existing proof (who knows, maybe even on MSE). Do you know of any references where this is proved? Alternatively, a combinatorial proof would be great. Thanks!

Answer 1

There is a combinatorial proof given in

Benjamin, Arthur & Quinn, Jennifer. (1999). Fibonacci and Lucas identities through colored tilings. Utilitas Mathematica. 56.

It is available online here.

The proof is a bit too involved for me to try to reproduce here. Basically, $2^nF_{n+1}$ counts ways to color the $n$ cells of a $1\times n$ board white and black, and then cover that same board with transparent squares and dominoes. The underlying white/black coloring leads to two flavors of squares and four flavors of dominoes, depending on what colored squares they cover. Alternatively, you can choose a subset of the squares in $\binom{n}{2k+1}$ ways. This subset breaks the board into intervals, and each even interval can be covered in five ways. But there are still several details to iron out; one sentence that stands out is "The coloring rules, as stated, have two deficiencies, which conveniently complement each other."