Graduate Theses, Dissertations, and Problem Reports

2016

Chebyshev Polynomials and Fibonacci Numbers

Nurul Wahyuni

Follow this and additional works at: https://researchrepository.wvu.edu/etd

Recommended Citation
Wahyuni, Nurul, "Chebyshev Polynomials and Fibonacci Numbers" (2016). Graduate Theses,
Dissertations, and Problem Reports. 6885.
https://researchrepository.wvu.edu/etd/6885

This Thesis is protected by copyright and/or related rights. It has been brought to you by the The Research
Repository @ WVU with permission from the rights-holder(s). You are free to use this Thesis in any way that is
permitted by the copyright and related rights legislation that applies to your use. For other uses you must obtain
permission from the rights-holder(s) directly, unless additional rights are indicated by a Creative Commons license
in the record and/ or on the work itself. This Thesis has been accepted for inclusion in WVU Graduate Theses,
Dissertations, and Problem Reports collection by an authorized administrator of The Research Repository @ WVU.
For more information, please contact researchrepository@mail.wvu.edu.
Chebyshev Polynomials and Fibonacci Numbers

Nurul Wahyuni

Thesis submitted
to the Eberly College of Arts and Sciences
at West Virginia University

in partial fulfillment of the requirements for the degree of

Master of Science in
Mathematics

Dr. Kevin Milans., Chair

Dr. Harvey Diamond
Dr. Michael Mays

Department of Mathematics

Morgantown, West Virginia

2016

Keywords: chebyshev polynomials, fibonacci numbers,

combinatorics

Copyright 2016 Nurul Wahyuni

 ABSTRACT

Chebyshev Polynomials and Fibonacci Numbers

Nurul Wahyuni

The Chebyshev polynomials arise in several mathematical contexts such as

approximation theory, numerical integration, and differential equations. Here
we study a combinatorial interpretation of Chebyshev polynomials due to
Shapiro, and we use it to give a slight variation of a combinatorial proof of
Binet’s Formula due to Benjamin, Derks and Quinn. Another beautiful for-
mula for the Fibonacci numbers involves complex roots of unity. Presently,
no combinatorial proof is known. We give combinatorial proofs of some re-
lated identities as progress toward a full combinatorial proof.
Contents

1 Introduction 1

2 Combinatorial Interpretation of Chebyshev Polynomials 3

2.1 Chebyshev Polynomials of the Second Kind . . . . . . . . . . 3
2.2 Chebyshev Polynomials of the First Kind . . . . . . . . . . . . 5
2.3 Chebyshev and Trigonometry . . . . . . . . . . . . . . . . . . 6

3 Another Proof for Binet’s Formula 9

4 Fibonacci and Roots of Unity 12

4.1 Current Incomplete Work . . . . . . . . . . . . . . . . . . . . 12
4.1.1 Tiling Approach . . . . . . . . . . . . . . . . . . . . . . 13
4.1.2 Graph Theoretic Approach . . . . . . . . . . . . . . . . 17

5 Conclusion 22

Bibliography 23

iii
Chapter 1

Introduction

Definition 1 The Chebyshev polynomials of the first kind are defined by the
recurrence relation T0 (x) = 1, T1 (x) = x, and for n ≥ 2,

Tn (x) = 2xTn−1 (x) − Tn−2 (x).

Definition 2 The Chebyshev polynomials of the second kind are defined by

the recurrence relation U0 (x) = 1, U1 (x) = 2x, and for n ≥ 2,

Un (x) = 2xUn−1 (x) − Un−2 (x).

Here is a list of the first few terms of Chebyshev polynomials of the first and
second kind

Table 1.1: First few terms for each sequence

n Tn Un
0 1 1
1 x 2x
2 2x2 − 1 4x2 − 1
3
3 4x − 3x 8x3 − 4x
4 8x4 − 8x2 + 1 16x4 − 12x2 + 1

At first sight, there is nothing special with these polynomials. However,

when we pick some special values for x, these polynomials become so special.
For instance, when x = i/2, where i ∈ C and i2 = −1, Chebyshev polyno-
mials of the second kind are related to Fibonacci numbers, Un (i/2) = in fn ,

1
where fn = Fn+1 , the shifted Fibonacci numbers. When x = cos θ, we
obtain nice trigonometric identites Tn (cos θ) = cos(nθ) and Un (cos θ) =
sin((n + 1)θ)/ sin θ.

2
Chapter 2

Combinatorial Interpretation of
Chebyshev Polynomials

