\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf Some Trigonometric Identities Involving \\
\vskip .11in Fibonacci and Lucas Numbers} \vskip 1cm \large
Kh.\ Bibak and M. H. Shirdareh Haghighi\\
Department of Mathematics\\
Shiraz University\\
Shiraz 71454\\
Iran\\
\href{mailto:khmath@gmail.com}{\tt khmath@gmail.com}\\
\href{mailto:shirdareh@susc.ac.ir}{\tt shirdareh@susc.ac.ir}
\end{center}

\vskip .2 in

\begin{abstract}
In this paper, using the number of spanning trees in  some
classes of graphs, we prove the identities:
\begin{eqnarray*}
  &&F_n=\frac{2^{n-1}}{n}\sqrt{\prod_{k=1}^{n-1}(1-\cos\frac{k\pi}{n}\cos \frac{3k\pi}{n}}),\;\;n\geq 2,\\
  &&\prod_{k=0}^{n-1}(1+4\sin^2{\frac{k\pi}{n}})=L_{2n}-2=F_{2n+2}-F_{2n-2}-2,\;\;n\geq 1,
\end{eqnarray*}
where $F_n$ and $L_n$ denote the Fibonacci and Lucas numbers,
respectively. Also, we  give a new proof for the identity:
$$F_n=\prod_{k=1}^{\lfloor\frac{n-1}{2}\rfloor}(1+4\sin^2{\frac{k\pi}{n}})=\prod_{k=1}^{\lfloor\frac{n-1}{2}\rfloor}(1+4\cos^2{\frac{k\pi}{n}}),\;\;n\geq 4.$$
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}

