<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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}}$; &amp; &amp; &amp; $l_n(x) = \alpha^n + \beta^n$;\\[0.15cm] 
      $J_n(x) = \displaystyle{\frac{u^n - v^n}{u - v}}$;                   &amp; &amp; &amp; $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 &amp; 1\\ 
          1 &amp; 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} &amp; f_n\\ 
                f_n &amp; 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 &amp; = &amp; (xg_{n+2} + g_{n+1})^2 + (g_{n+2} - xg_{n+1})^2\\ 
                     &amp; = &amp; (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 &amp; = &amp; x^2f^2_{n+2} + f^2_{n+1} + 2xf_{n+2}f_n\\ 
     &amp; = &amp; (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} &amp; = &amp; (xf_{n+3} + 2f_{n+2})^2\nonumber\\ 
                                                &amp; = &amp; (f_{n+4} + f_{n+2})^2\nonumber\\ 
                                                &amp; = &amp; l^2_{n+3}\label{equation03}\\ 
                                                &amp; = &amp; 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 &amp; = &amp; S_1 + S_2 + S_3 + S_4\\ 
     &amp; = &amp; x^2f^2_{n+3} + 4f^2_{n+2} + 4xf_{n+3}f_{n+2}\\ 
     &amp; = &amp; 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 &amp; = &amp; x^2f^2_{n+3}f_{n+1}  + xf_{n+3}f_n + xf_{n+2}f_{n+1} + f_{n+2}f_n\\ 
       &amp; = &amp; 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 &amp; = &amp; x^2f^2_{n+1} + 2xf_{n+1}f_n + f^2_n\\ 
       &amp; = &amp; f^2_{n+2}. 
\end{eqnarray*} 
 
Finally, let $v\in D$ and $w\in C$. The corresponding contribution is  
\begin{eqnarray*} 
   S_4 &amp; = &amp; x^2f_{n+3}f_{n+1}  + xf_{n+3}f_n + xf_{n+2}f_{n+1} + f_{n+2}f_n\\ 
       &amp; = &amp; 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 &amp; = &amp; x^2f^2_{n+3} + 4f^2_{n+2} + 4xf_{n+3}f_{n+2}\\ 
                         &amp; = &amp; 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},          &amp; {\rm if}~ g_n = f_n;\\ 
                          (x^2 + 4)f_{2n+1}, &amp; {\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 &amp; = &amp; (x^2 + 1)(g^2_{n+2} + g_{n+1}^2)\\ 
                     &amp; = &amp; \begin{cases} 
                              (x^2 + 1)f_{2n+3},          &amp; {\rm if}~ g_n = f_n;\\ 
                              (x^2 + 1)(x^2 + 4)f_{2n+3}, &amp; {\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} &amp; = &amp; 4x^2p^2_{n+3} + 4p^2_{n+2} + 8xp_{n+3}p_{n+2}\\ 
             &amp; = &amp; 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} &amp; = &amp; 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) &amp; = &amp; 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} &amp; = &amp; 3C^2_{n+2} + 6C^2_{n+1} - 8C^2_n;\nonumber\\ 
   j^2_{n+1} &amp; = &amp; 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 &amp; x\\ 1 &amp; 0
       \end{bmatrix}.
\end{equation*} Then \begin{equation*}
   M^n = \begin{bmatrix}
            J_{n+1}(x) &amp; xJ_n(x)\\
                J_n(x) &amp; 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 &amp; = &amp; J^2_{n+2}(x) + 2xJ_{n+2}(x)J_{n+1}(x) + x^2J^2_{n+1}(x)\\
     &amp; = &amp; 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)\\ &amp; = &amp; (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)]\\ &amp; = &amp; (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 &amp; = &amp; J^2_{n+4}(x) + x^2J^2_{n+2}(x) + x^3J^2_{n+1}(x);\\ B &amp; = &amp;
   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 &amp; = &amp; (J_{n+3} + xJ_{n+2})^2 + x^2J^2_{n+2} + x^3J^2_{n+1}\\
     &amp; = &amp; J^2_{n+3} + 2x^2J^2_{n+2} + 2xJ_{n+2}(J_{n+2} + xJ_{n+1}) +
     x^3J^2_{n+1}\\ &amp; = &amp; 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}\\ &amp; = &amp; 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})\\ &amp; = &amp; 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 &amp; = &amp; 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)\\
     &amp; = &amp; 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\\ &amp; = &amp; 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\\ &amp; = &amp; 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\\
     &amp; = &amp; 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}\\
         &amp;&amp; -~ 4x^3J_{n+1}J_n\\
     &amp; = &amp; 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}\\
         &amp;&amp; +~ 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 &amp; = &amp; (x + 1)(J^2_{n+3} + 2xJ_{n+3}J_{n+1}) + x^3J^2_{n+1}\\
     &amp; = &amp; (x + 1)(J_{n+3} + xJ_{n+1})^2 - x^2J^2_{n+1}\\ &amp; = &amp; (x +
     1)j^2_{n+2} - x^2J^2_{n+1};\\
   D &amp; = &amp; (x^2 + x)J^2_{n+2} + x^3J^2_n + 2x^2J_{n+2}J_n\\
     &amp; = &amp; (x^2 + x)(J_{n+2} + xJ_n)^2 - 2x^3J_{n+2}J_n - x^4J^2_n\\ &amp;
     = &amp; 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 &amp; = &amp; -2x^3J_{n+1}J_n - 2x^2J_{n+2}J_{n+1} - 2x^4J^2_n +
   2x^2J^2_{n+2}\\
     &amp; = &amp; - 2x^3J_n(J_{n+1} + xJ_n) + 2x^2J_{n+2}(J_{n+2} - J_{n+1})\\
     &amp; = &amp; -2x^3J_{n+2}J_n + 2x^3J_{n+2}J_n\\ &amp; = &amp; 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}

                                                                                

</pre></body></html>