First of all, let us recall the combinatorial interpretation for Fibonacci num-
bers. Traditionally, Fibonacci numbers are defined by F0 = 0, F1 = 1
and Fn = Fn−1 + Fn−2 for n ≥ 2. But in combinatorics, it is more nat-
ural to define fn = Fn+1 . The shifted Fibonacci fn counts the ways to
tile a strip of length n with squares and dominoes (see [1]). For example,
f3 = 3 and f4 = 5 count 3 tilings of length 3 and 5 tilings of length 4 below:

It turns out that Chebyshev polynomials count the same object but with a
weight assigned to each tile.

Definition 3 In a tiling whose tiles are assigned weights, the weight of the
tiling is the product of the weights of its tiles.

2.1 Chebyshev Polynomials of the Second Kind

Due to its simpler interpretation, we begin with Chebyshev polynomials of
the second kind. U0 = 1, U1 = 2x, and Un = 2xUn−1 − Un−1 for n ≥ 2 has
an interpretation as follow (see [2]).

3
Theorem 4 For n ≥ 0, Un (x) is the total weight of weighted tilings of length
n when squares have weight 2x and dominoes have weight −1.

Proof. We proceed by induction. For n = 0, empty tiling has weight 1. For

n = 1, we can only put a square tile, and the weight is 2x. So the initial
conditions agree with the recurrence. Since any tiling begins with either a
square or a domino, we can partition the tilings of length n ≥ 2 into two
groups, the tilings whose initial tile is a square and the tilings whose initial
tile is domino. Since a square has weigh 2x and followed by (n − 1)-tiling
which has total weight Un−1 (x), the first group has total weight 2xUn−1 (x).
Since a domino has weight −1 and followed by (n − 2)-tiling which has total
weight Un−2 (x), the second group has total weight (−1)Un−2 (x).

2x Un−1 (x) or −1 Un−2 (x)

Hence Un = 2xUn−1 + (−1)Un−2 = 2xUn−1 − Un−2 .

Here we provide the tilings of length two, three, four which sum to Cheby-
shev polynomials U2 (x), U3 (x), U4 (x).
2x 2x −1

2x 2x 2x 2x −1 −1 2x

2x 2x 2x 2x 2x 2x −1 2x −1 2x −1 2x 2x −1 −1
We can see that the total weight of the first row is 4x2 − 2 = U2 (x), and for
the second row 8x3 − 2x − 2x = 8x3 − 4x = U3 (x) and the last one has total
weight 16x4 − 4x2 − 4x2 − 4x2 + 1 = 16x4 − 12x2 + 1 = U4 (x).
We can extend this model into a colored tiling interpretation by splitting
the square into two squares of different colors. But now since we have two
kind of squares, each square has weight half of the beginning, which is x.
So, by giving the squares a color, black and white, we will have a colored
interpretation as follow (see [2]).

Corollary 5 For n ≥ 0, Un (x) counts the sum of the weights of n−tilings

with dominoes, white squares and black squares, by giving all dominoes a
weight of −1, all white squares and black squares a weight of x.

4
2.2 Chebyshev Polynomials of the First Kind
Chebyshev polynomials of the first kind only differ in their initial condition.
Due to their initial condition in which T1 (x) = x, we have a restriction for
the model. To make a model which agree with T1 (x) = x, and the recurrence
still follow the same rules, it is not surprising that we just need to make en
exception at it’s initial square, the square which is located at the first cell.
So here is the interpretation for Chebyshev polynomials for the first kind (see
[2]).

Theorem 6 For n ≥ 0, Tn (x) is the total weight of weighted tilings of length

n where an initial square has weight x, all other squares have weight 2x, and
all dominoes have weight −1. We will call this a restricted tiling.

Proof. We use induction. It is easy to verify that the first two terms are
good. Now consider a configuration of length n ≥ 2. Due to it’s restriction
at the initial tile, we cannot calculate the total weight by conditioning at
the first tile. Instead, we look at the last tile. We partition the tilings into
two groups, the first group consisting all tilings ended with a square and the
second group consisting all tilings ended with a domino. Since a square which
is not an initial has weight 2x and the first (n − 1)-tiling has total weight
Tn−1 (x), the first group has total weight 2xTn−1 (x). By the same logic, the
second group has total weight (−1)Tn−2 (x).

Tn−1 (x) 2x or Tn−2 (x) −1

Hence Tn (x) = 2xTn−1 (x) − Tn−2 (x).

Here we provide all configurations for T2 (x), T3 (x), and T4 (x).

x 2x −1

x 2x 2x x −1 −1 2x

