\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{mathrsfs}
\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}{\rm \underline{#1}}}
\begin{document}
\begin{center}
\includegraphics[width=4in]{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
Convolutions of Sequences with Similar\\
\vskip .1in
Linear Recurrence Formulas
}
\vskip 1cm
\large
Greg Dresden\\
Washington \& Lee University \\
Lexington, VA 24450 \\ USA\\
\href{mailto:dresdeng@wlu.edu}{\tt dresdeng@wlu.edu} \\
\ \\
Michael Tulskikh\\
Columbia University\\
New York, NY 10027\\ USA\\
\href{mailto:tulskikhmichael@gmail.com}{\tt tulskikhmichael@gmail.com}\\
\end{center}
\vskip 0.2in
\begin{abstract}
We show that a collection of convolution formulas involving the Fibonacci,
Tribonacci, Pell, Jacobsthal, Narayana, and other number sequences can
all be derived from a single elegant formula so long as the sequences
follow certain mild requirements. We give many examples, both old and new.
\end{abstract}
\section{Introduction}
Let us dive right into some interesting convolution formulas.
From Szak\'{a}cs \cite[Corollary 2.4]{Szakacs} and two years later in Koshy and Griffiths \cite[equation (2.2)]{KoshyGriffiths} we have this lovely convolution formula that connects the Fibonacci numbers $F_n$
(\seqnum{A000045} in the OnLine Encyclopedia of Integer Sequences \cite{oeis}) with the seeminglyunrelated Jacobsthal numbers $J_n$ (\seqnum{A001045}),
\begin{equation}\label{last1.1}
\sum_{i=0}^n F_i J_{ni} = J_{n+1}  F_{n+1}.
\end{equation}
This formula can also be found at \seqnum{A094687}.
From Frontczak \cite[Theorem 2.1]{Frontczak} we have
another lovely formula, this one with the Fibonacci numbers and the Tribonacci numbers $T_n$ (\seqnum{A000073}) except that our Tribonacci numbers start with $T_0 =0, T_1 = 1, T_2 = 1$,
\begin{equation}\label{last1.2}
\sum_{i=0}^n F_i T_{ni} = T_{n+2}  F_{n+2}.
\end{equation}
The terms $T_{n+2}F_{n+2}$ appear at sequence
\seqnum{A000100}.
Dresden and Wang \cite{DW} noted the similarity between formulas \ref{last1.1} and \ref{last1.2}, and asked if there were other convolution formulas of this type. A bit of investigation reveals quite a few more, such as this next little gem that involves just the Fibonacci numbers,
\begin{equation}\label{F3nFn}
\sum_{i=0}^n F_{3i}F_{ni} =
\frac{1}{3} \left(F_{3n}  2F_n\right).
\end{equation}
The above formula can be found at
\seqnum{A049674}.
Here is an adorable equation that connects the Narayana numbers $N_n$
(\seqnum{A000930}) and
the triangular numbers $t_n$
(\seqnum{A000217}),
\begin{equation}\label{tnNn}
\sum_{i=1}^n N_{3i1}t_{ni} =
N_{3n1}  t_n.
\end{equation}
We believe this formula is new; we added it to the OEIS at \seqnum{A350498}.
This next one gives us another surprising connection (first proved by Szak\'{a}cs
\cite[Corollary 2.7]{Szakacs}), this time between the Jacobsthal numbers and Pell numbers (\seqnum{A000129}),
\begin{equation}\label{JP}
\sum_{i=0}^n J_{i}P_{ni} =
\frac{1}{2}\left(P_{n+1} + P_{n}  J_{n+2}\right).
\end{equation}
Here are some formulas with Fibonacci numbers and
with powers that all seem rather similar:
\begin{align}
\sum_{i=0}^n F_{i}\, 1^{ni} &=
F_{n+2}  1\cdot 1^{n+1}\label{fib1}\\
\sum_{i=0}^n F_{2i}\, 3^{ni} &=
1\cdot 3^{n+1}  F_{2(n+2)}\label{fib2}\\
\sum_{i=0}^n F_{3i}\, 4^{ni} &=
F_{3(n+2)}  2\cdot 4^{n+1}.\label{fib3}\\
\intertext{The general rule is}
\sum_{i=0}^n F_{ki}\, (L_k)^{ni} &= (1)^{k} \left(F_k\cdot (L_k)^{n+1}  F_{k(n+2)} \right).\label{fibgen}
\end{align}
It should not come as a surprise that we can play a similar game with the Pell numbers:
\begin{align}
\sum_{i=0}^n P_{i}\, 2^{ni} &=
P_{n+2}  1\cdot 2^{n+1}\label{pell1}\\
\sum_{i=0}^n P_{2i}\, 6^{ni} &=
2\cdot 6^{n+1}  P_{2(n+2)}\label{pell2}\\
\sum_{i=0}^n P_{3i}\, 14^{ni} &=
P_{3(n+2)}  5\cdot 14^{n+1}.\label{pell3}\\
\intertext{The general rule for these is}
\sum_{i=0}^n P_{ki}\, (Q_k)^{ni} &= (1)^{k} \left( P_k\cdot (Q_k)^{n+1}  P_{k(n+2)}\right), \label{pellgen}
\end{align}
where the $Q_n$'s are the PellLucas numbers
\href{https://oeis.org/A002203}{A002203}.
For $k$ odd, these Fibonacci and Pell formulas can also be derived from a combinatorial formula by
Benjamin and Quinn \cite[Identity 99]{BQ}.
At this point, it is probably not surprising
that we can also find convolution formulas for Fibonacci numbers and Pell numbers
together, such as the wellknown formula
\begin{align}
\sum_{i=0}^n F_i P_{ni} &= P_n  F_n\label{FibPell11}\\
\intertext{and the less familiar formula}
\sum_{i=0}^n F_{3i} P_{ni} &= F_{3n}/2  P_n. \label{FibPell13}
\end{align}
With not much effort, we can prove a general formula for the Fibonacci and Pell numbers
involving the Lucas numbers $L_n$ (\seqnum{A000032}) and the PellLucas numbers $Q_n$,
\begin{equation}\label{FibPell}
\sum_{i=0}^n F_{ki} P_{m(ni)} =
\frac{1}{L_k  Q_m}
\left( F_{kn} P_m  F_k P_{m n}\right), \qquad \mbox{for $k,m$ same parity.}
\end{equation}
(It takes a bit more effort to show that $L_k = Q_m$ only for $k=0$ and $m=0,1$; this follows from a procedure of Alekseyev \cite[eq.\ (10)]{Alekseyev} which gives us the Diophantine system $x^25y^2 = \pm 4$
and $x^2  8z^2 = \pm 4$ which by a bit of algebra and the method of infinite descent gives only $(x,y,z) = (2,0,0)$ as the single nonnegative solution and hence $L_k=Q_m$ only when both equal 2.)
Along the lines of equation (\ref{FibPell}),
we have another general convolution formula,
this one just involving the Fibonacci numbers which is a nice generalization
of equation (\ref{F3nFn}) from earlier:
\begin{equation}\label{FibFib}
\sum_{i=0}^n F_{ki} F_{m(ni)} =
\frac{1}{L_k  L_m}
\left( F_{kn} F_m  F_k F_{m n}\right), \qquad \mbox{for $k \not= m$ but of same parity.}
\end{equation}
It should not come as a surprise to learn that we have a version of equation (\ref{FibFib}) but for the Pell numbers in place of the Fibonacci numbers,
\begin{equation}\label{PellPell}
\sum_{i=0}^n P_{ki} P_{m(ni)} =
\frac{1}{Q_k  Q_m}
\left( P_{kn} P_m  P_k P_{m n}\right), \qquad \mbox{for $k \not= m$ but of same parity.}
\end{equation}
We note that for $k,m$ both odd, then equations (\ref{FibPell}), (\ref{FibFib}), and (\ref{PellPell}) can all be
derived from a theorem of Bramham and Griffiths \cite[Theorem 3.1]{BG}, but we believe the extension to when $k,m$ are both even is original to this paper.
Finally, here is a rather complicated formula that does not seem related to the others (but as we will reveal later it is indeed in the same family),
\begin{equation}\label{triple}
\sum_{i=0}^{2n} (1)^i F_i F_{i+1} F_{2ni1}
\ = \
\frac{2}{3}\sum_{i=0}^{n} F_{2i1} F_{4(ni)}
\ = \
\frac{1}{2}\left(F_{4n+1}  F_{2n1}\right).
\end{equation}
This formula is completely new, and it illustrates how our approach can produce novel results.
The righthand sides of all these equations (\ref{last1.1}) through (\ref{triple})
exhibit a striking pattern. Is there a single
theorem that will allow us to derive all these formulas?
Of course there is, and we give two proofs of this theorem, one using generating functions and the other using a tiling argument.
Our work follows closely the tiling techniques studied by Benjamin and Quinn \cite{BQ} and elaborated by Bramham and Griffiths \cite{BG}, and also the generating function techniques illustrated by Wilf \cite{Wilf}.
We should note that in general, most convolution formulas are not as elegant as the
ones seen above. For example,
the convolution of $F_n$ with itself
is the rather unpleasant $((n1)F_n + 2nF_{n1})/5$, and for the convolution of $(F_n)^2$ with $F_{3n}$ we have the quite unsavory equation
\[
\sum_{i=0}^{n}(F_{i})^2 F_{3(ni)} = \frac{1}{11}\Big(
F_{3n} + L_{3 n + 1}  5 (F_n)^2 
(F_{n + 1})^2  3 F_n F_{n+1}
\Big).
\]
By comparison, our convolution formulas
(\ref{last1.1}) through (\ref{triple})
are delightfully simple and graceful, with all but equation (\ref{JP}) involving just two terms. Furthermore, they all derive from a single theorem, as we now explain.
\section{Definitions and the main theorem}
To begin, we suppose that
$(a_n)_{n \geq 0}$ is a linear recurrence sequence with
initial values $a_n = 0$ for $n \leq 0$ and $a_1 = 1$, and with
recurrence formula
\begin{equation}\label{an.definition}
a_n = c_1 a_{n1} + c_2 a_{n2} + \cdots + c_L a_{nL}
\end{equation}
for $n > 1$, with not all $c_i$ equal to zero. We say that
this sequence has {\em signature} $\{c_1, c_2, \dots, c_L\}$ and has {\em order} $L$. It is not hard to show that this sequence
$(a_n)$ has generating function $A(x)$, where
\begin{equation}\label{gfA}
A(x) = \sum_{n=0}^{\infty} a_n x^n = \frac{x}{1  c_1 x  c_2 x^2  \cdots  c_L x^L}.
\end{equation}
As an example, the Fibonacci sequence $(F_n)_{n \geq 0}$ has signature $\{1,1\}$, order 2, and generating function $x/(1xx^2)$.
Next, we suppose that $(b_n)$ is another linear
recurrence sequence
with the same initial values as $(a_n)$ and whose signature is
$\{c_1, c_2, \dots, (c_j+d_j), \dots, c_L\}$, differing from the signature for $(a_n)$ only in position $j$ by a nonzero amount $d_j$. It is convenient but not necessary to assume that $d_j>0$. The sequence $(b_n)$ has generating function $B(x)$, where
\begin{equation}\label{gfB}
B(x) = \sum_{n=0}^{\infty} b_n x^n = \frac{x}{1  c_1 x  c_2 x^2  \cdots  (c_j + d_j)x^j  \cdots  c_L x^L}.
\end{equation}
With all this in mind, we have the following theorem.
\begin{theorem}\label{convolution_theorem}
For any two sequences $(a_n)$ and $(b_n)$ as defined above with initial values of $0$ for $n \leq 0$ and $1$ for $n=1$ and whose recurrence signatures differ in only the $j^{th}$ term by an amount $d_j$, we have the convolution formula
\begin{equation}\label{convolution_formula}
\displaystyle\sum_{i=0}^n{a_i}{b_{ni}} \ = \
\displaystyle\sum_{i=0}^n{b_i}{a_{ni}} \ = \ \frac{1}{d_j}\Big(b_{n+j1}  a_{n+j1}\Big).
\end{equation}
\end{theorem}
We note that Szak\'{a}cs \cite[Theorem 2.1]{Szakacs} covers
our Theorem \ref{convolution_theorem} but only
for secondorder linear recurrences. In the next two sections, we present two separate proofs of
our theorem.
\section{Proving the convolution theorem using generating functions}
Recall that we have
\begin{align*}
A(x) &= \sum_{n=0}^{\infty} a_n x^n = \frac{x}{1  c_1 x  c_2 x^2  \cdots  c_L x^L}, \\
B(x) &= \sum_{n=0}^{\infty} b_n x^n = \frac{x}{1  c_1 x  c_2 x^2  \cdots  (c_j + d_j)x^j  \cdots  c_L x^L}.
\end{align*}
A bit of algebra (and a common denominator) reveals that
\[
B(x)  A(x) \ = \ d_j x^{j1} A(x)B(x),
\]
which we simplify to
\begin{equation}\label{AxBx}
A(x)B(x) \ = \ \frac{1}{d_j} \left( \frac{B(x)}{x^{j1}}  \frac{A(x)}{x^{j1}}\right).
\end{equation}
Here we make two crucial observations.
First, we note that $A(x)B(x)$ is the generating function for
the convolution
sequence $\left(\sum_{i=0}^n a_i b_{ni} \right)_{n \geq 0}$ which if we replace $i$ with $ni$ gives us the identical expression
$\left(\sum_{i=0}^n b_i a_{ni} \right)_{n \geq 0}$,
and second, we
note that dividing a generating function by a power of $x$ shifts the index in the positive direction by that same power.
In other words,
\[
\frac{A(x)}{x^{j1}} \ = \ \sum_{n=(j1)}^{\infty} a_{n+(j1)} x^n,
\]
with a similar statement for $B(x)/x^{j1}$.
Hence, equation (\ref{AxBx}) can be rewritten in terms of coefficients as
\[
\sum_{i=0}^n a_i b_{ni} = \frac{1}{d_j} \Big( b_{n+j1} a_{n+j1}\Big) \qquad \mbox{for all $n \geq 0$}.
\]
Therefore, we have proved Theorem \ref{convolution_theorem}.
\section{Proving the convolution theorem using tilings}
Note that tiling proofs for convolution formulas are quite common. Equation (\ref{fib1}) is the very first identity in Benjamin and Quinn's book \cite{BQ}. Versions of Theorem \ref{convolution_theorem} for degreetwo recurrence sequences can be found in that same book \cite[Identities 99, 100]{BQ} and
also in an article by Bramham and Griffiths \cite[Theorems 3.1, 3.2]{BG}, and a limited version for degree three also appears in Benjamin and Quinn \cite[p.\ 47, Ex.\ 4]{BQ}.
To begin our tiling proof, we turn once more to Benjamin and Quinn \cite[Section 3.1]{BQ},
where we find the following theorem:
\begin{theorem}[Benjamin, Quinn]\label{BQ_theorem}
Let $c_1, c_2, \dots c_L$ be nonnegative integers, and let $a_0, a_1, \dots$ be the sequence of numbers
defined by the recurrence
$$
a_n = c_1 a_{n1} + c_2 a_{n2} + \cdots + c_L a_{nL}
$$
with
``ideal" initial conditions $a_1 = 1$ and $a_n = 0$ for $n \leq 0$. Then for all $n \geq 1$,
$a_n$ counts the {\bf colored tilings} of
a board of length $n1$, using tiles of length
at most $L$, where for $1 \leq i \leq L$ each tile
of length $i$ is assigned one of $c_i$ colors.
\end{theorem}
With this in mind, we can now prove Theorem
\ref{convolution_theorem} for two sequences
$(a_n)$ and $(b_n)$ in the case that all their
associated constants are nonnegative integers. (Benjamin and Quinn \cite[Section 3.5]{BQ} also discussed how to extend tiling proofs to deal with complex coefficients, but we will leave that as an exercise for the reader.)
From Theorem \ref{BQ_theorem} and our definitions of $(a_n)$ and $(b_n)$ we know that
$a_n$ measures the number of ways to tile
a board of length $n1$ and that
$b_n$ measures the same except that the tiles of length
$j$ (henceforth called {\em $j$minos}) have an additional $d_j$ colors.
We now consider a
board of length $n+j2$ and we ask, how many ways are there to tile this board with our colored tiles of
length $1$ through $L$, and using at least one of the ``additional" $d_j$ colors for the $j$mino?
On the one hand, by Theorem
\ref{BQ_theorem} there are $b_{n+j1}$ ways using all $c_j + d_j$ colors for the $j$mino and $a_{n+j1}$ ways that do not use the additional
$d_j$ colors, so their difference $b_{n+j1}  a_{n+j1}$ gives us the desired count.
On the other hand, we can condition on the location of the
last $j$mino that uses one of the additional $d_j$ colors (we are given that there must be at least one such $j$mino). We can think of this $j$mino as stretching from position $i$ to position $i+j1$ on our board of length $n+j2$ as $i$ ranges from 1 to $n1$; see Figure \ref{f1Label}.
\begin{figure}[h]
\centering
\includegraphics[scale=0.6]{dresdenfig12b.png}
\caption{Conditioning on the location of the last $j$mino.}
\label{f1Label}
\end{figure}
At each position of the
$j$mino, there would be $b_{i}$ possible tilings for the board of length $i1$ to the left
of the $j$mino (these tilings could use one of these ``additional" $d_j$ colors) and $a_{ni}$ possible tilings for the board of length $ni1$ to the right (these tilings would not use one of the additional colors), and of course the $j$mino itself has $d_j$ possible colors. This gives us $ b_{i}\cdot d_j \cdot a_{ni}$ tilings for this configuration, and summing over $i$ from $1$ to $n1$ gives
\[
d_j \cdot \sum_{i=1}^{n1} b_{i} a_{ni},
\]
and since $a_0 = b_0 = 0$ by our initial conditions, we can extend the sum from $0$ to $n$ without changing its value, giving us
$$
d_j \cdot \sum_{i=0}^{n} b_{i} a_{ni}
$$
total number of tilings. Comparing this with our expression $b_{n+j1}  a_{n+j1}$ from earlier will give us our desired statement.
\section{Examples}
We now show
how all our equations (\ref{last1.1}) through (\ref{triple})
follow from Theorem \ref{convolution_theorem}.
For our first equation (\ref{last1.1}), we recall that the generating functions for
the Fibonacci numbers and Jacobsthal numbers
are
\begin{align*}
\sum_{n=0}^\infty{F_n x^n} &= \frac{x}{1xx^2}\\
\sum_{n=0}^\infty{J_n x^n} &= \frac{x}{1x2x^2},
\end{align*}
and so they have signatures $\{1,1\}$ and $\{1,2\}$ respectively. We can now apply
Theorem \ref{convolution_theorem} with
$a_n = F_n$, $b_n = J_n$, $j=2$, and $d_j = 1$
to obtain
$$
\sum_{i=0}^{n}F_iJ_{ni} = J_{n+1}  F_{n+1},
$$
which is our equation
(\ref{last1.1}).
Moving on to equation (\ref{last1.2}) with the Fibonacci numbers
and Tribonacci numbers, we recall that our definition of the Tribonacci numbers has them starting with $T_0=0$ and $T_1 = T_2 = 1$ so as to match the requirements for initial conditions in Theorem \ref{convolution_theorem}. These two sequences have signature
$\{1,1\}$ and $\{1,1,1\}$ respectively, and so
we use $a_n = F_n$
and $b_n = T_n$, which means $j=3$ and $d_j=1$ and so
equation (\ref{convolution_formula}) of Theorem \ref{convolution_theorem} gives us
$$
\sum_{i=0}^{n}T_iF_{ni} = T_{n+2}  F_{n+2},
$$
which is a perfect match for our equation (\ref{last1.2}).
For equation (\ref{F3nFn}) on two Fibonacci sequences, the sequence
$(F_{3n})_{n \geq 0}$ presents a bit of a problem since
its generating function is
\begin{align*} \displaystyle\sum_{n=0}^\infty{F_{3n}x^n} &= \frac{2x}{14xx^2}\\
\intertext{and the numerator does not match the numerators in equations (\ref{gfA}) and (\ref{gfB}). We simply divide by 2 to obtain}
\displaystyle\sum_{n=0}^\infty{(F_{3n}/2)x^n} &= \frac{x}{14xx^2},
\end{align*}
and so we now use
$a_n = F_n$, $b_n = F_{3n}/2$, $j=1$, and $d_j = 3$
and so Theorem \ref{convolution_theorem} gives us
$$
\displaystyle\sum_{i=0}^{n}(F_{3i}/2)F_{ni} = \frac{1}{3}\left((F_{3n}/2)  F_n\right),
$$
and we simply multiply through by $2$ to obtain
equation (\ref{F3nFn}). We will use this technique again in what follows, and in particular when we prove the general Fibonacci
convolution formula (\ref{FibFib}).
To derive equation (\ref{tnNn}) involving the triangular numbers and Narayana's numbers, we begin with two generating functions,
\begin{equation}
\frac{x}{(1x)^3} = \frac{x}{13x+3x^2x^3}
\qquad \mbox{and} \qquad
\frac{x}{14x+3x^2x^3}.
\end{equation}
The first generating function gives us the triangular numbers $0, 1, 3, 6, 10, 15, \dots$ from \seqnum{A000217}. The second gives us
the sequence $0, 1, 4, 13, 41, 129$ which (aside from the first term)
is a trisection of Narayana's numbers as seen at
\seqnum{A052529}. To be precise, if we let
$a_n$ and $b_n$ represent these two sequences then $a_n = t_n$ for all $n$, and $b_n = N_{3n1}$ for $n>0$ (with $b_0=0$). We can now apply Theorem \ref{convolution_theorem} with $j=1$ and $d_j=1$, dropping the
first term $b_0 a_n$ from the sum, to
obtain
\begin{equation}
\displaystyle\sum_{i=1}^{n} b_i a_{ni} = b_n  a_n,
\end{equation}
and we replace $a_n$ and $b_n$ with $t_n$
and $N_{3n1}$ to obtain our
equation (\ref{tnNn}).
To obtain equation (\ref{JP}) with
the Jacobsthal and the Pell sequences, we begin with the Lichtenberg numbers $(\ell_n)_{n\geq 0}$
(\seqnum{A000975}) as discussed by
Hinz \cite{Hinz}. These have generating function
\begin{equation}
\displaystyle\sum_{n=0}^\infty{\ell_n x^n} = \frac{x}{12xx^2+2x^3}
\end{equation}
and so when we look at
\[
\sum_{i=0}^{n} \ell_i P_{ni}
\]
we see that we can apply Theorem \ref{convolution_theorem} if we let
$a_n = \ell_n$, $b_n = P_n$, $j=3$, and $d_j = 2$, giving us
\begin{equation}\label{26}
\sum_{i=0}^{n} \ell_i P_{ni} =
\frac{1}{2}\left( P_{n+2}  \ell_{n+2}\right).
\end{equation}
From \seqnum{A000975} we learn that
$\ell_n = J_{n+1}  \pi_{n+1}$ where $\pi_n$ is $n \bmod 2$, the parity of $n$.
We substitute this into equation (\ref{26}) to obtain
\begin{equation}\label{27}
\sum_{i=0}^{n} (J_{i+1}  \pi_{i+1})P_{ni} =
\frac{1}{2}\left( P_{n+2}  J_{n+3} + \pi_{n+3}\right).
\end{equation}
If we separate the sum on the left, the above equation becomes
\begin{equation}\label{28}
\sum_{i=0}^{n} J_{i+1} P_{ni} \  \
(P_n + P_{n2} + P_{n4} + \cdots) =
\frac{1}{2}\left( P_{n+2}  J_{n+3} + \pi_{n+3}\right).
\end{equation}
From an article by Koshy and Pell \cite[Section 10.2]{KoshyPell}
we learn that $(P_n + P_{n2} + P_{n4} + \cdots)$
equals $(P_{n+1}  \pi_{n+1})/2$, and so moving this over to the right of equation (\ref{28}) gives us
\begin{equation}\label{29}
\sum_{i=0}^{n} J_{i+1} P_{ni} =
\frac{1}{2}\left( P_{n+2}  J_{n+3} + \pi_{n+3} + P_{n+1}  \pi_{n+1} \right),
\end{equation}
and since $\pi_{n+3} = \pi_{n+1}$ then all this simplifies to
\begin{equation}\label{almostJP}
\sum_{i=0}^{n} J_{i+1} P_{ni} =
\frac{1}{2}\left( P_{n+2} + P_{n+1}  J_{n+3} \right).
\end{equation}
The expression on the left is $J_1 P_n + J_2 P_{n1} + \cdots + J_{n+1} P_0$. Since $J_0 =0$ we can add
$J_0 P_{n+1}$ in front without changing the value, giving us $\sum_{i=0}^{n+1} J_i P_{n+1i}$ on the left of
equation (\ref{almostJP}). We now replace all $n$'s with $n1$'s in (\ref{almostJP}) to obtain
\begin{equation}\label{almostJP2}
\sum_{i=0}^{n} J_{i} P_{ni} =
\frac{1}{2}\left( P_{n+1} + P_{n}  J_{n+2} \right),
\end{equation}
which is equation (\ref{JP}).
Moving on to equations
(\ref{fib1}) through
(\ref{fibgen}) on the convolution of powers and Fibonacci numbers, we need
the identity
\[
F_{k (n+2)} = L_k F_{k(n+1)}  (1)^k F_{kn}
\]
which Koshy \cite[p.\ 112]{KoshyFib} credits to Ruggles \cite{Ruggles}. This identity, along with the initial values of
$F_{k0}= 0$ and $F_{k1} = F_k$,
tells us that the generating function for
$(F_{kn})_{n \geq 0}$ is
\begin{equation}\label{Fibgf}
\sum_{n=0}^{\infty} F_{kn}x^n = \frac{F_k x}{1  L_k x + (1)^k x^2}.
\end{equation}
As for the sequence
$0, 1, L_k, (L_k)^2, (L_k)^3, \dots$, this has generating function $x/(1 L_k x)$, which means to apply Theorem \ref{convolution_theorem} we would have to use $b_0=0$ and $b_n = (L_k)^{n1}$ to
have $\sum_{n=0}^\infty b_n x^n$ match the coefficients of $x/(1L_k x)$.
For $a_n$ we let $a_n = F_{kn}/F_k$,
and then we assign $j=2$ and $d_j = (1)^k$ to obtain from
Theorem \ref{convolution_theorem} the intermediate step
\begin{equation}\label{snowday1}
\sum_{i=0}^{n} (F_{ki}/F_k) b_{ni} =
\frac{1}{(1)^k}\left( b_{n+1} 
(F_{k(n+1)}/F_k) \right).
\end{equation}
Since $b_0=0$ and $b_n = (L_k)^{n1}$ for $n>0$, the sum on the left of equation (\ref{snowday1}) doesn't have an $n$th term and so we really have
\begin{equation}\label{snowday2}
\sum_{i=0}^{n1} (F_{ki}/F_k) (L_k)^{n1i} =
\frac{1}{(1)^k}\left( (L_k)^{n} 
(F_{k(n+1)}/F_k) \right).
\end{equation}
We now replace $n$ with $n+1$, multiply both sides by $F_k$, and rewrite $1/(1)^k$ as just $(1)^k$, to obtain
\[
\sum_{i=0}^n F_{ki}\, (L_k)^{ni} = (1)^{k} \left(F_k\cdot (L_k)^{n+1}  F_{k(n+2)} \right)
\]
which is our desired equation (\ref{fibgen}), and this covers
(\ref{fib1}) through (\ref{fib3})
by replacing $k$ with $1, 2$, and $3$ respectively.
As for equations
(\ref{pell1}) through
(\ref{pellgen}) on powers and Pell numbers, we need
the identity
\[
P_{k (n+2)} = Q_k P_{k(n+1)}  (1)^k P_{kn}
\]
which can be obtained from Koshy's book on Pell numbers \cite[(7.20)]{KoshyPell} although Koshy's definition of $Q_n$ is slightly different from ours.
This identity, along with the initial values of
$P_{k0}= 0$ and $P_{k1} = P_k$,
tells us that the generating function for
$(P_{kn})_{n \geq 0}$ is
\begin{equation}\label{Pellgf}
\sum_{n=0}^{\infty} P_{kn}x^n = \frac{P_k x}{1  Q_k x + (1)^k x^2}.
\end{equation}
From here, the procedure is identical to the one before, except
that here we use
$P_{kn}/P_k$ instead of $F_{kn}/F_k$
and we use
$Q_k$ in place of $L_k$.
This gives us equation (\ref{pellgen}), which covers
(\ref{pell1}) through (\ref{pell3})
by replacing $k$ with $1, 2$, and $3$ respectively.
At this point, we have already done most of the work to establish equation (\ref{FibPell}) on the convolution of Fibonacci numbers and Pell numbers. Thanks to equations
(\ref{Fibgf}) and (\ref{Pellgf}), we know that the signature for
$\left(F_{kn}/F_k\right)_{n \geq 0}$ is
$\{L_k,(1)^k\}$
and for
$\left(P_{m n}/P_m\right)_{n \geq 0}$ is
$\{Q_m,(1)^m\}$. So long as $k$ and $m$ have the same parity, we can apply Theorem \ref{convolution_theorem} with
$a_n = P_{m n}/P_m$,
$b_n = F_{kn}/F_k$, $j=1$, and $d_j = L_k  Q_m$. After multiplying both sides by $F_k \cdot Q_m$, we have our formula
(\ref{FibPell}), which will then give us
(\ref{FibPell11}) and
(\ref{FibPell13}) with appropriate choices for $k$ and $m$.
Moving on, let us discuss equation (\ref{FibFib}) on the convolution of two Fibonacci sequences. From our discussion earlier, we
know that the signature for
$\left(F_{kn}/F_k\right)_{n \geq 0}$ is
$\{L_k,(1)^k\}$
and likewise
for $\left(F_{mn}/F_m\right)_{n \geq 0}$ it is
$\{L_m,(1)^m\}$. So long as $k \not= m$ have the same parity, we can use
Theorem \ref{convolution_theorem}
with $j=1$,
$a_n = F_{m n}/F_m$,
$b_n = F_{kn}/F_k$,
and $d_j = L_k  L_m$ to obtain
equation (\ref{FibFib}). The identical
technique applies to equation (\ref{PellPell}) with the convolution of two Pell sequences and so we will not
elaborate further on that.
Finally, we will derive equation (\ref{triple}), which we repeat here:
\begin{equation}\label{triple2}
\sum_{i=0}^{2n}
(1)^i F_i F_{i+1} F_{2ni1}
\ = \
\frac{2}{3}\sum_{i=0}^{n} F_{2i1} F_{4(ni)}
\ = \
\frac{1}{2}\left(F_{4n+1}  F_{2n1}\right).
\end{equation}
We begin with the sum on the far left.
We note that if we let
$a_n = (1)^{n1}F_{n1} + 1$
and
$b_n = F_nF_{n+1}$
then
the two sequences have generating functions
$x/(12x^2 + x^3)$
and
$x/(12x2x^2+x^3)$ respectively, so we can
apply Theorem \ref{convolution_theorem} with
$j=1$ and $d_j=2$ to obtain
\begin{equation}\label{triple3}
\sum_{i=0}^{n} F_i F_{i+1} \left( (1)^{ni1}F_{ni1} + 1\right)
= \frac{1}{2}\left( F_n F_{n+1} 
((1)^{n1}F_{n1} + 1)
\right).
\end{equation}
We split up the sum on the left, and replace all $n$'s with $2n$'s, to get
\begin{equation}\label{triple4}
\sum_{i=0}^{2n} (1)^{i+1} F_i F_{i+1} F_{2ni1}
\ + \ \sum_{i=0}^{2n} F_i F_{i+1}
\ = \ \frac{1}{2}\left( F_{2n} F_{2n+1} +
F_{2n1}  1
\right).
\end{equation}
Next, from Koshy \cite[p.\ 109]{KoshyFib} we learn that $\sum_{i=0}^{2n} F_i F_{i+1}$ equals
$F_{2n+1}^2  1$, so moving that over to the right we have
\begin{equation}\label{triple5}
\sum_{i=0}^{2n} (1)^{i+1} F_i F_{i+1} F_{2ni1}
\ = \ \frac{1}{2}\left( F_{2n} F_{2n+1} +
F_{2n1}  1  2F_{2n+1}^2 + 2
\right),
\end{equation}
and after some tedious calculations the righthand side simplifies to
$\left( F_{2n1}  F_{4n+1} \right)/2$, and so after multiplying everything by $1$ we obtain our desired formula.
For the sum in the middle of equation (\ref{triple2}),
we note that $F_{2i1} = F_{2(i+1)}  2 F_{2i}$ so we
cam split up this middle sum as
\begin{equation}
\frac{2}{3}\sum_{i=0}^{n} F_{2i1} F_{4(ni)}
\ = \
\frac{2}{3}
\sum_{i=0}^{n} F_{2(i+1)} F_{4(ni)} 
\frac{4}{3}\sum_{i=0}^{n} F_{2i} F_{4(ni)}.
\end{equation}
The second sum on the right matches perfectly with
equation (\ref{FibFib}), allowing us to rewrite the above equation as
\begin{equation}\label{43}
\frac{2}{3}\sum_{i=0}^{n} F_{2i1} F_{4(ni)}
\ = \
\frac{2}{3}
\sum_{i=0}^{n} F_{2(i+1)} F_{4(ni)} 
\frac{1}{3}\left( F_{4n}  3 F_{2n}\right),
\end{equation}
and for the first sum on the right, we first reindex the sum (replacing $i$ with $i1$) to get
$(2/3)\sum_{i=1}^{n+1} F_{2i} F_{4(n+1i)}$ and then
since $F_{2\cdot0} = 0$ we can change the starting value from $i=1$ to $i=0$ giving us
$(2/3)\sum_{i=0}^{n+1} F_{2i} F_{4(n+1i)}$ and this matches again with equation (\ref{FibFib}) but using $n+1$ instead of $n$, giving us $(1/6)\left( F_{4(n+1)}  3 F_{2(n+1)}\right)$. Thus, equation (\ref{43}) becomes
\begin{equation}\label{44}
\frac{2}{3}\sum_{i=0}^{n} F_{2i1} F_{4(ni)}
\ = \
\frac{1}{6}\left( F_{4(n+1)}  3 F_{2(n+1)}\right)

\frac{1}{3}\left( F_{4n}  3 F_{2n}\right),
\end{equation}
and after combining terms we have
\begin{equation}\label{45}
\frac{2}{3}\sum_{i=0}^{n} F_{2i1} F_{4(ni)}
\ = \
\frac{1}{6}\Big( \left(F_{4n+4}  2F_{4n}\right)
 3\left(F_{2n+2}  2F_{2n}\right) \Big).
\end{equation}
Since $F_{4n+4}  2F_{4n} = 3F_{4n+1}$ and
$F_{2n+2}  2F_{2n} = F_{2n1}$, we get
\begin{equation}\label{46}
\frac{2}{3}\sum_{i=0}^{n} F_{2i1} F_{4(ni)}
\ = \
\frac{1}{6}\Big( 3F_{4n+1}
 3F_{2n1}\Big)
\ = \ \frac{1}{2}\left( F_{4n+1}
 F_{2n1}\right),
\end{equation}
which gives us the second part of equation
(\ref{triple2}), as desired.
\section{Conclusion}
What other ``universal convolution" formulas can we find? As we noted earlier,
Szak\'{a}cs has a version of our Theorem \ref{convolution_theorem} that
applies to ordertwo recurrences with completely different signatures; the formulas are rather complicated when done in
such generality. Dresden and Wang \cite{DW} have a surprisingly simple universal convolution formula that applies to Fibonaccitype and Lucastype sequences with the same signatures but different initial values, as follows:
\begin{theorem}[Dresden, Wang]
For a given Fibonaccitype sequence $(\mathcal{F}_n^{(k)})_{n \geq 0}$ and companion Lucastype sequence $(\mathcal{L}_n^{(k)})_{n \geq 0}$ which count the number of ways to tile a strip and a bracelet respectively with the same collection of singlecolor tiles of lengths $1$ through $k$, we have
\begin{equation*}
\sum_{i=0}^{n1} \mathcal{F}_i^{(k)} \mathcal{L}_{ni}^{(k)} \ = \ (n1)\mathcal{F}_n^{(k)}.
\end{equation*}
\end{theorem}
Going back to our Theorem \ref{convolution_theorem}, there are plenty of additional convolutions that we could write down. For example, the Tripell nuumbers (\seqnum{A077939}), the Tribonacci numbers,
the Padovan numbers (\seqnum{A000931}), and
the sum of every other Tribonacci number
(\seqnum{A113300})
have signatures $\{2,1,1\}$, $\{1,1,1\}$,
$\{0,1,1\}$ and $\{3,1,1\}$ respectively, and so it would be easy to write down convolution formulas for these numbers.
Likewise, the Tribonacci numbers and the Tetranacci numbers
(\seqnum{A000078}) have signatures $\{1,1,1\}$ and $\{1,1,1,1\}$ and so they too would have an elegant convolution formula.
We also mention the LucasLehmer sequence
\seqnum{A107920} with signature $\{1,2\}$ that
can be matched to the Fibonacci numbers (signature $\{1,1\}$), the Jacobsthal numbers
(signature $\{1,2\}$), and the Mersenne numbers $2^n1$
(signature $\{3,2\}$).
We finish with one last example along these lines.
If we define $a_n$ as $F_{n/2}F_{n/2 + 1}$ for $n$ even,
and $(F_{(n+1)/2})^2$ for $n$ odd, then $(a_n)_{n \geq 0}$
is \seqnum{A006498} with indexing offset by 1. We then define $U_n$ to be the Tetranacci
numbers with indexing offset by 2, so that $U_n =0$ for $n \leq 0$ and $U_1 = 1$. These two sequences have signatures $\{1, 0,1,1\}$ and $\{1,1,1,1\}$ respectively. Then, Theorem \ref{convolution_theorem} with $2n+1$ in place of $n$ tells us that
\begin{equation}
\sum_{i=0}^{2n+1} a_{i} U_{2n+1i} \ = \
U_{2n+2}  a_{2n+2}.
\end{equation}
Using our definition of $a_n$, and splitting up the sum on the left into two sums over even indices and odd indices respectively that we then reindex, we obtain this fascinating relationship between the Fibonacci numbers and the Tetranacci numbers,
\begin{equation}
\sum_{i=0}^{n} F_i F_{i+1} U_{2n2i+1}
+
\sum_{i=0}^{n} (F_{i+1})^2 U_{2n2i}
\ = \
U_{2n+2}  F_{n+1}F_{n+2}.
\end{equation}
We can only imagine that there are many other interesting convolution formulas just waiting to be found.
\begin{thebibliography}{99}
\bibitem{Alekseyev}
Max~A. Alekseyev, On the intersections of {F}ibonacci, {P}ell, and {L}ucas
numbers, {\em Integers} {\bf 11} (2011), 239259.
\bibitem{BQ}
Arthur~T. Benjamin and Jennifer~J. Quinn, {\em Proofs That Really Count},
Vol.~27 of {\em The Dolciani Mathematical Expositions}, Mathematical
Association of America, 2003.
\bibitem{BG}
Alex Bramham and Martin Griffiths, Combinatorial interpretations of some
convolution identities, {\em Fibonacci Quart.} {\bf 54} (2016), 335339.
\bibitem{DW}
Gregory Dresden and Yichen Wang, A {g}eneral {c}onvolution {i}dentity, {\em Math.~Mag.}, to appear.
\bibitem{Frontczak}
Robert Frontczak, Some {F}ibonacci{L}ucas{T}ribonacci{L}ucas identities,
{\em Fibonacci Quart.} {\bf 56} (2018), 263274.
\bibitem{Hinz}
Andreas~M. Hinz, The {L}ichtenberg sequence, {\em Fibonacci Quart.} {\bf 55}
(2017), 212.
\bibitem{oeis}
The OEIS~Foundation Inc., The online encyclopedia of integer sequences, 2022.
\newblock Published electronically at \url{http://oeis.org/}.
\bibitem{KoshyPell}
Thomas Koshy, {\em Pell and {P}ell{L}ucas Numbers with Applications},
Springer, 2014.
\bibitem{KoshyFib}
Thomas Koshy, {\em Fibonacci and {L}ucas Numbers with Applications. {V}ol. 1},
Pure and Applied Mathematics, John Wiley \& Sons, Inc., 2018.
\bibitem{KoshyGriffiths}
Thomas Koshy and Martin Griffiths, Some {G}ibonacci convolutions with
dividends, {\em Fibonacci Quart.} {\bf 56} (2018), 237245.
\bibitem{Ruggles}
I.~Dale Ruggles, Some {F}ibonacci results using {F}ibonaccitype sequences,
{\em Fibonacci Quart.} {\bf 1} (1963), 7580.
\bibitem{Szakacs}
Tam\'{a}s Szak\'{a}cs, Convolution of second order linear recursive sequences
{I}, {\em Ann.~Math.~Inform.} {\bf 46} (2016), 205216.
\bibitem{Wilf}
Herbert~S. Wilf, {\em generatingfunctionology}, A K Peters, 3rd edition, 2006.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}: Primary 11B39;
Secondary 05A15, 05B45.
\noindent \emph{Keywords: } Fibonacci number, convolution, tiling,
generating function.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A000045},
\seqnum{A000073},
\seqnum{A000078},
\seqnum{A000100},
\seqnum{A000129},
\seqnum{A000217},
\seqnum{A000217},
\seqnum{A000930},
\seqnum{A000931},
\seqnum{A000975},
\seqnum{A000975},
\seqnum{A001045},
\seqnum{A002203},
\seqnum{A002203},
\seqnum{A006498}
\seqnum{A049674},
\seqnum{A052529},
\seqnum{A077939},
\seqnum{A094687},
\seqnum{A107920},
\seqnum{A113300},
and
\seqnum{A350498}.
)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received January 07 2022;
revised version received February 05 2022.
Published in {\it Journal of Integer Sequences}, March 21 2022.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}