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

\usepackage{tikz}
\usetikzlibrary{arrows}

\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 
Diagonal Sums in the Pascal Pyramid, II:  Applications
}
\Large
\vskip 1cm
Hac\`ene Belbachir and Abdelghani Mehdaoui\\
USTHB \\
Faculty of Mathematics\\
RECITS Laboratory\\
BP 32 \\
El Alia 16111 \\
Bab Ezzouar\\
Algiers \\
Algeria \\
\href {mailto:hacenebelbachir@gmail.com}{\tt hacenebelbachir@gmail.com} \\
\href {mailto:mehabdelghani@gmail.com}{\tt mehabdelghani@gmail.com}\\
\ \\
L\'aszl\'o Szalay\\
University of Sopron \\
Institute of Mathematics\\
Bajcsy-Zsilinszky utca 4\\
H-9400 Sopron \\
Hungary\\
\href {mailto:szalay.laszlo@uni-sopron.hu}{\tt szalay.laszlo@uni-sopron.hu}
\end{center}

\newpage

\begin{abstract}
In a previous paper, we derived a theorem which describes, in the language
of linear recurrences, the sum of diagonal elements lying along a finite
ray of a certain type crossing the 3-dimensional Pascal pyramid. The
corresponding generating function was also determined. In this paper,
we apply these results to prove several (more precisely 24) recurrence
relations previously
conjectured, or not given in the {\it On-Line Encyclopedia of Integer
Sequences}. Moreover, we provide many (exactly 75) new summatory identities
linked to sequences listed in the Encyclopedia.
\end{abstract}


\section{Introduction}

Let $(F_n)_{n=0}^\infty$ denote the Fibonacci sequence given by the
initial values $F_0=0$ and $F_1=1$, and by $F_n=F_{n-1}+F_{n-2}$ for
$n\ge2$.  Probably Binet \cite{Bi} was the first to publish
the identity
$$F_{n+1}={n\choose0}+{n-1\choose1}+{n-2\choose2}+\cdots,\quad (n\ge0)$$
about the sum of elements of ascending diagonals, which motivated the
paper \cite{BKSz} to investigate diagonals of arbitrary direction
similarly generating finite sums. It turned out that such sums can
also be described by suitable linear recurrences. In this paper, we
recall the two main theorems and some corollaries of \cite{BMSz} which
study the analogous question in the 3D Pascal pyramid (in short: PP3D),
and we apply the results to many sequences appearing in the {\it On-Line
Encyclopedia of Integer Sequences} (OEIS) \cite{Bi}.


It is known that trinomial coefficients 
$\binom{n}{i,\;j,\;k}=\frac{n!}{i!\cdot j!\cdot k!}$
(where $i,j,k$  are non-negative integers and $i+j+k=n$) appear in the expansion of $(x+y+z)^n$ as
\begin{equation}
(x+y+z)^n=\sum_{i+j+k=n}\binom{n}{i,\;j,\;k}x^i \; y^j\; z^k
\end{equation}
(see, for example, Feinberg \cite{F} or Anatriello and Vincenzi \cite{AV}). 

We adapted the trinomial coefficients to the 3D coordinate-system --- more
precisely, to the vertices of the lattice $\mathbb{Z}^3$. The location of
$\binom{n}{i,\;j,\;k}$ is the point $(i,j,-n)$ (recall that $n=i+j+k$).

Take two arbitrary vertices $P_0(x_0,y_0,z_0)\in\mathbb{Z}^3$ and
$P_1(x_1,y_1,z_1)\in\mathbb{Z}^3$ of the pyramid (that is, such
that the conditions $x_i\ge0$, $y_i\ge0$, $z_i\le0$,
$x_i+y_i+z_i\le0$ are fulfilled)
such that if $r=z_1-z_0$ holds, then
$$ \alpha_1=x_1-x_0>0,\qquad
\alpha_2=y_1-y_0>0,\qquad \alpha_1+\alpha_2+r>0.  $$ 
We also
require that $x_0+y_0+z_0<0$, excluding the case when the vector
$\overrightarrow{v}=\overrightarrow{P_0P_1}$ is on the plane $x+y+z=0$.

Along the straight line determined by the points $P_0$ and $P_1$ we translate  $-\overrightarrow{v}$ from $P_0$ as many times as possible: let $x_0=s_1\alpha_1+\ell_1$ with $0\le\ell_1<\alpha_1$,  and let $x_1=s_2\alpha_2+\ell_2$ with $0\le\ell_2<\alpha_2$. Put $s=\min\{s_1,s_2\}$, and then set
$$
\theta_1=x_0-s\alpha_1,\qquad \theta_2=y_0-s\alpha_2.
$$
The point we obtain, say $P$, has coordinates
$(\theta_1,\theta_2,z_0-sr)$.  Now we raise the point $P$ parallel
to the $z$-axis until it reaches the plane $x+y+z=0$. Then
we consider the uppermost ray defined by the quintuple
$(\alpha_1,\alpha_2,r,\theta_1,\theta_2)$. Note that, seemingly, the
conditions $\alpha_1>0$ and $\alpha_2>0$ together would not cover all the
possible directions in PP3D. Nevertheless, here they do because of the
symmetry of rotation around the vertical axis (before fitting PP3D to
the coordinate system).

Thus the direction $(\alpha_1,\alpha_2,r,\theta_1,\theta_2)$ defines diagonal rays in the Pascal pyramid. Such a ray contains the elements  
\begin{equation}
A_k=\binom{n-rk}{\theta_1+\alpha_1k,\; \theta_2+\alpha_2k,\; \eta_{k}}x^{\theta_1+\alpha_1k}y^{\theta_2+\alpha_2k}z^{\eta_{k}},
\end{equation}
where $k=0,\ldots,\lfloor \frac{n-\theta_1-\theta_2}{\alpha_1+\alpha_2+r}\rfloor$ and $\eta_{k}=n-\theta_1-\theta_2-(\alpha_1+\alpha_2+r)k$. Here 
$x,y$ and $z$ are nonzero real parameters. 
What most interests us is the sum
\begin{equation*}
T_n^{(\alpha_1,\alpha_2,r,\theta_1,\theta_2)}=\sum_{k=0}^{\lfloor \frac{n-\theta_1-\theta_2}{\alpha_1+\alpha_2+r} \rfloor}A_k,
\end{equation*} 
but computing it is a hard problem in general.

Belbachir, Mehdaoui, and Szalay \cite{BMSz} considered only 
$$
T_{n}^{(r)}=\sum_{k=0}^{\lfloor \frac{n}{r+2} \rfloor}\binom{n-rk}{k,\; k,\; n-(r+2)k}x^{k}y^{k}z^{n-(2+r)k}
$$
corresponding
to the particular case $(\alpha_1,\alpha_2,r,\theta_1,\theta_2)=(1,1,r,0,0)$.
They also assumed $r\ge-1$ to ensure the finiteness of the rays. Here we mention that Shannon \cite{S} found a connection between such sums and ternary recurrences. In fact, our approach is more general.

In the next section, we summarize the main result of \cite{BMSz} and its consequences.


\section{Previous results}

Assume $t=xy$. For notational convenience, set $T_n=T_n^{(r)}$.
\begin{theorem}\label{TH1}
The terms of the sequence $(T_n)$ given by 
\begin{equation}\label{sequ}
T_n=\sum_{k=0}^{\lfloor {n/(r+2)} \rfloor}\binom{n-rk}{k,\; k, \;n-(r+2)k}t^{k}z^{n-(r+2)k}
\end{equation} 
satisfy the linear recurrence relation
\begin{align}\label{Rec1}
nT_n=(2n-1)zT_{n-1}-(n-1)z^2T_{n-2}+2(2n-(r+2))tT_{n-r-2}.
\end{align}
\end{theorem} 

Observe that the last subscript which appears in the right-hand side of (\ref{Rec1}) is $n-r-2$. If $r=-1$ or $r=0$, then $T_{n-r-2}$ can be joined to $T_{n-1}$ or $T_{n-2}$, respectively. 
This is the Morgan-Voyce phenomenon,
and under such conditions we obtain the following corollaries. 

\begin{corollary}
If $r=0$, then the recurrence relation (\ref{Rec1}) simplifies to
\begin{align}\label{morgan2}
nT_n=(2n-1)zT_{n-1}+(n-1)(4t-z^2)T_{n-2}.
\end{align}
\end{corollary}

\begin{corollary}
Assume $r=-1$. Then (\ref{Rec1}) provides
\begin{align}\label{morgan1}
nT_n=(2n-1)(2t+z)T_{n-1}-(n-1)z^2T_{n-2}.
\end{align}
\end{corollary}

The comparison of the two formulae (\ref{morgan2}) and (\ref{morgan1})
makes it possible to establish equalities between two sums belonging to
the same recurrence. This idea leads to the following result.
\begin{corollary}\label{cc}
We have the identity
\begin{equation}\label{plu}
\sum_{k}^{\lfloor  n/2\rfloor} \binom {n}{ k,\; k,\; n-2k}(t_1\tau)^k\,(\tau+t_1)^{n-2k} =  \sum_{k}^n \binom {n+k}{ k,\; k,\; n-k}t_1^k\,(\tau-t_1)^{n-k},
\end{equation}
where $\tau\ne0$ and $\tau\ne \pm t_1$. 
\end{corollary}
Finally, we were able to determine the generating function of sequence \eqref{sequ} \cite{BMSz}.

\begin{theorem}\label{genf}
The generating function of variable $u$ of the sequence given by \eqref{sequ} is
\begin{equation}\label{genfunc}
g(u)=\frac{1}{\sqrt{(zu-1)^2-4tu^{r+2}}}.
\end{equation}
\end{theorem}

Now we list several examples of the type of Corollary \ref{cc} we found in the OEIS \cite{S}. In the sequel, keeping the notation of \cite{S} we use $(a_n)$ for the sequences (instead of $(T_n)$).




\section{List of new identities, and a combinatorial interpretation of Theorem \ref{TH1}}

\subsection{Supplement of OEIS}

We use the generating function for the identification of sequences since a sequence in the OEIS is usually defined by its generating function or the generating function is often given as a feature of the sequence. In other words, the generating function is the connection between the sequence, its recurrence relation, and the corresponding sum(s).

We split our results into four blocks. The first one contains the sequences for which the appropriate recurrence relations were given in the OEIS with the note ``conjecture''. The application of Theorem \ref{genf} (identification) and Theorem \ref{TH1} provide the proofs automatically. So we showed 

\begin{theorem}\label{nt1}
Each sequence of the first column of Table~\ref{tab1} satisfies the linear recurrence rule located in the same row of the second column.
\end{theorem}

Table~\ref{tab2} gives the sequences for which the recurrence relations were not given in the OEIS.

\begin{theorem}\label{nt2}
The sequences given in Table~\ref{tab2}
satisfy the corresponding recurrence relations.
\end{theorem}

The next theorem, thanks to Theorem \ref{TH1} and Corollary \ref{cc}, collects at least two new trinomial sums for some sequences. Note that the parameter $r$ of the direction $(\alpha_1,\alpha_2,r)=(1,1,r)$ appears, for example, in the upper index of the trinomial coefficient in (\ref{sequ}). Hence one can easily conclude the value of $r$ from the corresponding sum.

\begin{theorem}
Columns 2--4 of Table~\ref{tab3} provide new sum identities for the sequences of the first column.
\end{theorem}

Finally, we found a few new identities for certain sequences when only one sum exists or we could add only one new sum to the detected one(s).

\begin{theorem}\label{nt4}
The sums in Table~\ref{tab4} give new descriptions for the corresponding sequences.
\end{theorem}

\subsection{Powers of integers}

\begin{corollary}\label{c3}
Formula \eqref{sequ} simplifies to
\begin{align}\label{th2}
T_n=\sum_{k=0}^n \binom{n+k}{k,\;k,\; n-k}\;(-1)^{n-k}=1
\end{align}
if $r=-1$, $t=1$, and $z=-1$.
\end{corollary}

\begin{table}[H]
{\renewcommand{\arraystretch}{1.8}
\begin{center}
\resizebox{.70\textwidth}{!}{

\begin{tabular}{|c|l|} \hline   

OEIS code &  Recurrence relation conjectured in the OEIS \tabularnewline \hline

\href{https://oeis.org/A084768}{A084768} & $na_{n}=7(2n-1)a_{n-1}-(n-1)a_{n-2}$ \tabularnewline \hline

\href{https://oeis.org/A084769}{A084769} & $na_{n}=9(2n-1)a_{n-1}-(n-1)a_{n-2}$ \tabularnewline \hline 

\href{https://oeis.org/A084771}{A084771} & $na_{n}=5(2n-1)a_{n-1}-9(n-1)a_{n-2}$ \tabularnewline \hline 

\href{https://oeis.org/A098270}{A098270} & $na_{n}=10(2n-1)a_{n-1}-4(n-1)a_{n-2}$ \tabularnewline \hline 

\href{https://oeis.org/A098333}{A098333} & $na_n=(2n-1)a_{n-1}-13(n-1)a_{n-2}$ \tabularnewline \hline

\href{https://oeis.org/A098334}{A098334} & $na_n=(2n-1)a_{n-1}-17(n-1)a_{n-2}$ \tabularnewline \hline

\href{https://oeis.org/A098336}{A098336} & $na_n=2(2n-1)a_{n-1}-12(n-1)a_{n-2}$ \tabularnewline \hline

\href{https://oeis.org/A098337}{A098337} & $na_n=2(2n-1)a_{n-1}-20(n-1)a_{n-2}$ \tabularnewline \hline

\href{https://oeis.org/A098338}{A098338} & $na_n=3(2n-1)a_{n-1}-13(n-1)a_{n-2}$ \tabularnewline \hline

\href{https://oeis.org/A098340}{A098340} & $na_n=3(2n-1)a_{n-1}-21(n-1)a_{n-2}$ \tabularnewline \hline

\href{https://oeis.org/A098341}{A098341} & $na_{n}=3(2n-1)a_{n-1}-25(n-1)a_{n-2}$ \tabularnewline \hline 

\href{https://oeis.org/A098411}{A098411} & $na_n=8(2n-1)a_{n-1}-48(n-1)a_{n-2}$ \tabularnewline \hline

\href{https://oeis.org/A098439}{A098439} & $na_n=(2n-1)a_{n-1}+47(n-1)a_{n-2}$ \tabularnewline \hline

\href{https://oeis.org/A098456}{A098456} & $na_n=2(2n-1)a_{n-1}+64(n-1)a_{n-2}$ \tabularnewline \hline

\href{https://oeis.org/A098479}{A098479} & $na_n=(2n-1)a_{n-1}-(n-1)a_{n-2}+2(2n-3)a_{n-3}$ \tabularnewline \hline

\href{https://oeis.org/A098480}{A098480} & $na_n=(2n-1)a_{n-1}-(n-1)a_{n-2}+4(2n-3)a_{n-3}$ \tabularnewline \hline

\href{https://oeis.org/A106186}{A106186} & $na_{n}=2(2n-1)a_{n-1}-4(n-1)a_{n-2}+8(2n-3)a_{n-3}$ \tabularnewline \hline 

\href{https://oeis.org/A115864}{A115864} & $na_{n}=8(2n-1)a_{n-1}-16(n-1)a_{n-2}$ \tabularnewline \hline 

\href{https://oeis.org/A116092}{A116092} & $na_{n}=-4(2n - 1)a_{n-1}-64(n-1)a_{n-2}$ \tabularnewline \hline 

\href{https://oeis.org/A116093}{A116093} & $na_n=-2(2n-1)a_{n-1}-12(n-1)a_{n-2}$  \tabularnewline \hline

\href{https://oeis.org/A122868}{A122868} & $na_n=3(2n-1)a_{n-1}+3(n-1)a_{n-2}$ \tabularnewline \hline

\end{tabular}
}
\end{center}
}
\caption{Conjectured recurrence relations we proved.} 
\label{tab1}
\end{table}


\begin{table}[H]
{\renewcommand{\arraystretch}{1.8}

\begin{center}

\resizebox{.70\textwidth}{!}{

\begin{tabular}{|c|l|} \hline   

OEIS code & Recurrence relation we discovered \tabularnewline \hline

\href{https://oeis.org/A113179}{A113179} & $na_n=2(2n-1)a_{n-1}-4(n-1)a_{n-2}+4(2n-3)a_{n-3}$ \tabularnewline \hline

\href{https://oeis.org/A248168}{A248168} & $na_n=7(2n-1)a_{n-1}-33(n-1)a_{n-2}$ \tabularnewline \hline

\href{https://oeis.org/A258723}{A258723} & $na_n=6(2n-1)a_{n-1}-48(n-1)a_{n-2}$ \tabularnewline \hline

\end{tabular}
}
\end{center}

}
\caption{Recurrence relation discovered.} 
\label{tab2}
\end{table}



{\small
\begin{table}[H]
{\renewcommand{\arraystretch}{1.7}
\begin{center}

\resizebox{.95\textwidth}{!}{

\begin{tabular}{|c|l|l|l|} \hline   

OEIS code & \ \ \ Sum 1 & \ \ \ Sum 2 & \ \ \ Sum 3 \tabularnewline \hline

\href{https://oeis.org/A012000}{A012000} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,(-3)^k\,2^{n-2k}$ & $\sum_{k}^n\binom {n+k}{k,\;k,\;n-k}\,(-1)^k\,4^{n-k}$ & $\sum_{k}^n \binom {n+k}{k,\;k,\;n-k}\,3^k\,(-4)^{n-k}$ \tabularnewline \hline

\href{https://oeis.org/A084771}{A084771} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,4^k\,5^{n-2k}$ & $\sum_{k}^n \binom{n+k}{k,\;k,\;n-k}\,3^{n-k}$ & $\sum_{k}^n \binom {n+k}{k,\;k,\;n-k}\,4^k\,(-3)^{n-k}$ \tabularnewline \hline

\href{https://oeis.org/A084772}{A084772} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,5^k\,6^{n-2k}$ & $\sum_{k}^n \binom{n+k}{k,\;k,\;n-k}\,4^{n-k}$ & $\sum_{k}^n \binom {n+k}{k,\;k,\;n-k}\,5^k\,(-4)^{n-k}$ \tabularnewline \hline

\href{https://oeis.org/A084773}{A084773} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,8^k\,6^{n-2k}$ & $\sum_{k}^n \binom{n+k}{k,\;k,\;n-k}\,2^k2^{n-k}$ & $\sum_{k}^n \binom {n+k}{k,\;k,\;n-k}\,4^k\,(-2)^{n-k}$ \tabularnewline \hline

\href{https://oeis.org/A084774}{A084774} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,10^k\,7^{n-2k}$ & $\sum_{k}^n \binom{n+k}{k,\;k,\;n-k}\,2^k3^{n-k}$ & $\sum_{k}^n \binom {n+k}{k,\;k,\;n-k}\,5^k\,(-3)^{n-k}$ \tabularnewline \hline

\href{https://oeis.org/A098269}{A098269} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,15^k\,8^{n-2k}$ & $\sum_{k}^n \binom{n+k}{k,\;k,\;n-k}\,3^k2^{n-k}$ & $\sum_{k}^n \binom {n+k}{k,\;k,\;n-k}\,5^k\,(-2)^{n-k}$ \tabularnewline \hline

\href{https://oeis.org/A098270}{A098270} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,24^k\,10^{n-2k}$ & $\sum_{k}^n \binom{n+k}{k,\;k,\;n-k}\,4^k2^{n-k}$ & $\sum_{k}^n \binom {n+k}{k,\;k,\;n-k}\,6^k\,(-2)^{n-k}$ \tabularnewline \hline

\href{https://oeis.org/A098341}{A098341} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,(-4)^k\,3^{n-2k}$ & $\sum_{k}^n \binom{n+k}{k,\;k,\;n-k}\,(-1)^k5^{n-k}$ & $\sum_{k}^n \binom {n+k}{k,\;k,\;n-k}\,4^k\,(-5)^{n-k}$ \tabularnewline \hline

\href{https://oeis.org/A098659}{A098659} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,6^k\,7^{n-2k}$ & $\sum_{k}^n \binom{n+k}{k,\;k,\;n-k}\,5^{n-k}$ & $\sum_{k}^n \binom {n+k}{k,\;k,\;n-k}\,6^k\,(-5)^{n-k}$ \tabularnewline \hline

\href{https://oeis.org/A115864}{A115864} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,12^k\,8^{n-2k}$ & $\sum_{k}^n \binom{n+k}{k,\;k,\;n-k}\,2^k4^{n-k}$ & $\sum_{k}^n \binom {n+k}{k,\;k,\;n-k}\,6^k\,(-4)^{n-k}$ \tabularnewline \hline

\href{https://oeis.org/A115865}{A115865} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,27^k\,12^{n-2k}$ & $\sum_{k}^n \binom{n+k}{k,\;k,\;n-k}\,3^k6^{n-k}$ & $\sum_{k}^n \binom {n+k}{k,\;k,\;n-k}\,9^k\,(-6)^{n-k}$ \tabularnewline \hline

\href{https://oeis.org/A116091}{A116091} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,(-3)^k\,(-2)^{n-2k}$ & $\sum_{k}^n \binom{n+k}{k,\;k,\;n-k}\,(-3)^k4^{n-k}$ & $\sum_{k}^n \binom {n+k}{k,\;k,\;n-k}\,(-4)^{n-k}$ \tabularnewline \hline

\href{https://oeis.org/A116092}{A116092} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,(-12)^k\,(-4)^{n-2k}$ & $\sum_{k}^n \binom{n+k}{k,\;k,\;n-k}\,(-6)^k8^{n-k}$ & $\sum_{k}^n \binom {n+k}{k,\;k,\;n-k}\,2^k\,(-8)^{n-k}$ \tabularnewline \hline

\href{https://oeis.org/A069835}{A069835} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,3^k\,4^{n-2k}$ & already known & $\sum_{k}^n \binom {n+k}{k,\;k,\;n-k}\,3^k\,(-2)^{n-k}$ \tabularnewline \hline

\href{https://oeis.org/A084768}{A084768} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,12^k\,7^{n-2k}$ & already known & $\sum_{k}^n \binom {n+k}{k,\;k,\;n-k}\,4^k\,(-1)^{n-k}$ \tabularnewline \hline

\href{https://oeis.org/A084769}{A084769} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,20^k\,9^{n-2k}$ & already known & $\sum_{k}^n \binom {n+k}{k,\;k,\;n-k}\,5^k\,(-1)^{n-k}$ \tabularnewline \hline

\href{https://oeis.org/A098332}{A098332} & already known & $\sum_{k}^n \binom{n+k}{k,\;k,\;n-k}\,(-1)^k3^{n-k}$ & $\sum_{k}^n \binom {n+k}{k,\;k,\;n-k}\,2^k(-3)^{n-k}$ \tabularnewline \hline


\end{tabular}
}
\end{center}
}
\caption{Sums discovered.} 
\label{tab3}
\end{table}
}




\begin{table}[H]
{\renewcommand{\arraystretch}{1.8}
\begin{center}
\resizebox{.95\textwidth}{!}{
\begin{tabular}{|c|l||c|l|} \hline   

OEIS code & Sum & OEIS code & Sum \tabularnewline \hline

\href{https://oeis.org/A001850}{A001850} & $\sum_{k}^n \binom {n+k}{k,\;k,\;n-k}\,2^k\,(-1)^{n-k}$ & \href{https://oeis.org/A006134}{A006134} & $\sum_{k}^{\lfloor n/3\rfloor} \binom{n-k}{k,\;k,\;n-3k}\,3^{n-3k}$ \tabularnewline \hline

\href{https://oeis.org/A006442}{A006442} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,6^k\,5^{n-2k}$ & \href{https://oeis.org/A026375}{A026375} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,3^{n-2k}$ \tabularnewline \hline

\href{https://oeis.org/A059304}{A059304} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,4^k\,4^{n-2k}$ & \href{https://oeis.org/A080609}{A080609} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,2^k\,4^{n-2k}$ \tabularnewline \hline

\href{https://oeis.org/A081671}{A081671} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,4^{n-2k}$ & \href{https://oeis.org/A084605}{A084605} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,4^k$ \tabularnewline \hline

\href{https://oeis.org/A084770}{A084770} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,5^k\,2^{n-2k}$ & \href{https://oeis.org/A098339}{A098339} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,(-2)^k3^{n-2k}$ \tabularnewline \hline

\href{https://oeis.org/A098409}{A098409} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,5^{n-2k}$ & \href{https://oeis.org/A098410}{A098410} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,6^{n-2k}$ \tabularnewline \hline

\href{https://oeis.org/A098411}{A098411} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,4^k8^{n-2k}$  & \href{https://oeis.org/A098430}{A098430} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,16^k8^{n-2k}$ \tabularnewline \hline

\href{https://oeis.org/A098443}{A098443} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,5^k4^{n-2k}$  & \href{https://oeis.org/A098444}{A098444} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,5^k3^{n-2k}$ \tabularnewline \hline

\href{https://oeis.org/A098453}{A098453} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,4^k2^{n-2k}$  & \href{https://oeis.org/A098455}{A098455} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,10^k2^{n-2k}$ \tabularnewline \hline

\href{https://oeis.org/A098456}{A098456} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,17^k2^{n-2k}$  & \href{https://oeis.org/A098658}{A098658} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,9^k6^{n-2k}$ \tabularnewline \hline

\href{https://oeis.org/A106186}{A106186} & $\sum_{k}^{\lfloor n/3\rfloor} \binom{n-k}{k,\;k,\;n-3k}\,4^k2^{n-3k}$  & \href{https://oeis.org/A106258}{A106258} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,6^k4^{n-2k}$ \tabularnewline \hline

\href{https://oeis.org/A106259}{A106259} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,12^k6^{n-2k}$  & \href{https://oeis.org/A106260}{A106260} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,20^k8^{n-2k}$ \tabularnewline \hline

\href{https://oeis.org/A106261}{A106261} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,30^k10^{n-2k}$  & \href{https://oeis.org/A122868}{A122868} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,3^k3^{n-2k}$ \tabularnewline \hline

\href{https://oeis.org/A248168}{A248168} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,4^k7^{n-2k}$  & \href{https://oeis.org/A258723}{A258723} & $\sum_{k}^{\lfloor n/2\rfloor} \binom{n}{k,\;k,\;n-2k}\,(-3)^k6^{n-2k}$ \tabularnewline \hline

\end{tabular}
}
\end{center}
}
\caption{Sums discovered.} 
\label{tab4}
\end{table}



\begin{proof}
Obviously, \eqref{th2} satisfies the recurrence rule \eqref{morgan1}. Hence for $n\ge2$ we have 
\begin{equation*}
nT_n=(2\,n-1)\,T_{n-1}+(n-1)\,T_{n-2},
\end{equation*}
which is equivalent to
\begin{equation*}
n\underbrace{(T_n-T_{n-1})}_{U_n} =
(n-1)\underbrace{(T_{n-1}-T_{n-2})}_{U_{n-1}}, 
\end{equation*}
and then to
\begin{equation*} 
\underbrace{n\,U_n}_{V_n}=\underbrace{(n-1)\,U_{n-1}}_{V_{n-1}}.
\end{equation*} 
Consequently, $V_n=V_1$ holds for $n\ge2$.
The initial values $T_0=T_1=1$ imply $V_1=0$. Thus $nU_n=0$ gives $U_n=0$, and then $T_n=T_{n-1}$ follows, which together with the initial values proves 
$T_n=1$ for all $n\ge0$. 
\end{proof}

\begin{corollary}\label{c4}
Assume that $r=-1$ and $z=-t$ hold in (\ref{sequ}). Then we have $T_n=t^n$.
\end{corollary}
\begin{proof}
Combine  \eqref{sequ}, Corollary \ref{c3}, and the conditions here to get
\begin{equation*}
T_n=\sum_{k=0}^{n}\binom{n+k}{k,\; k,\; n-k}t^{k}(-t)^{n-k}=t^n.
\end{equation*}
\end{proof}
Replacing $r=-1$ and $t=-z$ in  \eqref{th2},
together with Corollary \ref{c3} immediately leads to
\begin{corollary}\label{c5}
\begin{equation*}
T_n=\sum_{k=0}^{n}\binom{n+k}{k, \;k,\; n-k}(-z)^{k}z^{n-k}=(-z)^n.
\end{equation*}
\end{corollary}

\subsection{A combinatorial interpretation}

A combinatorial interpretation of sequence (\ref{sequ}) corresponding to the direction $(r,1,1)$ follows easily from the sum of (\ref{sequ}).
\begin{theorem}
The sequence $T_n$ in (\ref{sequ}) gives the sum of products of weighs associated with the walk in the square lattice from the point $(0,0)$ to $(n,n)$ when the steps allowed are in $\{(2+r,0),(0,2+r),(1,1)\}$. The first and second steps of the walk have weight $\sqrt{t}$, while the last one has $z$.
\end{theorem}

\begin{example}
The triple $(r,t,z)=(-1,3,2)$ yields a Morgan-Voyce direction, and provides the sequence \href{https://oeis.org/A098269}{A098269}. It can be given by 
$$T_n=\sum_{k=0}^n\binom{n+k}{k,\;k,\;n-k}3^k\;2^{n-k},$$
the first few elements are: $1, 8, 94, 1232, 16966, 240368, 3468844, \ldots$. 

The sums of products of weights are related to the lattice paths from $(0,0)$ to $(n,n)$ using only the steps $(1,0),(0,1)$ and $(1,1)$, with the weights $\sqrt{3}$, $\sqrt{3}$, $2$, respectively. 
In case of $n=2$ we illustrate all paths from $(0,0)$ to $(2,2)$ in Figure 1, which imply 
\begin{eqnarray*}
T_2&=&(\sqrt{3}\times\sqrt{3}\times\sqrt{3}\times\sqrt{3})+(2\times\sqrt{3}\times\sqrt{3})+(\sqrt{3}\times\sqrt{3}\times\sqrt{3}\times\sqrt{3})\\
&&+(\sqrt{3}\times 2\times\sqrt{3})
+(2\times2)+(\sqrt{3}\times\sqrt{3}\times\sqrt{3}\times\sqrt{3})+(\sqrt{3}\times\sqrt{3}\times\sqrt{3}\times\sqrt{3})\\
&&+(2\times\sqrt{3}\times\sqrt{3})
+(\sqrt{3}\times\sqrt{3}\times 2)+(\sqrt{3}\times\sqrt{3}\times\sqrt{3}\times\sqrt{3})\\
&&+(\sqrt{3}\times\sqrt{3}\times\sqrt{3}\times\sqrt{3})
+(\sqrt{3}\times\sqrt{3}\times 2)
+(\sqrt{3}\times 2 \times \sqrt{3})\\
&&=94.
\end{eqnarray*}

\begin{figure}[H]
\begin{center}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm] 
\draw [->,>=latex, line width=1.2pt] (-5.,0.) -- (-4.,1.);
\draw [->,>=latex, line width=1.2pt] (-4.,1.) -- (-3.,2.);
\draw [->,>=latex, line width=1.2pt] (0.9846242552373632,0.) -- (1.9846242552373634,0.);
\draw [->,>=latex, line width=1.2pt] (1.9846242552373634,0.) -- (2.9846242552373634,0.);
\draw [->,>=latex, line width=1.2pt] (2.9846242552373634,0.) -- (2.9846242552373634,0.9846242552373631);
\draw [->,>=latex, line width=1.2pt] (2.9846242552373634,0.9846242552373631) -- (2.9846242552373634,1.984624255237363);
\draw [->,>=latex, line width=1.2pt] (4.,0.) -- (5.,1.);
\draw [->,>=latex, line width=1.2pt] (5.,1.) -- (6.,1.);
\draw [->,>=latex, line width=1.2pt] (6.,1.) -- (6.,2.);
\draw [->,>=latex, line width=1.2pt] (-2.,3.) -- (-1.,4.);
\draw [->,>=latex, line width=1.2pt] (-1.,4.) -- (-1.,5.);
\draw [->,>=latex, line width=1.2pt] (-1.,5.) -- (0.,5.);
\draw [->,>=latex, line width=1.2pt] (-5.,-3.) -- (-5.,-2.);
\draw [->,>=latex, line width=1.2pt] (-5.,-2.) -- (-4.,-2.);
\draw [->,>=latex, line width=1.2pt] (-4.,-2.) -- (-3.,-1.);
\draw [->,>=latex, line width=1.2pt] (-2.,-3.) -- (-2.,-2.);
\draw [->,>=latex, line width=1.2pt] (-2.,-2.) -- (-2.,-1.);
\draw [->,>=latex, line width=1.2pt] (-2.,-1.) -- (-1.,-1.);
\draw [->,>=latex, line width=1.2pt] (-1.,-1.) -- (0.,-1.);
\draw [->,>=latex, line width=1.2pt] (1.,-3.) -- (2.,-3.);
\draw [->,>=latex, line width=1.2pt] (2.,-3.) -- (2.,-2.);
\draw [->,>=latex, line width=1.2pt] (2.,-2.) -- (2.,-1.);
\draw [->,>=latex, line width=1.2pt] (2.,-1.) -- (3.,-1.);
\draw [->,>=latex, line width=1.2pt] (4.,-3.) -- (5.,-3.);
\draw [->,>=latex, line width=1.2pt] (5.,-3.) -- (5.,-2.);
\draw [->,>=latex, line width=1.2pt] (5.,-2.) -- (6.,-1.);
\draw [->,>=latex, line width=1.2pt] (1.,3.) -- (1.,4.);
\draw [->,>=latex, line width=1.2pt] (3.,4.) -- (3.,5.);
\draw [->,>=latex, line width=1.2pt] (-2.,0.) -- (-2,1.);
\draw [->,>=latex, line width=1.2pt] (-2.,1.) -- (-1.,1.);
\draw [->,>=latex, line width=1.2pt] (-1.,1.) -- (-1.,2.);
\draw [->,>=latex, line width=1.2pt] (-1.,2.) -- (0.,2.);
\draw [->,>=latex, line width=1.2pt] (1.,4.) -- (2.,4.);
\draw [->,>=latex, line width=1.2pt] (2.,4.) -- (3.,4.);
\draw [->,>=latex, line width=1.2pt] (-5.,3.) -- (-4.,3.);
\draw [->,>=latex, line width=1.2pt] (-4.,3.) -- (-4.,4.);
\draw [->,>=latex, line width=1.2pt] (-4.,4.) -- (-3.,4.);
\draw [->,>=latex, line width=1.2pt] (-3.,4.) -- (-3.,5.);
\draw [->,>=latex, line width=1.2pt] (4.,3.) -- (5.,3.);
\draw [->,>=latex, line width=1.2pt] (5.,3.) -- (6.,4.);
\draw [->,>=latex, line width=1.2pt] (6.,4.) -- (6.,5.);
\draw [->,>=latex, line width=1.2pt] (-1.,-6.) -- (-1.,-5.);
\draw [->,>=latex, line width=1.2pt] (-1.,-5.) -- (0.,-4.);
\draw [->,>=latex, line width=1.2pt] (0.,-4.) -- (1.,-4.);

\draw (-5.,3.6) node[anchor=north west] {\small $\sqrt{3}$};
\draw (-4.,3.8) node[anchor=north west] {\small $\sqrt{3}$};
\draw (-4.,4.6) node[anchor=north west] {\small $\sqrt{3}$};
\draw (-3.,4.8) node[anchor=north west] {\small $\sqrt{3}$};
 
\draw (-1.,4.8) node[anchor=north west] {\small $\sqrt{3}$};
\draw (-2.,3.8) node[anchor=north west] {\small ${2}$};
\draw (-1.,5.6) node[anchor=north west] {\small $\sqrt{3}$};


\draw (0.2,3.8) node[anchor=north west] {\small $\sqrt{3}$};
\draw (1.,4.6) node[anchor=north west] {\small $\sqrt{3}$};
\draw (2.,4.6) node[anchor=north west] {\small $\sqrt{3}$};
\draw (3.,4.8) node[anchor=north west] {\small $\sqrt{3}$};


\draw (4.,3.6) node[anchor=north west] {\small $\sqrt{3}$};
\draw (5.,3.8) node[anchor=north west] {\small ${2}$};
\draw (5.2,4.8) node[anchor=north west] {\small $\sqrt{3}$};


\draw (-5.,1.) node[anchor=north west] {\small ${2}$};
\draw (-4.,1.9) node[anchor=north west] {\small ${2}$};


\draw (-2.9,0.8) node[anchor=north west] {\small $\sqrt{3}$};
\draw (-1.9,1.6) node[anchor=north west] {\small $\sqrt{3}$};
\draw (-1,1.8) node[anchor=north west] {\small $\sqrt{3}$};
\draw (-1,2.6) node[anchor=north west] {\small $\sqrt{3}$};

\draw (1,0.6) node[anchor=north west] {\small $\sqrt{3}$};
\draw (2,0.6) node[anchor=north west] {\small $\sqrt{3}$};
\draw (3,.8) node[anchor=north west] {\small $\sqrt{3}$};
\draw (3,1.6) node[anchor=north west] {\small $\sqrt{3}$};

\draw (4,.8) node[anchor=north west] {\small ${2}$};
\draw (5,1.6) node[anchor=north west] {\small $\sqrt{3}$};
\draw (6,1.8) node[anchor=north west] {\small $\sqrt{3}$};

\draw (-5.8,-2.2) node[anchor=north west] {\small $\sqrt{3}$};
\draw (-4.9,-1.4) node[anchor=north west] {\small $\sqrt{3}$};
\draw (-4.,-1.2) node[anchor=north west] {\small ${2}$};

\draw (-2.8,-2.2) node[anchor=north west] {\small $\sqrt{3}$};
\draw (-2.8,-1.2) node[anchor=north west] {\small $\sqrt{3}$};
\draw (-2,-.34) node[anchor=north west] {\small $\sqrt{3}$};

\draw (-1,-.34) node[anchor=north west] {\small $\sqrt{3}$};

\draw (1,-2.34) node[anchor=north west] {\small $\sqrt{3}$};
\draw (2,-2.3) node[anchor=north west] {\small $\sqrt{3}$};
\draw (2,-1.3) node[anchor=north west] {\small $\sqrt{3}$};
\draw (2,-.4) node[anchor=north west] {\small $\sqrt{3}$};

\draw (4,-2.4) node[anchor=north west] {\small $\sqrt{3}$};
\draw (5,-2.2) node[anchor=north west] {\small $\sqrt{3}$};
\draw (5,-1.1) node[anchor=north west] {\small ${2}$};

\draw (-1.8,-5.3) node[anchor=north west] {\small $\sqrt{3}$};
\draw (-1.,-4.2) node[anchor=north west] {\small ${2}$};
\draw (0,-3.4) node[anchor=north west] {\small $\sqrt{3}$};

\end{tikzpicture}
\caption{All lattice paths linked to \href{https://oeis.org/A098269}{A098269}.}
\end{center}
\end{figure}

\end{example}

\begin{thebibliography}{9}

\bibitem{AV} G. Anatriello and V. Giovanni, Tribonacci-like sequences and
generalized Pascal's pyramids, \emph{Internat. J. Math. Ed. Sci. Tech.}
{\bf 45} (2014), 1220--1232.

\bibitem{BKSz} H. Belbachir, T. Komatsu, and L. Szalay, Linear recurrences
associated with rays in Pascal's triangle and combinatorial identities,
\emph{Math.~Slovaca} {\bf 64} (2014), 287--300.

\bibitem{BMSz} H. Belbachir, A. Mehdaoui, and L. Szalay, Diagonal
sums in 3D Pascal pyramid, \emph{J. Combin. Theory Ser. A} {\bf 165}
(2019), 106--116.

\bibitem{Bi} J. P. M. Binet, M{\'e}moire sur l'int{\'e}gration des
{\'e}quations lin{\'e}aires aux diff{\'e}rences finies, d'un ordre
quelconque {\`a} coefficients variables, {\it Comptes Rendus des
S{\'e}ances de l'Acad{\'e}mie des Sciences} {\bf 17} (1843), 559--567.

\bibitem{F} M. Feinberg, New slants, \emph{Fibonacci Quart.} {\bf 2}
(1964), 223--227.

\bibitem{Sh} A. G. Shannon, Iterative formulas associated with generalized
third order recurrence relations, \emph{SIAM J. Appl. Math.} {\bf 23}
(1972), 364--368.

\bibitem{S} N. J. A. Sloane et al., \emph{The On-Line Encyclopedia of Integer
Sequences}. Available at \url{https://oeis.org}.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 11B65; Secondary 11B37, 05A10.

\noindent \emph{Keywords:}
Pascal pyramid, trinomial coefficient, combinatorial identity,
linear recurrence.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A001850},
\seqnum{A006134},
\seqnum{A006442},
\seqnum{A012000},
\seqnum{A026375},
\seqnum{A059304},
\seqnum{A069835},
\seqnum{A080609},
\seqnum{A081671},
\seqnum{A084605},
\seqnum{A084768},
\seqnum{A084769},
\seqnum{A084770},
\seqnum{A084771},
\seqnum{A084772},
\seqnum{A084773},
\seqnum{A084774},
\seqnum{A098269},
\seqnum{A098270},
\seqnum{A098332},
\seqnum{A098333},
\seqnum{A098334},
\seqnum{A098336},
\seqnum{A098337},
\seqnum{A098338},
\seqnum{A098339},
\seqnum{A098340},
\seqnum{A098341},
\seqnum{A098409},
\seqnum{A098410},
\seqnum{A098411},
\seqnum{A098430},
\seqnum{A098439},
\seqnum{A098443},
\seqnum{A098444},
\seqnum{A098453},
\seqnum{A098455},
\seqnum{A098456},
\seqnum{A098479},
\seqnum{A098480},
\seqnum{A098658},
\seqnum{A098659},
\seqnum{A106186},
\seqnum{A106258},
\seqnum{A106259},
\seqnum{A106260},
\seqnum{A106261},
\seqnum{A113179},
\seqnum{A115864},
\seqnum{A115865},
\seqnum{A116091},
\seqnum{A116092},
\seqnum{A116093},
\seqnum{A122868},
\seqnum{A248168}, and
\seqnum{A258723}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received March 30 2018;
revised versions received  February 4 2019; February 12 2019; March 6 2019.
Published in {\it Journal of Integer Sequences}, May 19 2019.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                


.