\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 On-Line Encyclopedia of Integer Sequences \cite{oeis}) with the seemingly-unrelated  Jacobsthal numbers $J_n$ (\seqnum{A001045}),
\begin{equation}\label{last1.1}
\sum_{i=0}^n F_i J_{n-i} = 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_{n-i} = 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_{n-i} = 
      \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_{3i-1}t_{n-i} = 
      N_{3n-1} - 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_{n-i} = 
      \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^{n-i} &= 
       F_{n+2} - 1\cdot 1^{n+1}\label{fib1}\\
    \sum_{i=0}^n F_{2i}\, 3^{n-i} &= 
      1\cdot 3^{n+1} - F_{2(n+2)}\label{fib2}\\
    \sum_{i=0}^n F_{3i}\, 4^{n-i} &= 
      F_{3(n+2)} -  2\cdot 4^{n+1}.\label{fib3}\\
\intertext{The general rule is}
\sum_{i=0}^n F_{ki}\, (L_k)^{n-i} &= (-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^{n-i} &= 
       P_{n+2} - 1\cdot 2^{n+1}\label{pell1}\\
    \sum_{i=0}^n P_{2i}\, 6^{n-i} &= 
      2\cdot 6^{n+1} - P_{2(n+2)}\label{pell2}\\
    \sum_{i=0}^n P_{3i}\, 14^{n-i} &= 
      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)^{n-i} &= (-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 Pell-Lucas 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 well-known formula
\begin{align}
\sum_{i=0}^n F_i P_{n-i} &= P_n - F_n\label{FibPell11}\\
\intertext{and the less familiar formula}
\sum_{i=0}^n F_{3i} P_{n-i} &= 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 Pell-Lucas numbers $Q_n$, 
\begin{equation}\label{FibPell}
\sum_{i=0}^n F_{ki} P_{m(n-i)} = 
    \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^2-5y^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 non-negative  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(n-i)} = 
    \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(n-i)} = 
    \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_{2n-i-1} 
\ = \ 
\frac{2}{3}\sum_{i=0}^{n}  F_{2i-1} F_{4(n-i)}
\ = \ 
\frac{1}{2}\left(F_{4n+1} - F_{2n-1}\right).
\end{equation}
This formula is completely new, and it illustrates how our approach can produce novel results. 

