International Mathematical Forum, 5, 2010, no.

18, 869 - 874

New Proofs of Some Fibonacci Identities

Marcin Krzywkowski

Faculty of Applied Physics and Mathematics

Gdańsk University of Technology
Narutowicza 11/12, 80952 Gdansk, Poland
fevernova@wp.pl
Abstract
Lucas proved in 1876 several identities for Fibonacci numbers. We give
elementary and short proofs of them.

Mathematics Subject Classification: 11B39

Keywords: Fibonacci number

By Fibonacci sequence we mean the sequence {Fn }∞ n=1 such that F1 = 1,

F2 = 1, and Fn = Fn−2 + Fn−1 , for n ≥ 3. The elements of this sequence
are called Fibonacci numbers. Lucas proved in 1876 that Pfor every positive
n
integer
Pn n we have F
P 2n+1 = F 2
n + F 2
n+1 , F 2n = F 2
n+1 − F 2
n−1 , i=1 i = Fn+2 − 1,
F
n
i=1 F2i−1 = F2n , i=1 F2i = F2n+1 − 1, see [1], pages 69, 71, and 79. We give
combinatorial proofs of these identities which are elementary and short.
Let us consider dominoes of dimensions 2 × 1 and an area of dimensions
2 × n, where n is a positive integer. Squares of our area are signed as follows:
upper from left to right by integers from 1 to n, and lower from left to right
by symbols from 10 to n0 . By the i-th column we mean the pair of squares
i and i0 . By the position of a domino we mean the set of squares on which
this domino lies. The covering of the area is the set of positions of dominoes
which cover this area. Two coverings are distinguish if and only if proper sets
of positions are different. Let the sequence {an }∞ n=1 be such that an is the
number of distinguish coverings of the area of dimensions 2 × n. For example,
a1 = 1, a2 = 2, and a3 = 3, see Figure 1. We also define a0 = 1.

Figure 1
870 M. Krzywkowski

In the following lemma we give a recursive formula for an .

Lemma 1 For every positive integer n ≥ 3 we have an = an−2 + an−1 .

Proof. If we want to cover the area of dimensions 2 × n, then the domino on

the square 1 lies horizontally or vertically, see Figure 2.

.....

.....

Figure 2

If it lies horizontally, then we have to cover the rest area of dimensions 2×

(n − 2). There are an−2 possibilities of doing that. If it lies vertically, then
we have to cover the rest area of dimensions 2 × (n − 1). There are a n−1
possibilities of doing that. Adding these numbers, we get a n = an−2 + an−1 .

Now we prove a relation between elements of sequences {an }∞

n=1 and {Fn }n=1 .
∞

Lemma 2 If n is a positive integer, then an = Fn+1 .

Proof. We have a1 = 1 = F2 , a2 = 2 = F3 , and the same recurrent formula

effects for both sequences {an }∞
n=1 and {Fn }n=1 , so an = Fn+1 .
∞

Now let us prove the following formula for a Fibonacci number with an odd
index.

Theorem 3 (Lucas, 1876) For every positive integer n we have

F2n+1 = Fn2 + Fn+1

2
.

Proof. By Lemma 2, the identity above is equivalent to a 2n = a2n−1 + a2n . Let

us consider two halfs of the area of dimensions 2 × 2n (two areas of dimensions
2 × n each). If we cover the area of dimensions 2 × 2n, then its halfs have
common dominoes or do not have common dominoes, see Figure 3.
In the first case it remains to cover independently two areas of dimensions
2 × (n − 1) each, there are a2n−1 possibilities of doing that. In the second case
we have to cover independently two areas of dimensions 2×n each, there are a 2n
possibilities of doing that. Adding these numbers, we get a 2n = a2n−1 + a2n .
New proofs of some Fibonacci identities 871

..... .....

..... .....

Figure 3

Now we prove a formula for a Fibonacci number with an even index.

Theorem 4 (Lucas, 1876) If n is a positive integer, then

2 2
F2n = Fn+1 − Fn−1 .

Proof. By Lemma 2, the identity above is equivalent to a 2n−1 = a2n − a2n−2 .

Since a2n − a2n−2 = (an−2 + an−1 )2 − a2n−2 = a2n−1 + 2an−2 an−1 , it suffices to prove
that a2n−1 = a2n−1 + 2an−2 an−1 . If we cover the area of dimensions 2 × (2n − 1),
then there are the following three possibilities respecting the column n: it is
covered by a domino lying vertically, or it is covered (together with column
n − 1) by pair of dominoes lying horizontally, or it is covered (together with
column n + 1) by pair of dominoes lying horizontally, see Figure 4.

..... .....

..... .....

..... .....

Figure 4

In the first case it remains to cover independently two areas of dimensions

2 × (n − 1) each, there are a2n−1 possibilities of doing that. In the second case
it remains to cover independently two areas of dimensions 2×(n−2) and 2×n,
there are an−2 an possibilities of doing that. In the third case, by symmetry to
872 M. Krzywkowski