x 2x 2x 2x x 2x −1 x −1 2x −1 2x 2x −1 −1
Here we can see that the total weight of the first row is 2x2 − 1 = T2 (x), the
second rows has total weight 4x3 − x − 2x = 4x3 − 3x = T3 (x) and the third
rows has total weight 8x4 − 2x2 − 2x2 − 4x2 + 1 = 8x4 − 8x2 + 1 = T4 x.

5
 For the colored tiling model, since Tn (x) has a restriction that the initial
square has weight half of the other squares, the initial square of any color has
weight x/2. Furthermore, another interpretation can be made by requiring
an initial square to be white and assigning an initial square a weight of x.
Hence, we have these two result (see [2]).

Corollary 7 For n ≥ 0, Tn (x) is the sum of the weights of n−tilings with

dominoes, white squares and black squares by giving all dominoes a weight of
−1, all white squares and black squares a weight of x, except that the initial
square has weight x/2.

Corollary 8 For n ≥ 0, Tn (x) is the sum of the weights of n−tilings with

dominoes, white squares and black squares by giving all dominoes a weight of
−1, all squares a weight of x with the restriction that the initial tile must be
either a white square or a domino.

The colored interpretation will help us in the next section to deal with
trigonometric identities involving Chebyshev polynomials.

2.3 Chebyshev and Trigonometry

When we substitute x = cos θ in each kind of Chebyshev polynomials, we
obtain these two upcoming nice theorems. And it is even more amazing
because we have combinatorial proof for them.
Recall De Moivre’s theorem einθ = cos(nθ) + i sin(nθ), which implies
1 1 inθ
cos(nθ) = (einθ + e−inθ ) and sin(nθ) = (e − e−inθ ).
2 2i
Since cos θ = 21 (eiθ +e−iθ ), we can interpret Tn (cos θ) as the sum of the weight
of colored tilings by assigning all white squares a weight of eiθ , all black
squares a weight of e−iθ , and all dominoes a weight of −1 with restriction
the initial white square has weight 21 eiθ and initial black square has weight
1 −iθ
2
e .
Since the second kind Chebyshev polynomials has no exception, Un (cos θ)
is the sum of the weight of colored tilings by assigning all white squares a
weight of eiθ , all white squares a weight of e−iθ , and all dominoes a weight of
−1. So now, we are ready to see combinatorial proof for these two theorems
(see [2]).

6
Theorem 9 For n ≥ 0,

Tn (cos θ) = cos(nθ).

Proof. We need to show the sum of the weights of colored n-tilings with
weights described above is equal to 21 (einθ + e−inθ ). Notice that the n-tiling
consisting all white squares has weight 12 einθ and the one consisting all black
squares has weight 12 e−inθ . So to prove this identity we need to show the
weights of the rest sum to zero.
In the other configurations, there exists the smallest index j such that
cells j and j + 1 are occupied by a domino or by squares of different colors.
We consider two cases.
If j > 1, we pair the tiling where cells j and j+1 are occupied by a domino
to the configuration where cells j and j + 1 are two squares of different colors
and leave the rest unchanged. If the tiles before the domino are all white
square then change the domino to white-black squares, otherwise change
the domino to black-white squares. Since a domino has weight −1 and two
different colors which is not at the beginning have weight eiθ e−iθ = 1, this
pair sums to zero.
For j = 1, we pair each tiling initialing with a domino to the two
tilings obatined by replacing the domino with an oppositely colored squares.
The total weight sums to zero because the initial white-black contributes a
weight of ( 12 eiθ )e−iθ = 21 and the initial black-white contributes a weight of
( 12 e−iθ )eiθ = 12 , which sum to 1.

Theorem 10 For n ≥ 0,
sin((n + 1)θ)
Un (cos(θ)) = .
sin θ
Proof. This is equivalent to (sin θ)Un (cos(θ)) = sin((n + 1)θ). Since sin θ =
1
2i
(eiθ − e−iθ ), the left hand side of our theorem is

eiθ e−iθ
Un (cos θ) + (− )Un (cos θ).
2i 2i
Hence, the left hand side is the sum of the weights of n + 1-tilings, where the
iθ
first tile is a special white square with weight e2i or a special black square
−iθ
with weight − e 2i and then followed by n-tilings with no restriction, i.e.
Un (cos θ).

7
 Meanwhile, the right hand side is
1 i(n+1)θ
− e−i(n+1)θ .


