Some Trigonometric Identities Involving Fibonacci and Lucas Numbers

Kh. Bibak and M. H. Shirdareh Haghighi Department of Mathematics Shiraz University Shiraz 71454 Iran

                   khmath@gmail.com
                 shirdareh@susc.ac.ir

Abstract

In this paper, using the number of spanning trees in some classes of graphs, we prove the identities:

F_{n} = \frac{2^{n−1}}{n} \sqrt{∏_{k=1}^{n−1}(1 − cos \frac{kπ}{n} cos \frac{3kπ}{n}}), n ≥ 2,

∏_{k=0}^{n−1}(1 + 4 sin^{2} \frac{kπ}{n}) = L_{2n} − 2 = F_{2n+2} − F_{2n−2} − 2, n ≥ 1,

where F_{n} and L_{n} denote the Fibonacci and Lucas numbers, respectively. Also, we give a new proof for the identity:

F_{n} = ∏_{k=1}^{⌊ \frac{n−1}{2} ⌋}(1 + 4 sin^{2} \frac{kπ}{n}) = ∏_{k=1}^{⌊ \frac{n−1}{2} ⌋}(1 + 4 cos^{2} \frac{kπ}{n}), n ≥ 4.

1 Introduction

Let F_{n} and L_{n} denote the Fibonacci and Lucas numbers respectively. That is, F_{n+2} = F_{n+1} + F_{n}, for n ≥ 1 with F_{1} = F_{2} = 1, and L_{n+2} = L_{n+1} + L_{n}, for n ≥ 1 with L_{1} = 1 and L_{2} = 3.

In this paper, we derive the identities:

F_{n} = \frac{2^{n−1}}{n} \sqrt{∏_{k=1}^{n−1}(1 − cos \frac{kπ}{n} cos \frac{3kπ}{n}}), n ≥ 2,  (1)

∏_{k=0}^{n−1}(1 + 4 sin^{2} \frac{kπ}{n}) = L_{2n} − 2 = F_{2n+2} − F_{2n−2} − 2, n ≥ 1.  (2)

To prove identity (1), we apply the number of spanning trees in a special class of graphs known as circulant graphs. Identity (2) is derived from the number of spanning trees in a wheel.

Applying the same technique to a graph known as fan gives us a new proof for the following identity:

F_{n} = ∏_{k=1}^{⌊ \frac{n−1}{2} ⌋}(1 + 4 sin^{2} \frac{kπ}{n}) = ∏_{k=1}^{⌊ \frac{n−1}{2} ⌋}(1 + 4 cos^{2} \frac{kπ}{n}), n ≥ 4,  (3)

appeared in [6] and its corresponding references.

Also, applying this technique to the path P_{n} and the cycle C_{n} gives us a new proof for the well-known identities:

∏_{k=1}^{n−1} sin \frac{kπ}{2n} = \frac{\sqrt{n}}{2^{n−1}} , n ≥ 2,  (4)

∏_{k=1}^{n−1} sin \frac{kπ}{n} = \frac{n}{2^{n−1}} , n ≥ 2.  (5)

2 Techniques and Proofs

For a graph G, a spanning tree in G is a tree which has the same vertex set as G. The number of spanning trees in a graph (network) G, denoted by t(G), is an important invariant of the graph (network). It is also an important measure of reliability of a network. In the sequel, we assume our graphs are loopless but multiple edges are allowed.

A famous and classic result on the study of t(G) is the following theorem, known as the Matrix-tree Theorem. The Laplacian matrix of a graph G is defined as L(G) = D(G)−A(G), where D(G) and A(G) are the degree matrix and the adjacency matrix of G, respectively. Since this theorem is first proved by Kirchhoff [7], L(G) is also known as the Kirchhoff matrix of the graph G.

Theorem 1. For every connected graph G, t(G) is equal to any cofactor of L(G).

The number of spanning trees of a connected graph G can be expressed in terms of the eigenvalues of L(G). Since by definition, L(G) is a real symmetric matrix, it therefore has n non-negative real eigenvalues, where n is the number of vertices of G. Anderson and Morley [1, Theorem 1] proved that the multiplicity of 0 as an eigenvalue of L(G) equals the number of components of G. Therefore, the Laplacian matrix of a connected graph G has 0 as an eigenvalue with multiplicity one.

