Combinatorial proof of a Fibonacci identity: n F 1 + ( n − 1 )...

sdentatoiz

sdentatoiz

Answered

2022-09-11

Combinatorial proof of a Fibonacci identity: n F 1 + ( n 1 ) F 2 + + F n = F n + 4 n 3.
Does anyone know a combinatorial proof of the following identity, where F n is the nth Fibonacci number?

Answer & Explanation

Peugeota2p

Peugeota2p

Expert

2022-09-12Added 14 answers

Recall that F n + 1 is the number of ways to tile a board of length 𝑛 with tiles of length 1 and 2. So F n + 4 is the number of ways to tile a board of length n + 3 with tiles of length 1 and 2. Note that n + 3 such tilings use at most one tile of length 2, so F n + 4 ( n + 3 ) such tilings use at least two tiles of length 2.
Given such a tiling, look at where the second-to-last tile of length 2 is used. The part after this tile is a tiling of some section of length k + 1 where exactly one tile of length 2 is used (which can be done in k ways), and the part before this tile is a tiling of the remaining portion of length n k (which can be done in F n k + 1 ways). Sum over k.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?