sin((n + 1)θ) = e
2i
iθ
The n + 1-tiling consisting all white squares has weight e2i · (eiθ )n = 2i1 ei(n+1)θ
−iθ
and the one consisting all black squares has weight − e 2i ·(e−iθ )n = − 2i1 ei(n+1)θ .
Like what we did in the previous theorem, we will show the rest of the
weights sum to zero. Again, let j be the first cell such that cells j and
j + 1 contain a domino or two squares of different colors. When j > 1, the
correspondence is the same as in Theorem 9. When j = 1, the initial black-
−iθ
white contributes a weight of − e 2i eiθ = −1/2i and an initial white-black
iθ
contributes a weight of e2i e−iθ = 1/2i. Thus the weights the tilings which
have the form black-white-X and white-black-X sum to zero.

8
Chapter 3

Another Proof for Binet’s

Formula

Recall Binet’s formula for Fibonacci numbers:

" √ !n √ !n #
1 1+ 5 1− 5
Fn = √ − .
5 2 2

Binet’s formula was first established using generating functions by Abraham

De Moivre in 1718 and then independently rediscovered by Jasques Binet
(1843) and Gabriel Lamé (1844). The first combinatorial proof for this was
using probability (see [1], [3], [6]). A more elegant combinatorial proof was
then presented in [4] by creating a weighted tiling interpretation for Fibonacci
numbers.
Here we will see a combinatorial proof for this formula using a Chebyshev
polynomial identity of the second kind. This simple identity that we found
in [9] is going to be useful.

Theorem 11
Un (i/2) = in fn .

Proof. Un (i/2) is interpreted as the sum of weights of n-tilings of dominoes

and squares where each domino has weight −1 and each square have weight i.
Since −1 = i·i, by viewing the value of every domino as i·i, any configuration
of length n have weight in .

9
Theorem 12
√ !n+1 √ !n+1
 
1 1 + 5 1− 5
Un (i/2) = in √  − .
5 2 2

Proof. It is equivalent to proving

√ !n+1 √ !n+1
 
√ i + i 5 i−i 5
(i 5)Un (i/2) =  − .
2 2

√ √
Let α = i+i2 5 and β = i−i2 5 . Observe some nice facts that α + β = i and
√
α − β = i 5, and moreover αβ = 1. Hence the left hand side of our identity
is (α − β)Un ( 12 (α + β)) and the right hand side is αn+1 − β n+1 . For our
combinatorial purpose, we will distribute the left hand side to be

(α)Un ((α + β)/2) + (−β)Un ((α + β)/2). (3.1)

Using the colored tiling interpretation, Un ((α + β)/2) is the sum of weighted
tilings with dominoes, white squares, and black squares by giving all domi-
noes a weight of −1, all white squares a weight of α and all black squares
a weight of β. Hence 3.1 can be interpreted as the sum of weights of all
(n + 1)−tilings with the restrictions the initial tile must be a square and a
black initial square has weight −β.
On the right hand side, pick any n + 1−tiling which initial tiling is a
square. The tiling consists all white squares has weight αn+1 and the tiling
with all black squares is going to be −β n+1 since the first black square has
weight −β. Now we will see that the sum of the rest configurations is zero.
Tilings other than those are tilings which involve dominoes or white and
black squares together. In those cases, there exist a smallest index j such that
cells j and j + 1 are occupied by a domino or cells j and j + 1 are occupied
by squares of different colors. Now let’s consider two cases for where j is
located.
Case 1: j > 1. If cells j and j + 1 are occupied by a domino, then pair
this tiling with a tiling in which cells j and j +1 are filled by different color of
squares and the rest is the same. The decision of the color of squares depends
on what is before the domino. It is either all black or all white. If it is all
black then the domino is replaced by black white, otherwise white black, as

10
illustrated below. In the other case, if cells j and j + 1 are occupied by
squares of different colors, then replace them with a domino. Since domino
has weight −1 and two different color which is not in the initial has weight
αβ = βα = 1, we get a one-to-one correspondence which sum up to zero.
Case 2: If j = 1, since the initial tiling is a square, the first two cells has
weight αβ in case it is white black or (−β)α in case it is black white. Put
these into one-to-one correspondence by leaving the rest unchanged. Since
αβ + (−β)α = 0, these will sum up to zero.

Corollary 13 Since Fn = fn−1 , theorem 1 and 2 will result in the nth Fi-
bonacci formula that we have in the beginning.

This proof is actually a slight variation from the one in [4], in which they
evaluate Un (x) at x = 1/2 instead of i/2. One can show that −Un (1/2) = fn .
Then the proof proceeds similarly.

11
Chapter 4

Fibonacci and Roots of Unity

4.1 Current Incomplete Work

Besides the famous Binet’s formula, we found another way to express Fi-
bonacci numbers explicitly (see [9]) as
b(n−1)/2c  
Y kπ
2
Fn = 1 + 4 cos . (4.1)
k=1
n