Theorem 2. ([5]) Suppose G is a connected graph with n vertices. Let λ_{1}, …, λ_{n} be the eigenvalues of L(G), with λ_{n} = 0. Then t(G) = \frac{1}{n}λ_{1} ⋯ λ_{n−1}.

As the first example, we prove identity (4).

Proof of identity (4). Consider the path P_{n}. It is known that the eigenvalues of the Laplacian matrix of P_{n} are 2 − 2 cos \frac{kπ}{n} (0 ≤ k ≤ n − 1) (see, e.g., [4]). On the other hand, we know that t(P_{n}) = 1, therefore by using Theorem (2) we obtain (4). □

Now, we state some more definitions and theorems.

Definition 3. An n × n matrix C = (c_{ij}) is called a circulant matrix if its entries satisfy c_{ij} = c_{1, j−i+1}, where subscripts are reduced modulo n and lie in the set {1, 2, …, n}.

Definition 4. Let 1 ≤ s_{1} < s_{2} < ⋯ < s_{k} < \frac{n}{2}, where n and s_{i} (1 ≤ i ≤ k) are positive integers. An undirected circulant graph C_{n}(s_{1}, s_{2}, …, s_{k}) is a 2k-regular graph with vertex set V = {0, 1, …, n − 1} and edge set E = {{i, i + s_{j} ( mod n)} | i = 0, 1, …, n − 1, j = 1, 2, …, k}.

The Laplacian matrix of C_{n}(s_{1}, s_{2}, …, s_{k}) is clearly a circulant matrix. By a direct using of Theorem 4.8 of [12], we obtain the following lemma:

Lemma 5. The nonzero eigenvalues of L(C_{n}(s_{1}, s_{2}, …, s_{k})) are

2k − ω^{s_{1}j} − ⋯ − ω^{s_{k}j} − ω^{−s_{1}j} − ⋯ − ω^{−s_{k}j}, 1 ≤ j ≤ n − 1,

where ω = e^{\frac{2πi}{n}}.

With combining Theorem 2 and the lemma above, we obtain the following corollary:

Corollary 6. The number of spanning trees in G = C_{n}(s_{1}, s_{2}, …, s_{k}) is equal to:

t(G) = \frac{1}{n} ∏_{j=1}^{n−1}( ∑_{i=1}^{k}(2 − 2 cos \frac{2js_{i}π}{n})).

Proof of identity (1). Consider the square cycle C_{n}(1, 2). We can use Corollary 6 to obtain the number of spanning trees of C_{n}(1, 2). On the other hand, Kleitman and Golden [8] proved that t(C_{n}(1, 2)) = nF_{n}^{2}. Now, with a little additional algebraic manipulation, identity (1) follows. □

Proof of identity (5). Look at the cycle C_{n}(1) = C_{n}. We know that t(C_{n}) = n, therefore by applying Corollary 6 to it, (5) follows. □

Definition 7. The join W_{n} = C_{n} ⋁ K_{1} of a cycle C_{n} and a single vertex is referred to as a wheel with n spokes. Similarly, the join F_{n} = P_{n} ⋁ K_{1} of a path P_{n} and a single vertex is called a fan.

Sedlacek [11] and later Myers [10] showed that t(W_{n}) = L_{2n}−2 = F_{2n+2}−F_{2n−2}−2, n ≥ 1. Also, Bibak and Shirdareh Haghighi [2, 3] proved that t(F_{n}) = F_{2n}, n ≥ 1.

Now, we find the number of spanning trees in W_{n} and F_{n} by applying Theorem 2. We first need to determine the eigenvalues of L(W_{n}) and L(F_{n}).

Theorem 8. ([9]) Let G_{1} and G_{2} be simple graphs on disjoint sets of r and s vertices, respectively. If S(G_{1}) = (μ_{1}, …, μ_{r}) and S(G_{2}) = (ν_{1}, …, ν_{s}) are the eigenvalues of L(G_{1}) and L(G_{2}) arranged in nonincreasing order, then the eigenvalues of L(G_{1} ⋁ G_{2}) are n = r+s; μ_{1} + s, …, μ_{r−1} + s; ν_{1} + r, …, ν_{s−1} + r; and 0.