The right-hand 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 $((n-1)F_n + 2nF_{n-1})/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(n-i)} = \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_{n-1} + c_2 a_{n-2} + \cdots + c_L a_{n-L}
\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/(1-x-x^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 non-zero 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_{n-i}} \ = \ 
\displaystyle\sum_{i=0}^n{b_i}{a_{n-i}} \ = \ \frac{1}{d_j}\Big(b_{n+j-1} - a_{n+j-1}\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 second-order 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^{j-1} 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^{j-1}} - \frac{A(x)}{x^{j-1}}\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_{n-i} \right)_{n \geq 0}$ which if we replace $i$ with $n-i$ gives us the identical expression 
$\left(\sum_{i=0}^n b_i a_{n-i} \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^{j-1}}   \ = \ \sum_{n=-(j-1)}^{\infty} a_{n+(j-1)} x^n,
\]
with a similar statement for $B(x)/x^{j-1}$. 
Hence, equation (\ref{AxBx}) can be rewritten in terms of coefficients as
\[
\sum_{i=0}^n a_i b_{n-i} = \frac{1}{d_j} \Big( b_{n+j-1}- a_{n+j-1}\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 degree-two 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_{n-1} + c_2 a_{n-2} + \cdots + c_L a_{n-L}
$$
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 $n-1$, 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 non-negative 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 $n-1$ 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+j-2$ 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+j-1}$ ways using all $c_j + d_j$ colors for the $j$-mino and $a_{n+j-1}$ ways that do not use the additional
 $d_j$ colors, so their difference $b_{n+j-1} - a_{n+j-1}$ 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+j-1$ on our board of length $n+j-2$ as $i$ ranges from 1 to $n-1$; see  Figure \ref{f1Label}.
 
 
 \begin{figure}[h]
\centering
    \includegraphics[scale=0.6]{dresden-fig12b.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 $i-1$ to the left
 of the $j$-mino (these tilings could use one of these ``additional"  $d_j$ colors) and $a_{n-i}$ possible tilings for the board of length $n-i-1$ 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_{n-i}$ tilings for this configuration, and summing over $i$ from $1$ to $n-1$ gives 
 \[
 d_j \cdot \sum_{i=1}^{n-1} b_{i} a_{n-i},
 \]
 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_{n-i}
 $$
 total number of tilings. Comparing this with our expression $b_{n+j-1} - a_{n+j-1}$ 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}{1-x-x^2}\\
\sum_{n=0}^\infty{J_n x^n} &= \frac{x}{1-x-2x^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_{n-i} = 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_{n-i} = 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}{1-4x-x^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}{1-4x-x^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_{n-i} = \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}{(1-x)^3} = \frac{x}{1-3x+3x^2-x^3}
\qquad \mbox{and} \qquad 
\frac{x}{1-4x+3x^2-x^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_{3n-1}$ 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_{n-i}  =  b_n - a_n,
\end{equation}
and we replace $a_n$ and $b_n$ with $t_n$
and $N_{3n-1}$ 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}{1-2x-x^2+2x^3}
\end{equation}
and so when we look at 
\[
\sum_{i=0}^{n} \ell_i P_{n-i}
\]
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_{n-i} = 
\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_{n-i} = 
\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_{n-i} \ - \ 
(P_n + P_{n-2} + P_{n-4} + \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_{n-2} + P_{n-4} + \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_{n-i}  = 
\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_{n-i}  = 
\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_{n-1} + \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+1-i}$ on the left of 
equation (\ref{almostJP}). We now replace all $n$'s with $n-1$'s in (\ref{almostJP}) to obtain
\begin{equation}\label{almostJP2}
\sum_{i=0}^{n} J_{i} P_{n-i}  = 
\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)^{n-1}$ to 
have $\sum_{n=0}^\infty b_n x^n$ match the coefficients of $x/(1-L_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_{n-i}  = 
\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)^{n-1}$ 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}^{n-1} (F_{ki}/F_k) (L_k)^{n-1-i}  = 
\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)^{n-i} = (-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_{2n-i-1} 
\ = \ 
\frac{2}{3}\sum_{i=0}^{n}  F_{2i-1} F_{4(n-i)}
\ = \ 
\frac{1}{2}\left(F_{4n+1} - F_{2n-1}\right).
\end{equation}
We begin with the sum on the far left. 
We note that if we let 
$a_n = (-1)^{n-1}F_{n-1} + 1$ 
and 
$b_n = F_nF_{n+1}$
then 
the two sequences have generating functions
$x/(1-2x^2 + x^3)$
and 
$x/(1-2x-2x^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)^{n-i-1}F_{n-i-1} + 1\right)
= \frac{1}{2}\left( F_n F_{n+1} - 
((-1)^{n-1}F_{n-1} + 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_{2n-i-1} 
    \ + \ \sum_{i=0}^{2n}  F_i F_{i+1}
\ = \ \frac{1}{2}\left( F_{2n} F_{2n+1} +
F_{2n-1} - 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_{2n-i-1} 
\ = \ \frac{1}{2}\left( F_{2n} F_{2n+1} +
F_{2n-1} - 1 - 2F_{2n+1}^2 + 2
\right),
\end{equation}
and after some tedious calculations the right-hand side simplifies to 
$\left( F_{2n-1} - 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_{2i-1} = 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_{2i-1} F_{4(n-i)} 
\ = \ 
\frac{2}{3}
\sum_{i=0}^{n}  F_{2(i+1)} F_{4(n-i)} - 
\frac{4}{3}\sum_{i=0}^{n}  F_{2i} F_{4(n-i)}.
\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_{2i-1} F_{4(n-i)} 
\ = \ 
\frac{2}{3}
\sum_{i=0}^{n}  F_{2(i+1)} F_{4(n-i)} - 
\frac{1}{3}\left( F_{4n} - 3 F_{2n}\right),
\end{equation}
and for the first sum on the right, we first re-index the sum (replacing $i$ with $i-1$) to get 
$(2/3)\sum_{i=1}^{n+1}  F_{2i} F_{4(n+1-i)}$ 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+1-i)}$ 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_{2i-1} F_{4(n-i)} 
\ = \ 
\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_{2i-1} F_{4(n-i)} 
\ = \ 
\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_{2n-1}$, we get 
\begin{equation}\label{46}
\frac{2}{3}\sum_{i=0}^{n}  F_{2i-1} F_{4(n-i)} 
\ = \ 
\frac{1}{6}\Big( 3F_{4n+1}
 - 3F_{2n-1}\Big) 
\  = \  \frac{1}{2}\left( F_{4n+1}
 - F_{2n-1}\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 order-two 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 Fibonacci-type and Lucas-type sequences with the same signatures but different initial values, as follows:
 \begin{theorem}[Dresden, Wang]
For a given  Fibonacci-type sequence  $(\mathcal{F}_n^{(k)})_{n \geq 0}$ and companion Lucas-type 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 single-color tiles of lengths $1$ through $k$, we have
\begin{equation*}
\sum_{i=0}^{n-1} \mathcal{F}_i^{(k)} \mathcal{L}_{n-i}^{(k)} \  = \ (n-1)\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 Lucas-Lehmer 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^n-1$
(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+1-i} \  = \ 
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 re-index, 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_{2n-2i+1} 
+
\sum_{i=0}^{n} (F_{i+1})^2 U_{2n-2i} 
\  = \ 
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), 239--259.

\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), 335--339.

\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), 263--274.

\bibitem{Hinz}
Andreas~M. Hinz, The {L}ichtenberg sequence, {\em Fibonacci Quart.} {\bf 55}
  (2017), 2--12.

\bibitem{oeis}
The OEIS~Foundation Inc., The on-line 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), 237--245.

\bibitem{Ruggles}
I.~Dale Ruggles, Some {F}ibonacci results using {F}ibonacci-type sequences,
  {\em Fibonacci Quart.} {\bf 1} (1963), 75--80.

\bibitem{Szakacs}
Tam\'{a}s Szak\'{a}cs, Convolution of second order linear recursive sequences
  {I}, {\em Ann.~Math.~Inform.} {\bf 46} (2016), 205--216.

\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}