The algebraic proof for 4.1 can be found in [5]. Until now we have not
seen any combinatorial proof for this. Since Binet’s formula can be proved
combinatorially, it is natural to ask for a combinatorial proof of 4.1, which
is our main goal in this chapter. In this chapter, we present some related
identities.
Recall that 2 cos θ = eiθ + e−iθ . So,
b(n−1)/2c  
Y kπ
2
Fn = 1 + 4 cos
k=1
n
b(n−1)/2c
Y
= (1 + (e(kπi)/n + e−(kπi)/n )2 )
k=1
b(n−1)/2c
Y
= (3 + ek(2πi)/n + e−k(2πi)/n ).
k=1

12
For our convinience, we can write
b(n−1)/2c
Y
Fn = (3 + ζ k + ζ −k )
k=1

where ζ = e(2πi)/n , a primitive nth root of unity.

4.1.1 Tiling Approach

Our approach on finding the combinatorial interpretation of 4.1 is by studying
the combinatorial properties of this polynomial
n−1
def Y
An (x) = (x + ζ k + ζ −k )
k=0

where ζ = e(2πi)/n . Our aim is to see the combinatorial interpretation when

x = 3. But, here are the special cases for x = 0 and x = 2 which are also
interesting.

Theorem 14 For n ≥ 1 and ζ = e(2πi)/n ,


n−1
Y 2,
 if n ≡ 1 or 3 (mod 4)
k −k
An (0) = (ζ + ζ ) = 0, if n ≡ 0 (mod 4)

k=0 
−4, if n ≡ 2 (mod 4)

Proof. By expanding n−1 k −k

Q
k=0 (ζ + ζ ), An (0) can be interpreted as the total
weight of weighted tilings of a strip of length n in which the square at position
i has weight either ζ i or ζ −i for 0 ≤ i ≤ n − 1.
Define Wa,b as the set of tilings t having a cells with positive power of ζ
and b cells with negative power of ζ and for t ∈ Wa,b , w(t) denotes the weight
of tiling t. For example, this tiling t

ζ 0 ζ −1 ζ 2 ζ −3 ζ −4

belongs to W2,3 since it has 2 positive powers and 3 negative powers and
w(t) = ζ −6 . Wa,b is closed under cyclic sign rotation. Rotating the sign of a
tiling in Wa,b of weight α produce a tiling of weight ζ a ζ −b α. To see how this

13
works, multiply each ζ of positive power by ζ 1 and each ζ of negative power
by ζ −1 . For instance, let w(t) = ζ 0 ζ 1 ζ −2 ζ 3 ζ −4 ∈ W3,2 , then ζ 3 ζ −2 w(t) =
ζ −0 ζ 1 ζ 2 ζ −3 ζ 4 ∈ W3,2 . Now we will see how this cyclic pattern helps us in
grouping the tilings that vanish in the summation.
Case 1: n is odd. So now we have
X X X
ζ a−b w(t) = w(t) which implies (ζ a−b − 1) w(t) = 0.
t∈Wa,b t∈Wa,b t∈Wa,b

Note that ζ a−b = 1 if and only if n | a − b. If a ≥ 1 and b ≥ 1, since a

and b are at most n, n | a − b if and only if a − b = 0 or a = b. But since
Phappen. So, when a ≥ 1 and b ≥ 1, we
a + b = n and n is odd, this will not
have ζ a−b 6= 1, which then implies α∈Wa,b = 0. The only contributions for
the sum are when (a, b) = (n, 0) and (a, b) = (0, n). In the first case we have

ζ 0 ζ 1 · · · ζ n−1 = ζ n(n−1)/2 = (ζ n )(n−1)/2 = 1

and in the second case we have

ζ −0 ζ −1 · · · ζ −(n−1) = ζ −n(n−1)/2 = (ζ −n )(n−1)/2 = 1

since (n − 1)/2 is an integer. So we have An (0) = 2 for odd integer n.