Since the eigenvalues of L(C_{n}) are 2 − 2 cos \frac{2kπ}{n} (0 ≤ k ≤ n − 1) (by Lemma 5), and the eigenvalues of L(P_{n}) are 2 − 2 cos \frac{kπ}{n} (0 ≤ k ≤ n − 1), therefore, by Theorem 8 we can determine the eigenvalues of L(W_{n}) and L(F_{n}).

Theorem 9. The eigenvalues of L(W_{n}) are n + 1, 0 and 1 + 4 sin^{2} \frac{kπ}{n} (1 ≤ k ≤ n − 1), and the eigenvalues of L(F_{n}) are n + 1, 0 and 1 + 4 sin^{2} \frac{kπ}{2n} (1 ≤ k ≤ n − 1) (or n + 1, 0 and 1 + 4 cos^{2} \frac{kπ}{2n} (1 ≤ k ≤ n − 1) ).

Proofs of the identities (2) and (3). By Theorems 2 and 9, the number of spanning trees of W_{n} and F_{n} are, respectively,

t(W_{n}) = ∏_{k=0}^{n−1}(1 + 4 sin^{2} \frac{kπ}{n}), n ≥ 1,

t(F_{n}) = ∏_{k=1}^{n−1}(1 + 4 sin^{2} \frac{kπ}{2n}) = ∏_{k=1}^{n−1}(1 + 4 cos^{2} \frac{kπ}{2n}), n ≥ 2.

On the other hand, as we already referred, t(W_{n}) = L_{2n} − 2 = F_{2n+2} − F_{2n−2} − 2, n ≥ 1 and t(F_{n}) = F_{2n}, n ≥ 1. Therefore, we obtain (2) and (3). □

References

[1] W. N. Anderson and T. D. Morley, Eigenvalues of the Laplacian of a graph, Linear Multilinear Algebra 18 (1985), 141–145.

[2] Kh. Bibak and M. H. Shirdareh Haghighi, Recursive relations for the number of spanning trees, Appl. Math. Sci. 3 (2009), 2263–2269.

[3] Kh. Bibak and M. H. Shirdareh Haghighi, The number of spanning trees in some classes of graphs, Rocky Mountain J. Math., to appear.

[4] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, 1989.

[5] D. Cvetkovič, M. Doob and H. Sachs, Spectra of Graphs: Theory and Applications, third ed., Johann Ambrosius Barth, 1995.

[6] N. Garnier and O. Ramaré, Fibonacci numbers and trigonometric identities, Fibonacci Quart. 46 (2008), 1–7.

[7] G. Kirchhoff, Über die Auflösung der gleichungen auf, welche man bei der untersuchung der linearen verteilung galvanischer Ströme geführt wird, Ann. Phy. Chem. 72 (1847), 497–508.

[8] D. J. Kleitman and B. Golden, Counting trees in a certain class of graphs, Amer. Math. Monthly 82 (1975), 40–44.

[9] R. Merris, Laplacian graph eigenvectors, Linear Algebra Appl. 278 (1998), 221–236.

[10] B. R. Myers, Number of spanning trees in a wheel, IEEE Trans. Circuit Theory 18 (1971), 280–282.

[11] J. Sedlacek, On the skeletons of a graph or digraph, In Proc. Calgary International Conference on Combinatorial Structures and their Applications, Gordon and Breach, 1970, pp. 387–391.

[12] F. Zhang, Matrix Theory: Basic Results and Techniques, Springer-Verlag, 1999.

2000 Mathematics Subject Classification: Primary 11B39, Secondary 05C05, 15A18. Keywords: Fibonacci numbers, Lucas numbers, spanning tree, trigonometric identity.

(Concerned with sequences \underline{A000032} and \underline{A000045}.)

Received November 16 2009; revised version received November 26 2009. Published in Journal of Integer Sequences, November 29 2009.

Return to Journal of Integer Sequences home page.