\newcommand{\len}{\mbox{len}}
\newcommand{\bal}[1]{\begin{align*}#1\end{align*}}
\newcommand{\f}[2]{\displaystyle \frac{#1}{#2}}
\newcommand{\bt}{\begin{thm}}
\newcommand{\et}{\end{thm}}
\newcommand{\bp}{\begin{proof}}
\newcommand{\ep}{\end{proof}}
\newcommand{\bprop}{\begin{prop}}
\newcommand{\eprop}{\end{prop}}
\newcommand{\bl}{\begin{lemma}}
\newcommand{\el}{\end{lemma}}
\newcommand{\bc}{\begin{corollary}}
\newcommand{\ec}{\end{corollary}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}

\section{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\geq 1$ with
$F_1=F_2=1$, and $L_{n+2}=L_{n+1}+L_n$, for $n\geq 1$ with
$L_1=1$ and $L_2=3$.

In this paper, we derive the identities:
\begin{eqnarray}
  &&F_n=\frac{2^{n-1}}{n}\sqrt{\prod_{k=1}^{n-1}(1-\cos\frac{k\pi}{n}\cos \frac{3k\pi}{n}}),\;\;n\geq
  2,\label{iden1}\\
  &&\prod_{k=0}^{n-1}(1+4\sin^2{\frac{k\pi}{n}})=L_{2n}-2=F_{2n+2}-F_{2n-2}-2,\;\;n\geq 1
  \label{iden2}.
\end{eqnarray}
To prove identity (\ref{iden1}), we apply the number of spanning
trees in a special class of graphs known as circulant graphs.
Identity (\ref{iden2}) 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:
\begin{eqnarray}
 F_n=\prod_{k=1}^{\lfloor\frac{n-1}{2}\rfloor}(1+4\sin^2{\frac{k\pi}{n}})=\prod_{k=1}^{\lfloor\frac{n-1}{2}\rfloor}(1+4\cos^2{\frac{k\pi}{n}}),
 \;\;n\geq 4,\label{iden3}
\end{eqnarray}
appeared in \cite{gar} 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:
\begin{eqnarray}
  &&\prod_{k=1}^{n-1} \sin{\frac{k\pi}{2n}}=\frac{\sqrt{n}}{2^{n-1}},\;\;\;\;n\geq2,\label{iden4}\\
  &&\prod_{k=1}^{n-1} \sin{\frac{k\pi}{n}}=\frac{n}{2^{n-1}},\;\;\;\;n\geq 2.\label{iden5}
\end{eqnarray}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Techniques and Proofs}

For a graph $G$, a {\it 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 {\it Matrix-tree Theorem}. The
{\it 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  \cite{hoff}, $L(G)$ is also known
as the {\it Kirchhoff matrix } of the graph $G$.

\begin{theorem}\label{thrm1}
For every connected graph $G$,  $t(G)$ is equal to any cofactor
of $L(G)$.
\end{theorem}

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 \cite[Theorem 1]{ander}
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.

\begin{theorem}(\cite{doob})\label{thrm2}
Suppose $G$ is a connected graph with $n$ vertices. Let
$\lambda_1,\ldots,\lambda_n$ be the eigenvalues of $L(G)$, with
$\lambda_n=0$. Then
$t(G)=\frac{1}{n}\lambda_1\cdots\lambda_{n-1}$.
\end{theorem}

As the first example, we  prove identity (\ref{iden4}).

\bigskip

\noindent{\it Proof of identity (\ref{iden4}).} Consider the path $P_{n}$.
It is known that the eigenvalues of the Laplacian matrix of
$P_{n}$ are $2-2\cos {\frac{k\pi}{n}}\;(0\leq{k}\leq{n-1})$ (see,
e.g., \cite{bro}). On the other hand, we know that $t(P_{n})=1$,
therefore by using Theorem (\ref{thrm2}) we obtain (\ref{iden4}).
\hfill $\Box$


Now, we state some more definitions and theorems.

\begin{definition}
An $n\times n$ matrix $C=(c_{ij})$ is called a {\it 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,\ldots,n\}$.
\end{definition}

\begin{definition}
Let $1\leq{s_1}<s_{2}<\cdots<s_{k}<\frac{n}{2}$, where $n$ and
$s_{i}$ $(1\leq{i}\leq {k})$ are positive integers. An {\it
undirected circulant graph} $C_{n}(s_{1},s_{2},\ldots,s_{k})$ is a
$2k$-regular graph with vertex set $V=\{0,1,\ldots,n-1\}$ and
edge set $E=\{\{i,i+s_{j}\;\;(\mod n)\} \mid
i=0,1,\ldots,n-1,\;j=1,2,\ldots,k\}$.
\end{definition}

The Laplacian matrix of $C_{n}(s_{1},s_{2},\ldots,s_{k})$ is
clearly a circulant matrix. By a direct using of Theorem 4.8 of
\cite {zhang}, we obtain the following lemma:

\begin{lemma}\label{lem1}
The nonzero eigenvalues of $L(C_{n}(s_{1},s_{2},\ldots,s_{k}))$
are
$$2k-\omega^{s_{1}j}-\cdots-\omega^{s_{k}j}-\omega^{-s_{1}j}-\cdots-\omega^{-s_{k}j},\;\; 1\leq{j}\leq{n-1},$$
where $\omega=e^{{\frac{2\pi{i}}{n}}}$.
\end{lemma}

With combining  Theorem \ref{thrm2} and the lemma above, we obtain
the following corollary:

\begin{corollary}\label{coro1}
The number of spanning trees in
$G=C_{n}(s_{1},s_{2},\ldots,s_{k})$ is equal to:
$$t(G)={\frac{1}{n}}\prod_{j=1}^{n-1}\bigl(\;\sum_{i=1}^{k}(2-2\cos\frac{2js_{i}\pi}{n})\bigr).$$
\end{corollary}

\noindent{\it Proof of identity (\ref{iden1}).} Consider the {\it square
cycle} $C_{n}(1,2)$. We can use  Corollary \ref{coro1} to obtain
the number of spanning trees of $C_{n}(1,2)$. On the other hand,
Kleitman and Golden \cite{kleit} proved that $t(C_{n}(1,2))=nF_{n}
^{2}$. Now, with a little additional algebraic manipulation,
identity (\ref{iden1}) follows.\hfill $\Box$

\bigskip

\noindent{\it Proof of identity (\ref{iden5}).} Look at the cycle
$C_{n}(1)=C_{n}$. We know that $t(C_{n})=n$, therefore by
applying  Corollary \ref{coro1} to it, (\ref{iden5}) follows.
\hfill $\Box$

\begin{definition}
The join $W_{n}=C_{n}\bigvee{K_{1}}$ of a cycle $C_{n}$ and a
single vertex is referred to as a {\it wheel} with $n$ {\it
spokes}. Similarly, the join ${\cal F}_{n}=P_{n}\bigvee{K_{1}}$
of a path $P_{n}$ and a single vertex is called a {\it fan}.
\end{definition}

Sedlacek \cite{sed} and later Myers  \cite{myers} showed that
$t(W_{n})=L_{2n}-2=F_{2n+2}-F_{2n-2}-2,\;n\geq 1$. Also, Bibak
and Shirdareh Haghighi \cite{bibak1,bibak2} proved that $t({\cal
F}_{n})=F_{2n},\;n\geq 1$.

Now, we find the number of spanning trees in $W_{n}$ and ${\cal
F}_{n}$ by applying Theorem \ref{thrm2}. We first need to
determine the eigenvalues of $L(W_{n})$ and $L({\cal F}_{n})$.

\begin{theorem}(\cite{mer})\label{thrm3}
Let $G_{1}$ and $G_{2}$ be simple graphs on disjoint sets of $r$
and $s$ vertices, respectively. If
$S(G_{1})=(\mu_{1},\ldots,\mu_{r})$ and
$S(G_{2})=(\nu_{1},\ldots,\nu_{s})$ are the eigenvalues of
$L(G_{1})$ and $L(G_{2})$ arranged in nonincreasing order, then
the eigenvalues of $L(G_{1}\bigvee{G_{2}})$ are $n=r+s$;
$\mu_{1}+s,\ldots,\mu_{r-1}+s$; $\nu_{1}+r,\ldots,\nu_{s-1}+r$;
and 0.
\end{theorem}

Since the eigenvalues of $L(C_{n})$  are
$2-2\cos{\frac{2k\pi}{n}}$\;$(0\leq{k}\leq{n-1})$ (by Lemma
\ref{lem1}), and the eigenvalues of $L(P_{n})$ are
$2-2\cos{\frac{k\pi}{n}}$\;$(0\leq{k}\leq{n-1})$, therefore, by
Theorem \ref{thrm3} we can determine the eigenvalues of $L(W_{n})$
and $L({\cal F}_{n})$.

\begin{theorem}\label{thrm4}
The eigenvalues of $L(W_{n})$ are $n+1$,\;0 and
$1+4\sin^2{\frac{k\pi}{n}}$\;$(1\leq{k}\leq{n-1})$, and the
eigenvalues of $L({\cal F}_{n})$ are $n+1$,\;0 and
$1+4\sin^2{\frac{k\pi}{2n}}$\;$(1\leq{k}\leq{n-1})$\;(or
$n+1$,\;0 and
$1+4\cos^2{\frac{k\pi}{2n}}$\;$(1\leq{k}\leq{n-1})\;)$.
\end{theorem}

\noindent{\it Proofs of the identities (\ref{iden2}) and (\ref{iden3}).} By
Theorems \ref{thrm2} and \ref{thrm4}, the number of spanning trees
of $W_n$ and ${\cal F}_{n}$ are, respectively,
\begin{eqnarray*}
  &&t(W_{n})=\prod_{k=0}^{n-1}(1+4\sin ^2{\frac{k\pi}{n}}),\;\; n\geq1,\\
  &&t({\cal F}_{n})=\prod_{k=1}^{n-1}(1+4\sin^2{\frac{k\pi}{2n}})=\prod_{k=1}^{n-1}(1+4\cos^2{\frac{k\pi}{2n}}),\;\;n\geq2.
\end{eqnarray*}
On the other hand, as we already referred,
$t(W_{n})=L_{2n}-2=F_{2n+2}-F_{2n-2}-2,\;n\geq 1$ and $t({\cal
F}_{n})=F_{2n},\;n\geq 1$. Therefore, we obtain (\ref{iden2}) and
(\ref{iden3}).\hfill $\Box$


\begin{thebibliography}{99}

\bibitem{ander}{ W. N. Anderson
 and T. D. Morley, Eigenvalues of the Laplacian of a graph, {\it Linear Multilinear Algebra} {\bf 18} (1985), 141--145.}

\bibitem{bibak1}{ Kh.\ Bibak and M. H. Shirdareh Haghighi, Recursive relations for the number of spanning trees, {\it Appl. Math. Sci.} {\bf 3} (2009), 2263--2269.}

\bibitem{bibak2}{ Kh.\ Bibak and M. H. Shirdareh Haghighi, The number of spanning trees in some classes of graphs, {\it Rocky Mountain J. Math.}, to appear.}

\bibitem{bro}{A. E. Brouwer, A. M. Cohen and A. Neumaier, \textit{Distance-Regular Graphs}, Springer-Verlag, 1989.}

\bibitem{doob}{D. Cvetkovi\v{c}, M. Doob and H. Sachs, \textit{Spectra of Graphs: Theory and Applications}, third ed., Johann Ambrosius Barth, 1995.}

\bibitem{gar}{ N. Garnier and O. Ramar\'{e}, Fibonacci numbers and trigonometric identities, {\it Fibonacci Quart.} {\bf 46} (2008), 1--7.}

\bibitem{hoff}{ G. Kirchhoff, \"{U}ber die Aufl\"{o}sung der gleichungen auf, welche man bei der untersuchung der linearen verteilung galvanischer Str\"{o}me gef\"{u}hrt wird,
{\it Ann. Phy. Chem.} {\bf 72} (1847), 497--508.}

\bibitem{kleit}{ D. J. Kleitman and B. Golden, Counting trees in a certain class of graphs, {\it Amer. Math. Monthly} {\bf 82} (1975), 40--44.}

\bibitem{mer}{ R. Merris, Laplacian graph eigenvectors, {\it Linear Algebra Appl.} {\bf 278} (1998), 221--236.}

\bibitem{myers}{ B. R. Myers, Number of spanning trees in a wheel, {\it IEEE Trans. Circuit Theory} {\bf 18} (1971), 280--282.}

\bibitem{sed}{ J. Sedlacek, On the skeletons of a graph or digraph, {\it In Proc. Calgary International Conference on Combinatorial Structures and their Applications}, Gordon and
Breach, 1970, pp. 387--391.}

\bibitem{zhang}{F. Zhang, \textit{Matrix Theory: Basic Results and Techniques}, Springer-Verlag, 1999.}

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: Primary
11B39, Secondary 05C05, 15A18.

\noindent \emph{Keywords: } Fibonacci numbers, Lucas numbers,
spanning tree, trigonometric identity.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  November 16 2009;
revised version received  November 26 2009.
Published in {\it Journal of Integer Sequences}, November 29 2009.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}