Case 2: n ≡ 0 (mod 4). Since n ≡ 0 (mod 4), n/4 is an integer, moreover
ζ n/4 = i and ζ −n/4 = −i. Pair every tiling with ζ n/4 at the n/4 position with
the tiling having ζ −n/4 at the n/4 position and leaving the rest unchanged.
Since ζ n/4 and ζ −n/4 has the same magnitude and opposite sign, every pair
sums to zero. Therefore An (0) = 0 when n ≡ 0 (mod 4).
Case 3: n ≡ 2 (mod 4). We split every tiling into two tilings, the odd
indices and the even indices. Note that our index here start from 0 to n − 1.
Now in each group we have odd number of cells. We will work on one group,
and fix the other group.
Consider the even indexes configuration. Let α be a configration in Wa,b .
Note that now a is how many positive powers of ζ in even index cells and b
is how many negative powers of ζ in even index cells. So the configuration
in the odd indexes can be anything but it is fixed. Instead of multiplying
with ζ a ζ −b , we now multiply with ζ 2a ζ −2b because to shift the signs in even
indexes we need to move 2 cells ahead. Hence we have,
X X X
ζ 2(a−b) w(t) = w(t) which implies (ζ 2(a−b) − 1) w(t) = 0.
t∈Wa,b t∈Wa,b t∈Wa,b

14
ζ 2(a−b) = 1 if and only if n | 2(a−b) or n2 | a−b. Note that a+b = n/2 and n/2
is an odd integer. Using the similar argument as in case 1, this
P is not the case
when a ≥ 1 and b ≥ 1. Therefore when a ≥ 1 and b ≥ 1, t∈Wa,b w(t) = 0.
P
Similarly, when working on odd index cells, we have α∈Wa,b = 0 when a ≥ 1
and b ≥ 1. Hence the only contributions are when in each group we have all
the powers of ζ with the same sign. There are 4 possibilities,
• Both groups have all positive powers

ζ 0 ζ 1 · · · ζ n−1 = ζ n(n−1)/2 = (ζ n/2 )n−1 = (−1)n−1 = −1

since n − 1 is odd.

• Both groups have all negative powers

ζ −0 ζ −1 · · · ζ −(n−1) = ζ −n(n−1)/2 = (ζ −n/2 )n−1 = (−1)n−1 = −1

since n − 1 is odd.

• Even index cells have all positive powers and odd index cells have all
negative powers

2 /4
(ζ 0 ζ 2 · · · ζ n−2 )(ζ −1 ζ −3 · · · ζ −(n−1) ) = (ζ n(n−2)/4 )(ζ −n )
n/2 (n−2)/2 −n/2 n/2
= (ζ ) (ζ )
(n−2)/2 n/2
= (−1) (−1)
= 1 · −1 = −1

since (n − 2)/2 is even and n/2 is odd.

• Even index cells have all negative powers and odd index cells have all
positive powers
2 /4
(ζ −0 ζ −2 · · · ζ −(n−2) )(ζ 1 ζ 3 · · · ζ (n−1) ) = (ζ −n(n−2)/4 )(ζ n )
= (ζ −n/2 )(n−2)/2 (ζ n/2 )n/2
= (−1)(n−2)/2 (−1)n/2
= 1 · −1 = −1

since (n − 2)/2 is even and n/2 is odd.

