\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf A Graph-Theoretic Model for a \\
\vskip .1in
Generalized Fibonacci Gem}
\vskip 1cm
\large
Thomas Koshy \\
Department of Mathematics \\
Framingham State University \\
Framingham, MA 01701 \\
USA \\
\href{mailto:tkoshy@emeriti.framingham.edu}{\tt tkoshy@emeriti.framingham.edu}\\
\end{center}
\vskip .2 in
\begin{abstract}
We extend a charming Fibonacci pleasantry to Fibonacci, Lucas, Jacobsthal, and Jacobsthal-Lucas polynomials; and then confirm the resulting polynomial delights using graph-theoretic tools.
\end{abstract}
\section{Introduction}
\textit{Generalized Fibonacci polynomials} $z_n(x)$ are defined by the recurrence $z_n(x) = a(x)z_{n-1}(x) + b(x)z_{n-2}(x)$, where $x$ is an arbitrary complex variable; $a(x), b(x), z_0(x)$, and $z_1(x)$ are arbitrary complex polynomials; and $n\geq 2$.
Let $a(x) = x$ and $b(x) = 1$. When $z_0(x) = 0$ and $z_1(x) = 1$, $z_n(x) = f_n(x)$, the $n$th \textit{Fibonacci polynomial}; and when $z_0(x) = 2$ and $z_1(x) = x$, $z_n(x) = l_n(x)$, the $n$th \textit{Lucas polynomial}. Clearly, $f_n(1) = F_n$, the $n$th Fibonacci number; and $l_n(1) = L_n$, the $n$th Lucas number \cite{almdeberhan-etal, bicknell, koshy0, koshy1}.
\textit{Pell polynomials} $p_n(x)$ and \textit{Pell-Lucas polynomials} $q_n(x)$ are defined by $p_n(x) = f_n(2x)$ and $q_n(x) = l_n(2x)$, respectively. The \textit{Pell numbers} $P_n$ and \textit{Pell-Lucas numbers} $Q_n$ are given by $P_n = p_n(1) = f_n(2)$ and $2Q_n = q_n(1) = l_n(2)$, respectively \cite{horadam-mahon, koshy3}.
Suppose $a(x) = 1$ and $b(x) = x$. When $z_0(x) = 0$ and $z_1(x) = 1$, $z_n(x) = J_n(x)$, the $n$th \textit{Jacobsthal polynomial}; and when $z_0(x) = 2$ and $z_1(x) = 1$, $z_n(x) = j_n(x)$, the $n$th \textit{Jacobsthal-Lucas polynomial} \cite{horadam1, horadam2}. Correspondingly, $J_n = J_n(2)$ and $j_n = j_n(2)$ are the $n$th Jacobsthal and Jacobsthal-Lucas numbers, respectively. Clearly, $J_n(1) = F_n$; and $j_n(1) = L_n$.
The polynomials $f_n(x), l_n(x), J_n(x)$, and $j_n(x)$ can also be defined explicitly using \emph{Binet-like} formulas:
\begin{center}
\begin{tabular}{llll}
$f_n(x) = \displaystyle{\frac{\alpha^n - \beta^n}{\alpha - \beta}}$; & & & $l_n(x) = \alpha^n + \beta^n$;\\[0.15cm]
$J_n(x) = \displaystyle{\frac{u^n - v^n}{u - v}}$; & & & $j_n(x) = u^n + v^n$,
\end{tabular}
\end{center}
where $\alpha = \alpha(x)$ and $\beta = \beta(x)$ are the solutions of the equation $t^2 - xt - 1$, and $u = u(x)$; and $v = v(x)$ are those of $t^2 - t - x = 0$. Notice that $\alpha - \beta = \sqrt{x^2 + 4}$ and $u - v = \sqrt{4x + 1}$.
In the interest of brevity, clarity, and convenience, we \emph{omit} the argument in the functional notation, when there is \emph{no} ambiguity; so $z_n$ means $z_n(x)$. In addition, we let $g_n = f_n$ or $l_n$; $b_n = p_n$ or $q_n$; and $c_n = J_n(x)$ or $j_n(x)$; and correspondingly, $G_n = F_n$ or $L_n$; $B_n = P_n$ or $Q_n$; and $C_n = J_n$ or $j_n$.
\section{$Q$-matrix and digraph}
Gibonacci polynomials $f_n$ and $l_n$ can be studied using the $Q$-matrix
\begin{equation*}
Q = \begin{bmatrix}
x & 1\\
1 & 0
\end{bmatrix},
\end{equation*}
where $Q = Q(x) = (q_{ij})_{2\times 2}$ \cite{koshy4, koshy5}. It then follows by induction that
\begin{equation*}
Q^n = \begin{bmatrix}
f_{n+1} & f_n\\
f_n & f_{n-1}
\end{bmatrix},
\end{equation*}
where $n\geq 1$.
The $Q$-matrix has a graph-theoretic appeal. It can be interpreted as the \emph{weighted adjacency matrix} of a \emph{weighted digraph} $D_1$ with vertices $v_1$ and $v_2$ \cite{koshy4, koshy5}; see Figure \ref{figure01}. Notice that a \emph{weight} is assigned to each edge.
A \emph{walk} from vertex $v_i$ to vertex $v_j$ is a sequence $v_i$-$e_i$-$v_{i+1}$-$\cdots$-$v_{j-1}$-$e_{j-1}$-$v_j$ of vertices $v_k$ and edges $e_k$, where edge $e_k$ is incident with vertices $v_k$ and $v_{k+1}$. The walk is \emph{closed} if $v_i = v_j$; otherwise, it is \emph{open}. The \emph{length} of a walk is the number of edges in the walk. The \emph{weight} of a walk is the product of the weights of the edges along the walk.
We can employ the weighted adjacency matrix to compute the weight of a walk of length $n$ from any vertex $v_i$ to any vertex $v_j$, as the following theorem shows \cite{koshy2, koshy4}.
\begin{figure}[H]
\centering
\includegraphics[width=4in]{graph3.eps}
\caption{Weighted digraph $D_1$}\label{figure01}
\end{figure}
\begin{theorem}\label{theorem01}~
Let $A$ be the weighted adjacency matrix of a weighted and connected digraph with vertices $v_1, v_2, \ldots, v_k$. Then the $ij$th entry of the matrix $A^n$ gives the sum of the weights of all walks of length $n$ from $v_i$ to $v_j$, where $n\geq 1$.
\end{theorem}
This theorem implies the following result.
\begin{corollary}\label{corollary01}~
The $ij$th entry of $Q^n$ gives the sum of the weights of all walks of length $n$ from $v_i$ to $v_j$ in the weighted digraph $D_1$, where $1\leq i,j\leq 2$.
\end{corollary}
It follows by this corollary that the sum of the weights of all closed walks of length $n$ originating in the digraph model is $f_{n+1}$, and that of walks of length $n$ originating at $v_2$ is $f_{n-1}$. So the sum of the weights of all closed walks of length $n$ is $f_{n+1} + f_{n-1} = l_n$.
\section{A Gibonacci delight}
In 1963, H. W. Gould established a charming identity for Fibonacci squares \cite{hould1, koshy1}:
\begin{equation}
F^2_{n+3} = 2F^2_{n+2} + 2F^2_{n+1} - F^2_n.\label{equation01}
\end{equation}
It has a simple, but delightful geometric interpretation \cite{koshy1}.
The next theorem extends identity \eqref{equation01} to gibonacci polynomials $g_n$.
\begin{theorem}\label{theorem02}~
\begin{equation}
g^2_{n+3} = f_3g^2_{n+2} + f_3g^2_{n+1} - g^2_n.\label{equation02}
\end{equation}
\end{theorem}
\begin{proof}~
Using the gibonacci recurrence, we have
\begin{eqnarray*}
g^2_{n+3} + g^2_n & = & (xg_{n+2} + g_{n+1})^2 + (g_{n+2} - xg_{n+1})^2\\
& = & (x^2 + 1)g^2_{n+2} + (x^2 + 1)g^2_{n+1}.
\end{eqnarray*}
This yields the desired identity. (It also follows by Binet's formulas.)
\end{proof}
\section{Graph-theoretic models}
With these tools at our finger tips, we can give graph-theoretic interpretations of the gibonacci results in Theorem \ref{theorem02}. The essence of our technique hinges on Corollary \ref{corollary01}, and the \textquotedblleft{weighted}\textquotedblright version of \emph{Fubini's principle} \cite{alsina-nelsen, koshy1}: \textit{Counting the number of elements in a set in two different ways yields the same result.}
We begin our discourse with $g_n = f_n$.
\subsection{Interpretation with $g_n = f_n$}
It follows by Corollary \ref{corollary01} that the sum of the weights of closed walks of length $n + 2$ originating at $v_1$ is $f_{n+3}$. The sum $S$ of the weights of ordered pairs $(v,w)$ of such closed walks is the product of the sum of the weights of such walks $v$ and $w$. Consequently, $S = f^2_{n+3}$.
We will now compute the sum $S$ in a different way.
\begin{proof}
\noindent\textit{Case 1}. Suppose $v$ and $w$ begin with a loop at $v_1$. The sum of the weights of pairs $(v,w)$ of such closed walks of length $n + 2$ is $(xf_{n+2})(xf_{n+2}) = x^2f^2_{n+2}$.
\bigskip
\noindent\textit{Case 2}. Suppose $v$ begins with a loop at $v_1$, but $w$ does \textit{not}. The sum of the weights of pairs of such closed walks is $(xf_{n+2})(1\cdot 1\cdot f_n) = xf_{n+2}f_n$.
\bigskip
\noindent\textit{Case 3}. On the other hand, suppose $v$ does \textit{not} begin with a loop, but $w$ does. The sum of the weights of pairs of such closed walks is $(1\cdot 1\cdot f_n)(xf_{n+2}) = xf_{n+2}f_n$.
\bigskip
\noindent\textit{Case 4}. Finally, suppose neither $v$ nor $w$ begins with a loop. The contribution of pairs of such walks toward the sum $S$ is $(1\cdot f_{n+1})(1\cdot f_{n+1}) = f^2_{n+1}$.
\bigskip
Combining the four cases, we also get
\begin{eqnarray*}
S & = & x^2f^2_{n+2} + f^2_{n+1} + 2xf_{n+2}f_n\\
& = & (x^2 + 1)f^2_{n+2} + (x^2 + 1)f^2_{n+1} - f^2_n,
\end{eqnarray*}
as in the proof of Theorem \ref{theorem02}.
Equating the cumulative sums yields the desired result.
\end{proof}
As a byproduct, this discourse then gives a graph-theoretic proof of the Pell identity
\begin{equation*}
p^2_{n+3} = p_3p^2_{n+2} + p_3p^2_{n+1} - p^2_n.
\end{equation*}
Next we investigate the graph-theoretic interpretation of identity \eqref{equation02} with $g_n = l_n$.
\subsection{Interpretation with $g_n = l_n$}
\begin{proof}
Let $A$ denote the set of closed walks of length $n + 3$ originating at $v_1$, and $B$ that of length $n + 3$ originating at $v_2$. Let $C = A\cup B$, where $A\cap B = \emptyset$. The sum of the weights of all closed walks in $C$ equals $f_{n+4} + f_{n+2} = l_{n+3}$. Consequently, the sum $S$ of the weights of ordered pairs $(v,w)\in C\times C$ is given by $S = l^2_{n+3}$.
To compute this sum in a different way, first we make an interesting observation. By Theorem \ref{theorem02}, we have
\begin{eqnarray}
x^2f^2_{n+3} + 4f^2_{n+2} + 4xf_{n+3}f_{n+2} & = & (xf_{n+3} + 2f_{n+2})^2\nonumber\\
& = & (f_{n+4} + f_{n+2})^2\nonumber\\
& = & l^2_{n+3}\label{equation03}\\
& = & f_3l^2_{n+2} + f_3l^2_{n+1} - l^2_n.\nonumber
\end{eqnarray}
Consequently, it suffices to establish graph-theoretically the equivalent identity
\begin{equation}
x^2f^2_{n+3} + 4f^2_{n+2} + 4xf_{n+3}f_{n+2} = l^2_{n+3}.\label{equation04}
\end{equation}
We will accomplish this using four cases for an arbitrary element $(v,w)\in C\times C$.
\bigskip
\noindent\textit{Case 1}. Suppose $v, w\in A$. Suppose both $v$ and $w$ begin with a loop. The sum of the weights of pairs $(v,w)$ of such closed walks is $(xf_{n+3})(xf_{n+3}) = x^2f^2_{n+3}$. If $v$ begins with a loop at $v_1$ and $w$ does \emph{not}, then $v\in A$ and $w\in B$. The sum of the weights of all such pairs $(v,w)$ of closed walks equals $(x\cdot f_{n+3})(1\cdot 1\cdot f_{n+2}) = xf_{n+3}f_{n+2}$. Suppose $v$ does \emph{not} begin with a loop, but $w$ does. Then $v\in B$ and $w\in A$. The sum of the weights of all such pairs $(v,w)$ of closed walks equals $(1\cdot 1\cdot f_{n+2})(x\cdot f_{n+3}) = xf_{n+3}f_{n+2}$. Suppose neither $v$ nor $w$ begins with a loop. The total contribution by the corresponding pairs $(v,w)$ is $(1\cdot 1\cdot f_{n+2})(1\cdot 1\cdot f_{n+2}) = f^2_{n+2}$.
Thus, when $v,w\in A$, the sum of the weights of such closed walks of length $n + 3$ is given by
\begin{equation*}
S_1 = x^2f^2_{n+3} + 2xf_{n+3}f_{n+2} + f^2_{n+2}.
\end{equation*}
\noindent\textit{Case 2}. Suppose $v\in A$ and $w\in B$. If $v$ begins with a loop, then the sum of the weights of products of such closed walks of length $n + 3$ is $(xf_{n+3})(f_{n+2}) = xf_{n+3}f_{n+2}$. On the other hand, suppose $v$ does not begin with a loop. The corresponding sum is $(1\cdot 1\cdot f_{n+2})(f_{n+2}) = f^2_{n+2}$. Consequently, the total contribution from this case is
\begin{equation*}
S_2 = xf_{n+3}f_{n+2} + f^2_{n+2}.
\end{equation*}
\noindent\textit{Case 3}. Suppose $v\not\in A$, but $w\in B$. Then $v\in B$. If $w$ begins with a loop, the resulting contribution is $(f_{n+2})(xf_{n+3}) = xf_{n+3}f_{n+2}$. If $w$ does not begin with a loop, then the corresponding contribution is $(f_{n+2})(1\cdot 1\cdot f_{n+2}) = f^2_{n+2}$. Consequently, the total contribution from Case 3 toward the cumulative sum is
\begin{equation*}
S_3 = xf_{n+3}f_{n+2} + f^2_{n+2}.
\end{equation*}
\noindent\textit{Case 4}. Suppose $v, w\in B$. Clearly, the resulting contribution from this case toward $S$ is
\begin{equation*}
S_4 = (f_{n+2})(f_{n+2}) = f^2_{n+2}.
\end{equation*}
Collecting all contributions from the four cases and using identities \eqref{equation02} and \eqref{equation03}, we get
\begin{eqnarray*}
S & = & S_1 + S_2 + S_3 + S_4\\
& = & x^2f^2_{n+3} + 4f^2_{n+2} + 4xf_{n+3}f_{n+2}\\
& = & l^2_{n+3},
\end{eqnarray*}
as desired.
\end{proof}
\noindent\textit{An Alternate Proof}.~~
\begin{proof}
Alternatively, by focusing on the closed walks at $v_1$ alone, we can establish identity \eqref{equation03}. To see this, let $C$ denote the set of closed walks of length $n+3$ at $v_1$, and $D$ that of length $n+1$ at $v_1$. Let $E = C\cup D$, where $C\cap D = \emptyset$. The sum of the weights of the walks in $E$ is $f_{n+4} + f_{n+2} = l_{n+3}$. Consequently, the sum $S$ of the weights of elements in $E\times E$ is $S = l^2_{n+3}$.
We will now compute $S$ in a different way. (In the interest of brevity, we highlight the key steps only.) To this end, let $(v,w)$ be an arbitrary element in $E\times E$.
Suppose $v, w\in C$. Then the sum of the weights of the pairs $(v,w)$ of such closed walks is given by
\begin{equation*}
S_1 = x^2f^2_{n+3} + f^2_{n+2} + 2xf_{n+3}f_{n+2}.
\end{equation*}
On the other hand, let $v\in C$ and $w\in D$. The total contribution from such pairs $(v,w)$ is
\begin{eqnarray*}
S_2 & = & x^2f^2_{n+3}f_{n+1} + xf_{n+3}f_n + xf_{n+2}f_{n+1} + f_{n+2}f_n\\
& = & f^2_{n+2} + xf_{n+3}f_{n+2}.
\end{eqnarray*}
When $v, w\in D$, the total contribution from the corresponding pairs is
\begin{eqnarray*}
S_3 & = & x^2f^2_{n+1} + 2xf_{n+1}f_n + f^2_n\\
& = & f^2_{n+2}.
\end{eqnarray*}
Finally, let $v\in D$ and $w\in C$. The corresponding contribution is
\begin{eqnarray*}
S_4 & = & x^2f_{n+3}f_{n+1} + xf_{n+3}f_n + xf_{n+2}f_{n+1} + f_{n+2}f_n\\
& = & f^2_{n+2} + xf_{n+3}f_{n+2}.
\end{eqnarray*}
Thus the cumulative sum $S$ of the weights of all pairs $(v,w)\in E\times E$ is also given by
\begin{eqnarray*}
S_1 + S_2 + S_3 + S_4 & = & x^2f^2_{n+3} + 4f^2_{n+2} + 4xf_{n+3}f_{n+2}\\
& = & l^2_{n+3},
\end{eqnarray*}
as expected.
\end{proof}
Since \cite{florez-etal, koshy5}
\begin{equation*}
g^2_{n+1} + g_n^2 = \begin{cases}
f_{2n+1}, & {\rm if}~ g_n = f_n;\\
(x^2 + 4)f_{2n+1}, & {\rm if}~ g_n = l_n;
\end{cases}
\end{equation*}
these models also give a graph-theoretic interpretation of the identity \cite{almdeberhan-etal, florez-etal, koshy5}
\begin{eqnarray*}
g^2_{n+3} + g_n^2 & = & (x^2 + 1)(g^2_{n+2} + g_{n+1}^2)\\
& = & \begin{cases}
(x^2 + 1)f_{2n+3}, & {\rm if}~ g_n = f_n;\\
(x^2 + 1)(x^2 + 4)f_{2n+3}, & {\rm if}~ g_n = l_n.
\end{cases}
\end{eqnarray*}
We now add that using the bijection algorithm in \cite{koshy4}, we can translate the graph-theoretic models into tiling models with squares and dominoes, where weight(square) = $x$; weight(domino) = 1; and the weight of a tiling is the product of the weights of tiles in the tiling.
Replacing $x$ with $2x$ in this discourse yields a graph-theoretic proof of the Pell-Lucas identity
\begin{eqnarray*}
q^2_{n+3} & = & 4x^2p^2_{n+3} + 4p^2_{n+2} + 8xp_{n+3}p_{n+2}\\
& = & p_3q^2_{n+2} + p_3q^2_{n+1} - q^2_n.
\end{eqnarray*}
Finally, it follows from identity \eqref{equation04} that
\begin{equation*}
F^2_{n+3} + 4F^2_{n+2} + 4F_{n+3}F_{n+2} = L^2_{n+3}.
\end{equation*}
Consequently, an $L_{n+3}\times L_{n+3}$ floor can be tessallated with nine tiles: one $F_{n+3}\times F_{n+3}$ tile; four $F_{n+2}\times F_{n+2}$ tiles; and four $F_{n+3}\times F_{n+2}$ tiles, where $n\geq 0$.
\section{Jacobsthal implications}
Using the gibonacci-Jacobsthal relationships $J_n(x) = x^{(n-1)/2}f_n(u)$ and $j_n(x) = x^{n/2}l_n(u)$ \cite{koshy0}, we can easily find the Jacobsthal counterparts of identities \eqref{equation02} and \eqref{equation03}, where $u = 1/\sqrt{x}$:
\begin{eqnarray}
c^2_{n+3} & = & J_3(x)c^2_{n+2} + xJ_3(x)c^2_{n+1} - x^3c^2_n;\label{equation05}\\
j^2_{n+1}(x) & = & J^2_{n+1}(x) + 4x^2J^2_{n}(x) + 4xJ_{n+1}(x)J_n(x),\nonumber
\end{eqnarray}
respectively. (We have \textit{omitted} the basic algebra for brevity and convenience.)
Consequently,
\begin{eqnarray}
C^2_{n+3} & = & 3C^2_{n+2} + 6C^2_{n+1} - 8C^2_n;\nonumber\\
j^2_{n+1} & = & J^2_{n+1} + 16J^2_n + 8J_{n+1}J_n.\label{equation06}
\end{eqnarray}
Identity \eqref{equation06} implies that a $j_{n+1}\times j_{n+1}$ floor can be tiled with 25 tiles: one $J_{n+1}\times J_{n+1}$ tile; sixteen $J_n\times J_n$ tiles; and eight $J_{n+1}\times J_n$ tiles, where $n\geq 1$.
\subsection{A Jacobsthal digraph}
Next we confirm independently identity \eqref{equation05} using
graph-theoretic tools. To this end, we first present a weighted digraph
$D_2$; see Figure \ref{figure02}. Its weighted adjacency matrix is
\begin{equation*}
M = \begin{bmatrix}
1 & x\\ 1 & 0
\end{bmatrix}.
\end{equation*} Then \begin{equation*}
M^n = \begin{bmatrix}
J_{n+1}(x) & xJ_n(x)\\
J_n(x) & xJ_{n-1}(x)
\end{bmatrix},
\end{equation*} where $n\geq 1$; we can confirm this using induction.
\begin{figure}[H]
\centering
\includegraphics[width=4in]{jacob00.eps}
\caption{Weighted digraph $D_2$}\label{figure02}
\end{figure}
It then follows that the sum of the weights of closed walks of length
$n$ originating at $v_1$ is $J_{n+1}(x)$, and that of those originating
at $v_2$ is $xJ_{n-1}(x)$. Consequently, the sum of all closed walks of
length in the digraph $D_2$ is $J_{n+1}(x) + xJ_{n-1}(x) = j_n(x)$. These
facts play a central role in the graph-theoretic proof.
With these tools at our finger tips, we now present the proof of each
part.
\begin{proof}
\leavevmode
\emph{Part 1}.~~To establish part 1, we let $A$ be the
set of closed walks of length $n + 2$ starting at $v_1$. The sum of the
weights of all such closed walks is $J_{n+3}(x)$; so the sum $S$ of the
weights of all ordered pairs $(v,w)\in A\times A$ is $J^2_{n+3}(x)$.
We will now compute $S$ in a different way. Again, let $(v,w)$
be an arbitrary element of $A\times A$. Suppose both $v$ and $w$
begin with a loop; the sum of the weights of such pairs $(v,w)$ is
$[1\cdot J_{n+2}(x)][1\cdot J_{n+2}(x)] = J^2_{n+2}(x)$. If $v$ begins
with a loop and $w$ does \emph{not}, the corresponding sum is $[1\cdot
J_{n+2}(x)][x\cdot 1\cdot J_{n+1}(x)] = xJ_{n+2}(x)J_{n+1}(x)$. Suppose
$v$ does \emph{not} begin with a loop, but $w$ does; then also the
resulting sum is $[x\cdot 1\cdot J_{n+1}(x)][1\cdot J_{n+2}(x)] =
xJ_{n+2}(x)J_{n+1}(x)$. Finally, if both $v$ and $w$ do \emph{not}
begin with a loop, the contribution from such pairs equals $[x\cdot
1\cdot J_{n+1}(x)][x\cdot 1\cdot J_{n+1}(x)] = x^2J^2_{n+1}(x)$.
Thus the cumulative contribution of pairs $(v,w)$ all closed walks of
length $n + 2$ starting at $v_1$ is given by \begin{eqnarray*}
S & = & J^2_{n+2}(x) + 2xJ_{n+2}(x)J_{n+1}(x) + x^2J^2_{n+1}(x)\\
& = & J^2_{n+2}(x) + xJ_{n+2}(x)[J_{n+2}(x) - xJ_n(x)] +
xJ_{n+1}(x)[J_{n+1}(x) + xJ_n(x)] + x^2J^2_{n+1}(x)\\ & = & (x +
1)J^2_{n+2}(x) + x(x + 1)J^2_{n+1}(x) - x^2J_n(x)[J_{n+2}(x) -
J_{n+1}(x)]\\ & = & (x + 1)J^2_{n+2}(x) + x(x + 1)J^2_{n+1}(x)
- x^3J_n(x).\\[-0.75cm]
\end{eqnarray*}
\end{proof}
Combining the two values of $S$ yields identity \eqref{equation05}
when $c_n = J_n(x)$.\\[0.25cm] \emph{Part 2}.~~To confirm identity
\eqref{equation05} when $c_n = j_n(x)$, we focus on the closed walks of
lengths $n + 3$ and $n$ in the digraph. Let $C$ be the set of closed walks
of length $n+3$ starting at $v_1$, and $D$ the set of those starting at
$v_2$. Clearly, $C\cap D = \emptyset$, so the sum of the weights of the
walks in $F = C\cup D$ is $j_{n+3}(x)$. Consequently, the sum $S_1$ of
the weights of the ordered pairs $(v,w)\in F\times F$ is $j^2_{n+3}(x)$.
Now let $R$ denote the set of closed walks of length $n$ originating
at $v_1$, and $S$ that of those originating at $v_2$. It follows by the
preceding argument that the sum $S_2$ of the weights of the ordered pairs
$(v,w)\in G\times G$ is $j^2_n(x)$, where $ G = R\cup S$ and $R\cap S
= \emptyset$.
Thus \begin{equation*}
S_1 + x^3S_2 = j^2_{n+3}(x) + x^3j^2_n(x).
\end{equation*}
We will now compute the sum $S_1 + x^3S_2$ in a different way. Again,
let $(v,w)$ be an arbitrary element of $F\times F$.
Suppose $v,w\in C$. Then the sum of the weights of pairs $(v,w)$
of such closed walks of length $n+3$ originating at $v_1$
is $[J_{n+4}(x)][J_{n+4}(x)] = J^2_{n+4}(x)$. If $v\in C$ and
$w\in D$, then the resulting sum is $[J_{n+4}(x)][xJ_{n+2}(x) =
xJ_{n+4}(x)J_{n+2}(x)$. When $v\in D$ and $w\in C$, the corresponding
sum is $[xJ_{n+2}(x)][J_{n+4}(x)] = xJ_{n+4}(x)J_{n+2}(x)$. Finally,
when $v,w\in D$, the contribution from such pairs $(v,w)$ is
$[xJ_{n+2}(x)][xJ_{n+2}(x)] = x^2J^2_{n+2}(x)$. Thus \begin{equation*}
S_1 = J^2_{n+4}(x) + 2xJ_{n+4}(x)J_{n+2}(x) + x^2J^2_{n+2}(x).
\end{equation*}
It then follows that \begin{equation*}
S_2 = J^2_{n+1}(x) + 2xJ_{n+1}(x)J_{n-1}(x) + x^2J^2_{n-1}(x).
\end{equation*}
Consequently, $S_1 + x^3S_2 = A + B$, where \begin{eqnarray*}
A & = & J^2_{n+4}(x) + x^2J^2_{n+2}(x) + x^3J^2_{n+1}(x);\\ B & = &
x^5J^2_{n-1}(x) + 2xJ_{n+4}(x)J_{n+2}(x) + 2x^4J_{n+1}(x)J_{n-1}(x).
\end{eqnarray*}
\begin{proof}
We will now confirm that $S_1 + x^3S_2 = (x + 1)j^2_{n+2}(x) + x(x +
1)j^2_{n+1}(x)$. The proof involves a lot of carefully prepared basic
algebra; so in the interest of brevity, clarity, and convenience, we
present only the major steps; also we \emph{omit} the argument in the
functional notation.
We have \begin{eqnarray*}
A & = & (J_{n+3} + xJ_{n+2})^2 + x^2J^2_{n+2} + x^3J^2_{n+1}\\
& = & J^2_{n+3} + 2x^2J^2_{n+2} + 2xJ_{n+2}(J_{n+2} + xJ_{n+1}) +
x^3J^2_{n+1}\\ & = & J^2_{n+3} + (x^2 + x)J^2_{n+2} + x^3J^2_{n+1} +
(x^2 + x)J^2_{n+2} + 2x^2J_{n+2}J_{n+1}\\ & = & J^2_{n+3} + (x^2 +
x)J^2_{n+2} + x^3J^2_{n+1} + (x^2 + x)J^2_{n+2} + 2x^2J_{n+1}(J_{n+3}
- xJ_{n+1})\\ & = & J^2_{n+3} + (x^2 + x)J^2_{n+2} + x^3J^2_{n+1} +
(x^2 + x)J^2_{n+2} + 2x^2J_{n+3}J_{n+1} - 2x^3J^2_{n+1};\\
B & = & x^3(J_{n+1} - J_n)^2 + 2xJ_{n+2}(J_{n+3} + xJ_{n+2}) +
2x^3J_{n+1}(J_{n+1} - J_n)\\
& = & x^3J^2_{n+1} + x^3J^2_n - 2x^3J_{n+1}J_n + 2xJ_{n+3}J_{n+2} +
2x^2J^2_{n+2} + 2x^3J^2_{n+1} - 2x^3J_{n+1}J_n\\ & = & x^3J^2_{n+1} +
x^3J^2_n - 2x^3J_{n+1}J_n + 2xJ_{n+3}(J_{n+1} + xJ_n) + 2x^2J^2_{n+2}
+ 2x^3J^2_{n+1} - 2x^3J_{n+1}J_n\\ & = & 2xJ_{n+3}J_{n+1} + x^3J^2_n
+ 2x^3J_{n+1}J_n + 2x^2J^2_{n+2} + 3x^3J^2_{n+1} - 4x^3J_{n+1}J_n\\
& = & 2xJ_{n+3}J_{n+1} + x^3J^2_n + 2x^2J_n(J_{n+2} + xJ_{n+1}) +
x(J_{n+3} - J_{n+2})^2 + + 2x^2J^2_{n+2} + 2x^3J^2_{n+1}\\
&& -~ 4x^3J_{n+1}J_n\\
& = & 2xJ_{n+3}J_{n+1} + x^3J^2_n + 2x^2J_{n+2}J_n + xJ^2_{n+3} +
2x^3J_{n+1}J_n + (2x^2 + x)J^2_{n+2} - 2xJ_{n+3}J_{n+2}\\
&& +~ 2x^3J^2_{n+1} - 4x^3J_{n+1}J_n.
\end{eqnarray*} \indent Then \begin{equation*}
S_1 + x^3S_2 = C + D + (x^2 + x)J^2_{n+2} - 2x^3J_{n+1}J_n + (2x^2 +
x)J^2_{n+2} - 2xJ_{n+3}J_{n+2},
\end{equation*} where \begin{eqnarray*}
C & = & (x + 1)(J^2_{n+3} + 2xJ_{n+3}J_{n+1}) + x^3J^2_{n+1}\\
& = & (x + 1)(J_{n+3} + xJ_{n+1})^2 - x^2J^2_{n+1}\\ & = & (x +
1)j^2_{n+2} - x^2J^2_{n+1};\\
D & = & (x^2 + x)J^2_{n+2} + x^3J^2_n + 2x^2J_{n+2}J_n\\
& = & (x^2 + x)(J_{n+2} + xJ_n)^2 - 2x^3J_{n+2}J_n - x^4J^2_n\\ &
= & x(x + 1)j^2_{n+1} - 2x^3J_{n+2}J_n - x^4J^2_n.
\end{eqnarray*} \indent Consequently, \begin{equation*}
S_1 + x^3S_2 = (x + 1)j^2_{n+2} + x(x + 1)j^2_{n+1} + E,
\end{equation*} where \begin{eqnarray*}
E & = & -2x^3J_{n+1}J_n - 2x^2J_{n+2}J_{n+1} - 2x^4J^2_n +
2x^2J^2_{n+2}\\
& = & - 2x^3J_n(J_{n+1} + xJ_n) + 2x^2J_{n+2}(J_{n+2} - J_{n+1})\\
& = & -2x^3J_{n+2}J_n + 2x^3J_{n+2}J_n\\ & = & 0.
\end{eqnarray*} \indent Thus \begin{equation*}
S_1 + x^3S_2 = (x + 1)j^2_{n+2} + x(x + 1)j^2_{n+1},
\end{equation*} as expected.
\end{proof}
\section{Acknowledgments}
The author would like to thank the
reviewer for his/her constructive suggestions for improving the quality
of exposition of the original version.
\begin{thebibliography}{99} \bibitem{alsina-nelsen}
C. Alsina and R. B. Nelsen, \textit{Charming Proofs: A Journey Into
Elegant Mathematics}, MAA, 2010.
\bibitem{almdeberhan-etal}
T. Amdeberhan, X. Chen, V. H. Moll, and B. E. Sagan,
Generalized Fibonacci polynomials and
Fibonomial coefficients, \textit{Ann. Comb}. \textbf{18} (2014),
541--562.
\bibitem{bicknell}
M. Bicknell, A primer for the Fibonacci numbers: Part VII,
\textit{Fibonacci Quart}. \textbf{8} (1970), 407--420.
\bibitem{florez-etal}
R. Fl{\'o}rez, N. McAnally, and A. Mukherjee,
Identities for the generalized Fibonacci
polynomial, \textit{Integers}, {\bf 18B} (2018), Article A2.
\bibitem{horadam1}
A. F. Horadam, Jacobsthal representation numbers, \textit{Fibonacci
Quart}. \textbf{34} (1996), 40--54.
\bibitem{horadam2}
A. F. Horadam, Jacobsthal representation polynomials, \textit{Fibonacci
Quart}. \textbf{35} (1997), 137--148.
\bibitem{horadam-mahon}
A. F. Horadam and Bro. J. M. Mahon, Pell and Pell-Lucas polynomials,
\textit{Fibonacci Quart}. \textbf{23} (1985), 7--20.
\bibitem{hould1}
H. W. Gould, Problem B-7, \textit{Fibonacci Quart}. \textbf{1}
(1963), 80.
\bibitem{koshy2}
T. Koshy, \textit{Discrete Mathematics with Applications}, Elsevier,
2004.
\bibitem{koshy3}
T. Koshy, \textit{Pell and Pell-Lucas Numbers with Applications},
Springer, 2014.
\bibitem{koshy4}
T. Koshy, Graph-theoretic models for the univariate Fibonacci family,
\textit{Fibonacci Quart}. \textbf{53} (2015), 135--146.
\bibitem{koshy0}
T. Koshy, Polynomial extensions of the Lucas and Ginsburg identities
revisited, \textit{Fibonacci Quart}. \textbf{55} (2017), 147--151.
\bibitem{koshy1}
T. Koshy, \textit{Fibonacci and Lucas Numbers with Applications},
Volume I, Second Edition, Wiley, 2018.
\bibitem{koshy5}
T. Koshy, \textit{Fibonacci and Lucas Numbers with Applications},
Volume II, Wiley, 2019.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}: Primary 05A19; Secondary 11B37, 11B39, 11Cxx.
\noindent \emph{Keywords: }
Fibonacci number, Lucas number, Pell number, Pell-Lucas number, Jacobsthal number,
Jacobsthal-Lucas number, $Q$-matrix, weight, weighted digraph,
weighted adjacency matrix, walk.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A000032},
\seqnum{A000045},
\seqnum{A000129},
\seqnum{A001045},
\seqnum{A002203}, and
\seqnum{A014551}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received June 1 2018; revised versions received August 24 2018;
February 24 2019; February 25 2019.
Published in {\it Journal of Integer Sequences}, May 22 2019.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}