the previous case, there are also an−2 an possibilities. Adding these numbers,
we get a2n−1 = a2n−1 + 2an−2 an−1 .

Now let us observe that Theorem 4 can be also easily proved using Theorem
3. We have F2n = F2n+1 −F2n−1 = Fn2 +Fn+1 2 2
−Fn−1 −Fn2 = Fn+1
2 2
− Fn−1 . The-
orem 3 similarly follows from Theorem 4, as F2n+1 = F2n+2 −F2n = Fn+2 − Fn2
2
2 2
−Fn+1 + Fn−1 = (Fn + Fn+1 )2 − Fn2 − Fn+1
2
+ (Fn+1 − Fn )2 = Fn2 + 2Fn Fn+1
2
+Fn+1 − Fn2 − Fn+1
2 2
+ Fn+1 − 2Fn Fn+1 + Fn2 = Fn2 + Fn+1
2
.

Now let us prove a formula for n first Fibonacci numbers.

Theorem 5 (Lucas, 1876) For every positive integer n we have

n
X
Fi = Fn+2 − 1.
i=1
P
Proof. By Lemma 2, the identity above is equivalent to n−1 i=0 ai = an+1 − 1.
Let us consider all possible coverings of the area of dimensions 2 × (n + 1) ex-
cluding the covering in which every domino lies vertically. There are a n+1 − 1
such coverings. Now let us count these coverings in different way. Since we
exclude the covering in which every domino lies vertically, every considered
covering has at least one pair of dominoes lying horizontally (one above an-
other). Let us consider the pair of indices of columns which are covered by first
(considering from left side) pair of dominoes lying horizontally. ”The small-
est” such possible pair is (1, 2), ”the next” possible is (2, 3), and ”the greatest”
possible is (n, n + 1), see Figure 5.

.....

.....

.....

Figure 5

There are ai possibilities of covering the area of dimensions 2 × (n + 1) in

such way that the first pair of dominoes lying horizontally covers the columns
n − i and n − i + 1. Thus the number of distinguish coverings of the area
New proofs of some Fibonacci identities 873

of dimensions 2 × (n P+ 1) excluding the covering in which every domino lies

vertically is equal to n−1
i=0 ai .

Now we prove the following formula for n first Fibonacci numbers with
even indices.

Theorem 6 (Lucas, 1876) If n is a positive integer, then

n
X
F2i = F2n+1 − 1.
i=1
Pn
Proof. The identity above is equivalent to i=1 a2i−1 = a2n − 1. Let us
consider all possible coverings of the area of dimensions 2 × 2n excluding the
covering in which every domino lies horizontally. There are a 2n − 1 such cov-
erings. Let us count these coverings in different way. Since we exclude the
covering in which every domino lies horizontally, every considered covering
has a domino lying vertically. Let us consider the column which is covered by
the first (considering from the left side) domino lying vertically. The index of
this column is odd, because the part of the area on the left side of that col-
umn has an even length, as it is covered only by dominoes lying horizontally.
The smallest such possible index is 1, the next possible is 3, and the greatest
possible is 2n − 1, see Figure 6.

.....

.....

.....

Figure 6

There are a2i−1 possibilities of covering the area of dimensions 2 × 2n in such

way that the first (considering from the left side) domino lying vertically covers
the column 2n−2i−1. Thus the number of coverings of the area of dimensions
2 ×P2n excluding the covering in which every domino lies horizontally is equal
to ni=1 a2i−1 .

Now we prove a formula for n first Fibonacci numbers with odd indices.
874 M. Krzywkowski

Theorem 7 (Lucas, 1876) For every positive integer n we have

n
X
F2i−1 = F2n .
i=1
P
Proof. The identity above is equivalent to n−1 i=0 a2i = a2n−1 . Let us consider
all possible coverings of the area of dimensions 2 × (2n − 1). There are a 2n−1
such coverings. Let us count these coverings in different way. Every counted
covering has a domino lying vertically, because our area has an odd length.
Let us consider the column which is covered by first (considering from the left
side) domino lying vertically. The index of this column is odd, because the
part of the area on the left side of that column has an even length, as it is
covered only by dominoes lying horizontally. The smallest such possible index
is 1, the next possible is 3, and the greatest possible is 2n − 1, see Figure 7.

.....

.....

.....

Figure 7

There are a2i possibilities of covering the area of dimensions 2 × (2n − 1) in

such way that the first (considering from the leftPside) domino lying vertically
covers the column 2n − 2i − 1. Thus there are n−1 i=0 a2i distinguish coverings
of the area of dimensions 2 × (2n − 1).
P2n
PIt is easy to see
P that Theorem 5 follows from Theorems 6 and 7, as i=1 Fi
= ni=1 F2i−1 + ni=1 F2i = F2n + F2n+1 − 1 = F2n+2 − 1. Similarly, Theorems
6 and 7 follow from each other.

References
[1] T. Koshy, Fibonacci and Lucas Numbers with Applications, Wiley-
Interscience, Canada, 2001.

Received: November, 2009