15
Since each configuration contributes −1, we have An (0) = −4 when n ≡ 2
(mod 4).
Theorem 15 For n ≥ 1 and ζ = e(2πi)/n ,
n−1
(
Y 0, if n is even
An (2) = (2 + ζ k + ζ −k ) =
k=0
4, if n is odd
Proof. An (2) can be interpreted as the total weight of weighted tilings of
a strip of length n tiled with only squares where squares at position i has
weight either 2 or ζ i or ζ −i for 0 ≤ i ≤ n − 1.
Case 1: n is even. We can simply pair each tiling with weight 2 at the
n/2-position with two tilings we obtain by replacing 2 with ζ n/2 = −1 and
ζ −n/2 = −1 and leave the rest unchanged. These three tilings have total sum
zero.
Case 2: n is odd. Note that 2 + ζ k + ζ −k = 1 + ζ k + ζ −k + ζ k ζ −k =
(1 + ζ k )(1 + ζ −k ).
So,
n−1
Y n−1
Y n−1
Y
−k
k
(2 + ζ + ζ ) = k
(1 + ζ ) (1 + ζ −k ).
k=0 k=0 k=0
So, we can make another interpretation of An (2) as the total weight of the
weighted tilings of 2 × n-rectangle tiled with squares of different weights. For
the first row, the weight of the square at position i is either 1 or ζ i , and for
the second row, the weight of the square at position i is either 1 of ζ −i , where
0 ≤ i ≤ n − 1. Let a be the number of ζ appear on the first row, and b the
number of ζ appear in the second row so 0 ≤ a, b ≤ n. We will work on one
row and fix the other row.
Define Wa,b as usual, so if t ∈ Wa,b , then t has a cells with positive power
of ζ in the first row and b cells with a negative power of ζ in the second row.
For example this tiling below belongs to W2,3 .

1 1 1 ζ3 ζ4
1 ζ −1 1 ζ −3 ζ −4

If 1 ≤ a ≤ n − 1, ζ a 6= 1. With the same logic as in the proof of previous

theorem, by multiplying ζ a to the first row, we have
X X X X
ζa w(t) = w(t) ⇒ (ζ a − 1) w(t) = 0 ⇒ w(t) = 0.
t∈Wa,b t∈Wa,b t∈Wa,b t∈Wa,b

16
Now let 1 ≤ b ≤ n − 1, and fix any configuration on the first row. By
multiplying ζ −b to the second row, we have
X X X X
ζ −b w(t) = w(t) ⇒ (ζ −b − 1) w(t) = 0 ⇒ w(t) = 0
t∈Wa,b t∈Wa,b t∈Wa,b t∈Wa,b

since ζ −b 6= 1. Hence the only contributions for the sum are when (a, b) ∈
{(0, 0), (0, n), (n, 0), (n, n)}. By calculating it we have the weight for each
case 1. Therefore An (2) = 4 when n is odd.

4.1.2 Graph Theoretic Approach

Graph Interpretation of Matrix and Its Determinant
A matrix (aij ) can be described as a weighted directed graph G in which aij
is the weight of the edge uj to ui . For example
 
1 3 2
A = 1 2 3
2 3 1

is interpreted as this graph below.

u1
1 2

3 2

u2 u3
3

2 3 1

Definition 16 The weight of a weighted graph G is the product of the weights

of its edges.

In our example, the weight of graph A is 216.

17
Definition 17 A 1-regular subgraph of a directed graph G is a subgraph F
such that every vertex in F has an in degree and out degree one.

The computation of the determinant of a matrix can be done in its graph

representation using this theorem (see [7]).

Theorem 18 Let R(G) be the set of all 1-regular subgraph of graph G. The
determinant of a weighted directed graph G is
X
(−1)α(F ) w(F )
F ∈R(G)

where α(F ) is the number of even cycles in F .

Let Bn be an n×n matrix, with n ≥ 3, such that the first row is [x 1 0 0 . . . 1],
and each subsequent row is obtained by cyclically shifting the entries of the
previous row by one. So the second row of Bn is [1 x 1 0 0 . . . 0], and
 
x 1 0 0 ... 1
 1 x 1 0 . . . 0
 
Bn =  0 1 x 1 . . . 0 .

. . . 
1 0 0 0 ... x

Theorem 19 For n ≥ 3,
n−1
Y
det Bn = An (x) = (x + ζ k + ζ −k )
k=0

Proof. We present an algebraic proof of this. Note that if λ is an eigenvalue

of Bn with associated eigenvector v then Av = λv. The proof is by show-
ing that (x + ζ k + ζ −k ) is an eigenvalue of Bn with associated eigenvector

18
[1 ζ k (ζ k )2 . . . (ζ k )n−1 ]. By matrix multiplication, for 0 ≤ k ≤ (n − 1),
    
x 1 0 0 ... 1 1 x + ζ k + ζ −k
1 x 1 0 . . .
 0
 ζk    1 + xζ + ζ 
 k 2k 
0 1 x 1 . . . k 2   k 2k 3k 
 0  (ζ )  =  ζ + xζ + ζ 

 ..  ..   .. 
.  .   . 
k n−1 −2k −k
1 0 0 0 ... x (ζ ) 1+ζ + xζ
 
x + ζ k + ζ −k

 ζ k (x + ζ k + ζ −k )  
=
 ζ 2k (x + ζ k + ζ −k )  
 .. 
 . 
n−1 k k −k
(ζ ) (x + ζ + ζ )
 
1

 ζk  
−k k 2 
k
=x+ζ +ζ 
 (ζ ) .
 .. 
 . 
k n−1
(ζ )
Hence Bn v = λv. We claim that these eigenvectors are linearly independent.
To see this, we can create a Vandermonde matrix V by putting every eigen-
vector in a row of V . The determinant of this square Vandermonde matrix
V is Y
(ζ j − ζ i ).
0≤i<j≤n−1
i
Since all ζ are distinct, this number is nonzero. This implies V has linearly
independent rows. Therefore we obtain all of the eigenvalues of Bn . As
always, the determinant of a matrix is the product of its eigenvalues. Hence
we complete the proof.
Let us consider when x = 0. The graph representation of Bn will be a
doubly oriented circle as shown below:

19
Note that all the edges in the graph have weight 1. When n is odd, the only
1-regular subgraphs are the long cycles L1 and L2 . Since each of the long
cycles has sign (−1)0 = 1, the determinant of Bn is 2 · 1 = 2.
When n is even we also have 1-regular subgraphs F1 and F2 in which
every cycle has length 2. The sign for F1 and F2 is (−1)n/2 . Since L1 and L2
have a single cycle of even length, the sign for L1 and L2 is (−1)1 = −1. So
the determinant is 2(−1) + 2 · (−1)n/2 . When n ≡ 0 (mod 4), n/2 is even,
and therefore 2(−1) + 2(−1)n/2 = 0. When n ≡ 2 (mod 4), n/2 is odd, and
therefore 2(−1) + 2(−1)n/2 = −4. This is exactly what we have in Theorem
14.

Here is the general case.

Theorem 20 For n ≥ 3,
bn/2c  
n+1
X n
k n − k n−2k
An (x) = 2(−1) + (−1) x .
k=0
n − k k

Proof. An (x) is the determinant of matrix Bn which is interpreted as the

graph below.

x
x

x
x
x

x
x
In this graph, every
non loop edge has
weight 1.
There are 2 types of 1-regular subgraph here, long cycles and 2-cycles with
some loops. There are 2 long cycles, one in each direction. If the numbers

20
of vertices, n, is odd then the sign is (−1)0 = 1, and if n is even, the sign is
(−1)1 = −1. So we can say the contribution from long cycles is 2(−1)n+1 .
Now, let’s consider a 1-regular subgraph which consists of 2-cycles and/or
loops. Every 1-regular subgraph F with k 2-cycles and n − 2k loops will
contribute to the coefficient of xn−2k . So the task is now to count the 1-
regular subgraphs having k 2-cycles since the left over will just be the loops.
Notice that it is equivalent to counting the matchings of size k in the n-cycle
Cn . The correspondence is by transforming every edge in the matching into
a 2-cycle and vice versa. Note that the number of matchings of size k in Cn
is (see [8])  
n n−k
.
n−k k
For the subgraph F with k 2-cycles and n − 2k loops, the sign will be (−1)k
since every 2-cycle is an even cycle and every loop is an odd cycle. The result
follows by applying Theorem 19.

21
Chapter 5

Conclusion

For the future research, one can continue trying to prove 4.1 combinatorially
with our approach or using different methods. Specifically, let ζ = e(2πi)/n .

• Since
 2
n−1 b(n−1)/2c
Y Y
An (3) = (3 + ζ k + ζ −k ) = 5  (3 + ζ k + ζ −k ) ,
k=0 k=1

Qb(n−1)/2c
to complete the combinatorial proof of Fn = k=1 (3 + ζ k + ζ −k )
one needs to show for n ≥ 3,
bn/2c  
n+1
X nk n − k n−2k
2(−1) + (−1) 3 = 5Fn2 .
k=0
n−k k

• A combinatorial proof for

bn/2c  
n+1
X nk n − k n−2k
An (x) = 2(−1) + (−1) x
k=0
n−k k

is still an open problem.

22
Bibliography

[1] A.T. Benjamin and J.J Quin. Proofs That Really Count: The Art of
Combinatorial Proof. Mathematical Association of America, Washington,
DC, 2003.

[2] A.T. Benjamin, L. Ericksen, P. Jayawant, and M. Shattuck. Combina-

torial Trigonometry with Chebyshev Polynomials. Journal of Statistical
Planning and Inference. 2010

[3] A.T. Benjamin, G.M. Levin, K. Mahlburg, and J.J Quinn. Random Ap-
proaches to Fibonacci Identities. The American Mathematical Monthly,
Vol. 107, No. 6 (Jun.-Jul.,2000), 511-516.

[4] A.T. Benjamin, H. Derks, J.J. Quinn. The Combinatorialization of Linear

Recurrences. Mathematics Subject Classifications, 05A19, 11B37.

[5] B. Sury. Trigonometric Expressions for Fibonacci and Lucas Numbers.

Acta Math. Univ. Comenianae. Vol. LXXIX, 2(2010), pp. 199-208.

[6] C.R.H. Hanusa, A.T. Benjamin, and F.E. Su. Linear Recurrences
Through Tilings and Markov Chains.

[7] J.S. Maybee, D.D Olesky, P.V.D. Driessche, G. Wiener. Matrices, Digraph
and Determinant. AMS Subject Classification 05C50, 15A15. 1987.

[8] L. Lovász, M.D. Plummer. Matching Theory. Amsterdam, Netherlands:

North-Holland, 1986.

[9] N. Garnier, O. Ramaré. Fibonacci Numbers and Trigonometric Identities.

AMS Classification: 11B39. 2006

23