\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \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,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Playing with Some Identities of Andrews } \vskip 1cm \large Donatella Merlini and Renzo Sprugnoli\\ Dipartimento di Sistemi e Informatica \\ Universit\`a di Firenze \\ viale Morgagni 65 \\ 50134 Firenze \\ Italy\\ \href{merlini@dsi.unifi.it}{\tt merlini@dsi.unifi.it}\\ \href{sprugnoli@dsi.unifi.it}{\tt sprugnoli@dsi.unifi.it}\\ \end{center} \vskip .2 in \begin{abstract} We study two remarkable identities of Andrews relating Fibonacci numbers and binomial coefficients in terms of generating functions and Riordan arrays. We thus give a deeper insight to the problem and find several new identities involving many other well-known sequences. \end{abstract} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \renewcommand{\theequation}{\thesection.\arabic{equation}} \newcommand{\N}{\mbox{$\mathbb{N}$}} \newcommand{\SEP}{\ \Bigm|\ } \newcommand{\EQ}[1]{\mbox{$\stackrel{\ \small #1}{=}\ $}} \section{Introduction} There exists a famous relation between binomial coefficients and Fibonacci numbers. In fact, Fibonacci numbers are just the diagonal sums of the Pascal triangle. The exact formula is $$F_{n+1} = \sum_{k=0}^n {n-k \choose k},$$ which can be proved in several ways. In order to introduce some concepts that will be used in the present paper, we prove this identity by means of the Riordan array method. A \emph{Riordan array} $D = (d_{n,k})_{n,k \in \N}$ is an infinite, lower triangular array defined by a pair of formal power series $\mathcal{R}(d(t),\ h(t))$ such that $d_{n,k} = [t^n]d(t)h(t)^k,$ where $[t^n]$ denotes the ``coefficient of'' operator $[t^n]\sum_{k\geq 0}f_kt^k=f_n.$ If $d(0) \neq 0$, $h(0) = 0$ and $h'(0) \neq 0$, then the Riordan array is called \emph{proper}. In practice, $D$ is defined by the generating functions of its columns, which are $d(t)h(t)^k$ for $k \in \mathbb{N}$. There is a connection between Riordan arrays and combinatorial sums; in fact, we have the following result: $$\sum_{k=0}^n d_{n,k}f_k = [t^n] d(t) f(h(t))$$ where $f(t)$ is the generating function of the sequence $(f_k)_{k \in \N}$. This means that the evaluation of the sum is reduced to the extraction of a coefficient from a formal power series. As a consequence of these facts, Sprugnoli \cite{Spr94} proved the two following summation rules involving binomial coefficients: \begin{equation} \label{Asum} \sum_k{n+ak\choose m+bk}f_k = [t^n]{t^m\over (1-t)^{m+1}}f\left({t^{b-a} \over (1-t)^b}\right), \qquad b>a; \end{equation} \begin{equation} \label{Bsum} \sum_k{n+ak\choose m+bk}f_k =[t^m](1+t)^nf(t^{-b}(1+t)^a), \qquad b<0. \end{equation} In the present paper, usually we will use these formulas with $f_k=1$ and hence $f(t)=1/(1-t).$ Let us consider the more general sum $\sum_{k=0}^n {n-k \choose k}c^kb^{n-2k}$ and apply Formula (\ref{Asum}): $$\sum_{k=0}^n {n-k \choose k}c^kb^{n-2k} = b^n\sum_{k=0}^n {n-k \choose k} \left( {c \over b^2}\right)^k =$$ $$ b^n[t^n] \frac{1}{1-t} \left[ \frac{1}{1-cu/b^2} \SEP u = \frac{t^2}{1-t} \right]=$$ $$ =b^n [t^n]\frac{1}{1-t-ct^2/b^2} = [t^{n}] \frac{1}{1-bt-ct^2}$$ where the notation: $\left[ f(u) \ |\ u=g(t) \right]$ is the linear form of the substitution rule $f(u) |_{u = g(t)} = f(g(t))$. For $b=c=1,$ the coefficient is obviously $F_{n+1}$ (sequence \seqnum{A000045} in \cite{IS}). On the other hand, we have obtained the generating function of several important sequences; for example, for $b=1, c=2,$ we have the Jacobsthal sequence; for $b=2, c=1,$ we have the Pell sequence; for $b=3, c=-2,$ we have the Mersenne sequence (sequences \seqnum{A001045}, \seqnum{A000129} and \seqnum{A000225} in \cite{IS}, respectively). We shall use some of these sequences again in what follows. Many years ago, Andrews \cite{And69} found two remarkable formulas relating Fibonacci numbers and binomial coefficients: \begin{equation}\label{andrews1} F_n = \sum_{j=-\infty}^\infty (-1)^j {n \choose \lfloor(n-1-5j)/2 \rfloor}, \end{equation} \begin{equation}\label{andrews2} F_n = \sum_{j=-\infty}^\infty (-1)^j {n-1 \choose \lfloor(n-1-5j)/2 \rfloor}. \end{equation} These equations are not very simple, so they attracted the attention of several researchers, and different proofs appeared in the literature: Gupta \cite{Gup78}, Hirschhorn \cite{Hir81, Hir02} and, more recently, Brietzke \cite{Bri06} and Cigler \cite{Cig01}. Actually, Andrews generalizes the two identities to every integer $p$, different from 5, but this has not been further considered, at least at our knowledge. In this paper we wish to approach Andrews' generalized sums from the point of view of generating functions and Riordan arrays, hoping to give a deeper insight to the problem. In fact, we'll be able to prove a number of new identities, analogous (but different) to those of Andrews. The paper is organized in the following way. In Section 2, we consider Andrews' generalized sums and observe that they can be transformed into other sums for which we find the corresponding generating functions. By using these results, in Section 3, we compute the rational generating functions of Andrews' generalizations and give several examples for specific values of $p$. Finally, in Section 4, we apply our results to other new combinatorial identities. \section{The generating functions' approach} In analogy to Andrews \cite{And69}, we wish to extend the two sums (\ref{andrews1}) and (\ref{andrews2}) to: \begin{equation} \label{mainsomme1} S^{[p]} _n = \sum_{j=-\infty}^\infty (-1)^j {n \choose \lfloor(n-1-pj)/2 \rfloor}, \end{equation} \begin{equation} \label{mainsomme2} T^{[p]}_n = \sum_{j=-\infty}^\infty (-1)^j {n-1 \choose \lfloor(n-1-pj)/2 \rfloor}, \end{equation} where $p$ is any positive integer number. In the cited papers by Gupta, Hirschborn and Brietzke, it is proven that these sums can be transformed into sums of the type: $$L^{[p,r]}_n = \sum_{k=0}^\infty {2n \choose n+r+pk} \qquad {\rm and} \qquad M^{[p,r]}_n = \sum_{k=0}^\infty {2n+1 \choose n+r+pk};$$ these sums are actually finite and, therefore, let us begin by looking for their generating functions. In the proof of the next theorem we use the Lagrange Inversion Formula (LIF) as in Goulden and Jackson \cite{GJ83}. \begin{theorem}\label{elle2} The generating function of the sum $L^{[p,r]}_n$ is $$L^{[p,r]}(t) = \frac{1}{\sqrt{1-4t}} \left( \frac{1-2t-\sqrt{1-4t}}{2t} \right)^r \Bigm/ \left( 1 - \left( \frac{1-2t-\sqrt{1-4t}}{2t} \right)^p \right)$$ or, alternatively: $$ L^{[p,r]}(t) = \frac{1}{\sqrt{1-4t}} \left( \frac{1-\sqrt{1-4t}}{1+\sqrt{1-4t}} \right)^r \frac{(1+\sqrt{1-4t})^p}{(1+\sqrt{1-4t})^p - (1-\sqrt{1-4t})^p}. $$ \end{theorem} \begin{proof} We apply rule (\ref{Bsum}) in the Introduction: $$\sum_k {2n \choose n+r+pk} = \sum_k {2n \choose n-r-pk} \EQ{(\ref{Bsum})} [t^{n-r}] (1+t)^{2n} \left[ \frac{1}{1-u} \SEP u=t^p \right] =$$ $$= [t^n] (1+t)^{2n} \frac{t^r}{1-t^p} \EQ{LIF} [t^n] \left[ \frac{w^r}{1-w^p} \cdot \frac{1}{1-2t(1+w)} \SEP w=t(1+w)^2 \right] =$$ $$= [t^n] \left[ \frac{w^r}{1-w^p} \cdot \frac{1+w}{1-w} \SEP w = \frac{1-2t-\sqrt{1-4t}}{2t}\right].$$ Now we find $$\frac{1+w}{1-w} = \left( 1 + \frac{1-2t-\sqrt{1-4t}}{2t} \right) \Bigm/ \left( 1 - \frac{1-2t-\sqrt{1-4t}}{2t} \right) = $$ $$=\frac{1 - \sqrt{1-4t}}{\sqrt{1-4t} - (1-4t)} = \frac{1}{\sqrt{1-4t}}$$ and from this the first formula in the assert follows immediately. Alternatively, we can apply rule (\ref{Asum}): $$\sum_k {2n \choose n+r+pk} \EQ{(\ref{Asum})} [t^{2n}] \frac{t^{n+r}}{(1-t)^{n+r+1}} \left[ \frac{1}{1-u} \SEP u = \frac{t^p}{1-t^p} \right] = $$ $$= [t^n] \frac{t^r}{(1-t)^{n+r+1}} \cdot \frac{(1-t)^p}{(1-t)^p - t^p} \EQ{LIF}$$ $$\EQ{LIF} [t^n] \left[ \frac{w^r}{(1-w)^{r+1}} \cdot \frac{(1-w)^p}{(1-w)^p - w^p} \cdot \frac{1-w}{1-2w} \SEP w = \frac{t}{1-w} \right].$$ The following partial computations hold $$w = \frac{1-\sqrt{1-4t}}{2}; \qquad 1-w = \frac{1+\sqrt{1-4t}}{2};$$ $$ \frac{w}{1-w} = \frac {1-\sqrt{1-4t}}{1+\sqrt{1-4t}}; \qquad 1-2w = \frac{1}{\sqrt{1-4t}}.$$ By substituting these values in the previous expression, we immediately find the second desired formula. \end{proof} For the sums $M^{[p,r]}_n$ the result is analogous, and we can state \begin{theorem} The generating function of the sum $M^{[p,r]}_n$ is \begin{equation}\label{forM} M^{[p,r]}(t) = \frac{1+\sqrt{1-4t}}{2t} L^{[p,r]}(t)=L^{[p,r]}(t)+L^{[p,r-1]}(t). \end{equation} \end{theorem} \begin{proof} The proof is analogous to that of the previous theorem: $$\sum_k {2n+1 \choose n+r+pk} = \sum_k {2n+1 \choose n+1-r-pk} \EQ{(\ref{Bsum})} $$ $$ = [t^{n+1-r}] (1+t)^{2n+1} \left[ \frac{1}{1-u} \SEP u=t^p \right] = [t^n] (1+t)^{2n+1} \frac{t^{r-1}}{1-t^p} \EQ{LIF}$$ $$ = [t^n] \left[ \frac{1+w}{w} \frac{w^r} {1-w^p} \cdot \frac{1}{1-2t(1+w)} \SEP w=t(1+w)^2 \right] =$$ $$= [t^n] \left[ \frac{1+w}{w} \frac{w^r}{1-w^p} \cdot \frac{1+w}{1-w} \SEP w = \frac{1-2t- \sqrt{1-4t}}{2t}\right].$$ With respect to $L^{[p,r]}(t)$ we have an extra $(1+w)/w$, the transformation of which is $$\frac{1+w}{w} = \left( 1 + \frac{1-2t-\sqrt{1-4t}}{2t} \right) \Bigm/ \left( \frac{1-2t-\sqrt{1-4t}}{2t} \right) = \frac{1 + \sqrt{1-4t}}{2t};$$ therefore, equation (\ref{forM}) follows. \end{proof} We can now make the following observations: \begin{theorem} \label{teoL} The generating function $\mathcal{L}^{[p,r]}(t) = L^{[p,r]}(t) + L^{[p,p-r]}(t)$ is a rational function. \end{theorem} \begin{proof} For the sake of simplicity, let us set $A = \sqrt{1-4t}$ and write $L^{[p,r]}(A)$ instead of $L^{[p,r]}(t)$ to emphasize the dependence from $A$. We have: $$L^{[p,p-r]}(A) = \frac{1}{A} \left( \frac{1-A}{1+A} \right)^{p-r} \frac{(1+A)^p}{(1+A)^p - (1-A)^p} = $$ $$=\frac{1}{A} \left( \frac{1+A}{1-A} \right)^r \frac{(1-A)^p}{(1+A)^p - (1-A)^p} = L^{[p,r]}(-A).$$ This implies $$\mathcal{L}^{[p,r]}(A) = L^{[p,r]}(A) + L^{[p,r]}(-A) = \mathcal{L}^{[p,r]}(-A),$$ so that $\mathcal{L}^{[p,r]}(t)$ is an even function of $A = \sqrt{1-4t}$, that is, it depends only on $1-4t$ and not on $\sqrt{1-4t}$. This is sufficient to show that $\mathcal{L}^{[p,r]}(t)$ is a rational function. \end{proof} In the same way we obtain \begin{theorem} \label{teoM} The generating function $\mathcal{M}^{[p,r]}(t) = M^{[p,r]}(t) + M^{[p,p-r+1]}(t)$ is a rational function. \end{theorem} \begin{proof} By using the same notations as in the previous theorem, we have $$M^{[p,p-r+1]}(A) = \frac{1+A}{2t} \frac{1-A}{1+A} L^{[p,p-r]}(A) = \frac{1-A}{2t} L^{[p,r]}(-A) = M^{[p,r]}(-A),$$ since by the second equation of Theorem \ref{elle2}: $L^{[p,p+1-r]}(A) = \frac{1-A}{1+A} L^{[p,p-r]}(A)$. So: $$\mathcal{M}^{[p,r]}(A) = M^{[p,r]}(A) + M^{[p,r]}(-A) = \mathcal{M}^{[p,r]}(-A),$$ and $\mathcal{M}^{[p,r]}(A)$ depends only on the square of $\sqrt{1-4t}$. \end{proof} From the two previous theorems, we obtain a limit for the order of the recurrences corresponding to the rational generating functions $\mathcal{L}^{[p,r]}(t)$ and $\mathcal{M}^{[p,r]}(t).$ Since the terms in $\sqrt{1-4t}$ disappear, the degree of the denominator $(1+\sqrt{1-4t})^p-(1- \sqrt{1-4t})^p$ is at most $\lceil p/2 \rceil$ (see Tables \ref{Tab1}--\ref{Tab4}). This improves the results of Cigler \cite{Cig01} about the order of the recurrences. We can now return to the identities of Andrews. If we perform the change of variable $n \mapsto 2n$ we can introduce a new quantity $\widehat{S}^{[p]}_n$: $$\widehat{S}^{[p]}_n = S^{[p]} _{2n} = \sum_{j=-\infty}^\infty (-1)^j {2n \choose \lfloor(2n-1-pj)/2 \rfloor}$$ which represents the elements of even position in the Andrews sequence $(S^{[p]} _n)_{n \in \N}$. We can show the following result: \begin{theorem} The generating function $\widehat{S}^{[p]}(t)$ of the sequence $(\widehat{S}^{[p]}_n)_{n \in \N}$ is $$\widehat{S}^{[p]}(t)=\left\{ \begin{array}{ll} L^{[p,1]}(t) - L^{[p,q-1]}(t) - L^{[p,q+1]}(t) + L^{[p,p-1]}(t), & p = 2q; \\ [2mm] L^{[p,1]}(t) - L^{[p,q]}(t) - L^{[p,q+1]}(t) + L^{[p,p-1]}(t), & p = 2q+1. \end{array} \right.$$ Or, in a single expression: $$\widehat{S}^{[p]}(t) = L^{[p,1]}(t) - L^{[p,\lfloor (p-1)/2 \rfloor)]}(t) - L^{[p,\lfloor (p+2)/2 \rfloor)]}(t) + L^{[p,p-1]}(t)=$$ $$=\mathcal{L}^{[p,1]}(t)-\mathcal{L}^{[p,\lfloor p/2 \rfloor+1]}(t), \qquad p \in \mathbb{N}. $$ \end{theorem} \begin{proof} Let us separate the binomial coefficients according to even and odd values of $j$: $$\widehat{S}^{[p]}_n = \sum_{k=-\infty}^\infty \left( {2n \choose \lfloor(2n-1-2pk)/2 \rfloor} - {2n \choose \lfloor(2n-1-2pk-p)/2 \rfloor} \right).$$ We now distinguish between even and odd values of $p$. \vspace{2mm}\textbf{First case}: $p$ is even: $p = 2q$ $$\left\lfloor {2n-1-2pk \over 2} \right\rfloor = n-1-pk \qquad \left\lfloor {2n-1-2pk-p \over 2} \right\rfloor = n-1-q-pk.$$ Therefore we have $$\widehat{S}^{[p]}_n = \sum_{k=-\infty}^\infty \left( {2n \choose n-1-pk} - {2n \choose n-1-q-pk} \right).$$ We now further divide the sum, distinguishing positive and negative indices. For $k \geq 0$ we have $$\sum_{k=0}^\infty \left( {2n \choose n-1-pk} - {2n \choose n-1-q-pk} \right) =$$ $$= \sum_{k=0}^\infty \left( {2n \choose n+1+pk} - {2n \choose n+(q+1)+pk} \right).$$ For $k<0$ we perform the change of variable $k \mapsto -k-1$, so that $k \geq 0$: $$\sum_{k=0}^\infty \left( {2n \choose n-1+pk+p} - {2n \choose n-1-q+pk+p} \right) =$$ $$= \sum_{k=0}^\infty \left( {2n \choose n+(p-1)+pk} - {2n \choose n+(q-1)+pk} \right).$$ The two sums can be merged together and we find the first formula in the assert. \vspace{2mm} \textbf{Second case}: $p$ is odd: $p = 2q+1$ $$\left\lfloor {2n-1-2pk \over 2} \right\rfloor = n-1-pk \qquad \left\lfloor {2n-1-2pk-2q-1 \over 2}\right\rfloor = n-(q+1)-pk.$$ We proceed as above and find $$\widehat{S}^{[p]}_n = \sum_{k=-\infty}^\infty \left( {2n \choose n-1-pk)} - {2n \choose n-(q+1)-pk} \right).$$ In this case also we distinguish between positive and negative indices. For $k \geq 0$ we have $$\sum_{k=0}^\infty \left( {2n \choose n-1-pk)} - {2n \choose n-1-q-pk} \right) =$$ $$= \sum_{k=0}^\infty \left( {2n \choose n+1+pk)} - {2n \choose n+(q+1)+pk} \right).$$ For $k<0$ we perform the change of variable $k \mapsto -k-1$, so that $k \geq 0$: $$\sum_{k=0}^\infty \left( {2n \choose n-1+pk+p)} - {2n \choose n-1-q+pk+p} \right) =$$ $$= \sum_{k=0}^\infty \left( {2n \choose n+(p-1)+pk)} - {2n \choose n+q+pk} \right);$$ in fact, $p=2q+1$ implies $p-q-1 = 2q+1-q-1 = q$. Therefore we conclude with the second formula in the assert. \end{proof} Let us now examine the sequence $(T^{[p]}_{n})_{n \in \N}$. If we perform the change of variable $n \mapsto 2n+1$ we can introduce a new quantity $\widehat{T}^{[p]}_n$: $$\widehat{T}^{[p]}_n = T^{[p]}_{2n} = \sum_{j=-\infty}^\infty (-1)^j {2n \choose \lfloor(2n-pj)/2 \rfloor}$$ which represents the elements of even position in the Andrews sequence $(T^{[p]}_n)_{n \in \N}$. We can show the following result: \begin{theorem} The generating function $\widehat{T}^{[p]}(t)$ of the sequence $(\widehat{T}^{[p]}_n)_{n \in \N}$ is: $$\widehat{T}^{[p]}(t)=\left\{ \begin{array}{ll} L^{[p,0]}(t) - 2L^{[p,q]}(t) + L^{[p,p]}(t), & p = 2q; \\ [2mm] L^{[p,0]}(t) - L^{[p,q]}(t) - L^{[p,q+1]}(t) + L^{[p,p]}(t), & p = 2q+1. \end{array} \right.$$ Or, in a single expression: $$\widehat{T}^{[p]}(t) = L^{[p,0]}(t) - L^{[p,\lfloor p/2 \rfloor]}(t) - L^{[p,\lfloor (p+1)/2 \rfloor]}(t) + L^{[p,p]}(t)=$$ $$=\mathcal{L}^{[p,0]}(t)-\mathcal{L}^{[p,\lfloor p/2 \rfloor]}(t), \qquad p \in \mathbb{N}. $$ \end{theorem} \begin{proof} The proof proceeds as in the previous theorem; therefore we limit ourselves to give the main points of the reasoning: $$\widehat{T}^{[p]}_n = \sum_{k=-\infty}^\infty \left( {2n \choose \lfloor(2n-2pk)/2 \rfloor} - {2n \choose \lfloor(2n-2pk-p)/2 \rfloor} \right).$$ \vspace{2mm}\textbf{First case}: $p$ is even: $p = 2q$. The denominators are $n-pk$ and $n-pk-q$, respectively. For $k\geq 0$ we have $$\sum_{k=0}^\infty \left( {2n \choose n-pk} - {2n \choose n-q-pk} \right) = \sum_{k=0}^\infty \left( {2n \choose n+pk} - {2n \choose n+q+pk} \right);$$ for $k< 0,$ changing $k \mapsto -k-1:$ $$\sum_{k=0}^\infty \left( {2n \choose n+pk+p} - {2n \choose n-q+pk+p} \right) = $$ $$= \sum_{k=0}^\infty \left( {2n \choose n+p+pk} - {2n \choose n+q+pk} \right).$$ This implies the first formula in the assert. \vspace{2mm}\textbf{Second case}: $p$ is odd: $p = 2q+1$. The denominators are $n-pk$ and $n-pk-q-1$, respectively. For $k\geq 0$ we have $$\sum_{k=0}^\infty \left( {2n \choose n-pk} - {2n \choose n-q-1-pk} \right) =$$ $$= \sum_{k=0}^\infty \left( {2n \choose n+pk} - {2n \choose n+q+1+pk} \right);$$ for $k< 0,$ changing $k \mapsto -k-1:$ $$\sum_{k=0}^\infty \left( {2n \choose n+pk+p} - {2n \choose n-q-1+pk+p} \right) = $$ $$= \sum_{k=0}^\infty \left( {2n \choose n+p+pk} - {2n \choose n+q+pk} \right).$$ This implies the second formula in the assert. \end{proof} Let us now consider the elements in odd position. If we perform the change of variable $n \mapsto 2n+1$ we can introduce a new quantity $\overline{S}^{[p]}_n$: $$\overline{S}^{[p]}_n = S^{[p]} _{2n+1} = \sum_{j=-\infty}^\infty (-1)^j {2n+1 \choose \lfloor(2n-pj)/2 \rfloor}.$$ We find \begin{theorem} The generating function $\overline{S}^{[p]}(t)$ of the sequence $(\overline{S}^{[p]}_n)_{n \in \N}$ is $$\overline{S}^{[p]}(t)=\left\{ \begin{array}{ll} M^{[p,1]}(t) - M^{[p,q]}(t) - M^{[p,q+1]}(t) + M^{[p,p]}(t), & p = 2q; \\ [2mm] M^{[p,1]}(t) - M^{[p,q]}(t) - M^{[p,q+2]}(t) + M^{[p,p]}(t); & p = 2q+1. \end{array} \right.$$ Or, in a single expression: $$\overline{S}^{[p]}(t) = M^{[p,1]}(t) - M^{[p,\lfloor p/2 \rfloor]}(t) - M^{[p,\lfloor (p+3)/2 \rfloor]}(t) + M^{[p,p]}(t)=$$ $$=\mathcal{M}^{[p,1]}(t)-\mathcal{M}^{[p,\lfloor p/2 \rfloor]}(t), \qquad p \in \mathbb{N}. $$ \end{theorem} \begin{proof} The proof proceeds as in the previous theorems: $$\overline{S}^{[p]}_n = \sum_{k=-\infty}^\infty \left( {2n+1 \choose \lfloor(2n-2pk)/2 \rfloor} - {2n+1 \choose \lfloor(2n-2pk-p)/2 \rfloor} \right).$$ \vspace{2mm}\textbf{First case}: $p$ is even: $p = 2q$. The denominators are $n-pk$ and $n-pk-q$, respectively. For $k\geq 0$ we have $$\sum_{k=0}^\infty \left( {2n+1 \choose n-pk} - {2n+1 \choose n-q-pk} \right) =$$ $$= \sum_{k=0}^\infty \left( {2n+1 \choose n+1+pk} - {2n+1 \choose n+q+1+pk} \right);$$ for $k< 0,$ changing $k \mapsto -k-1:$ $$\sum_{k=0}^\infty \left( {2n+1 \choose n+pk+p} - {2n+1 \choose n-q+pk+p} \right) =$$ $$= \sum_{k=0}^\infty \left( {2n+1 \choose n+p+pk} - {2n+1 \choose n+q+pk} \right).$$ This implies the first formula in the assert. \vspace{2mm}\textbf{Second case}: $p$ is odd: $p = 2q+1$. The denominators are $n-pk$ and $n-pk-q-1$, respectively. For $k\geq 0$ we have $$\sum_{k=0}^\infty \left( {2n+1 \choose n-pk} - {2n+1 \choose n-q-1-pk} \right) =$$ $$= \sum_{k=0}^\infty \left( {2n+1 \choose n+1+pk} - {2n+1 \choose n+q+2+pk} \right);$$ for $k< 0,$ changing $k \mapsto -k-1:$ $$\sum_{k=0}^\infty \left( {2n+1 \choose n+pk+p} - {2n+1 \choose n-q-1+pk+p} \right) =$$ $$= \sum_{k=0}^\infty \left( {2n+1 \choose n+p+pk} - {2n+1 \choose n+q+pk} \right).$$ This implies the second formula in the assert. \end{proof} Finally, let us consider the sequence $(T^{[p]}_{n})_{n \in \N}$. If we perform the change of variable $n \mapsto 2n+2$ we can introduce a new quantity $\overline{T}^{[p]}_n$: $$\overline{T}^{[p]}_n = T^{[p]}_{2n+1} = \sum_{j=-\infty}^\infty (-1)^j {2n+1 \choose \lfloor(2n+1-pj)/2 \rfloor}.$$ We find \begin{theorem} The generating function $\overline{T}^{[p]}(t)$ of the sequence $(\overline{T}^{[p]}_n)_{n \in \N}$ is $$\overline{T}^{[p]}(t)=\left\{ \begin{array}{ll} M^{[p,1]}(t) - M^{[p,q]}(t) - M^{[p,q+1]}(t) + M^{[p,p]}(t), & p = 2q; \\ [2mm] M^{[p,1]}(t) - 2M^{[p,q+1]}(t) + M^{[p,p]}(t), & p = 2q+1. \end{array} \right.$$ Or, in a single expression: $$\overline{T}^{[p]}(t) = M^{[p,1]}(t) - M^{[p,\lfloor (p+1)/2 \rfloor]}(t) - M^{[p,\lfloor (p+2)/2 \rfloor]}(t) + M^{[p,p]}(t) =$$ $$=\mathcal{M}^{[p,1]}(t)-\mathcal{M}^{[p,\lfloor p/2 \rfloor+1]}(t), \qquad p \in \mathbb{N}. $$ \end{theorem} \begin{proof} The proof proceeds as in the previous theorems: $$\overline{T}^{[p]}_n = \sum_{k=-\infty}^\infty \left( {2n+1 \choose \lfloor(2n+1-2pk)/2 \rfloor} - {2n+1 \choose \lfloor(2n+1-2pk-p)/2 \rfloor} \right).$$ \vspace{2mm}\textbf{First case}: $p$ is even: $p = 2q$. The denominators are $n-pk$ and $n-pk-q$, respectively. For $k\geq 0$ we have $$\sum_{k=0}^\infty \left( {2n+1 \choose n-pk} - {2n+1 \choose n-q-pk} \right) =$$ $$= \sum_{k=0}^\infty \left( {2n+1 \choose n+1+pk} - {2n+1 \choose n+q+1+pk} \right);$$ for $k< 0,$ changing $k \mapsto -k-1:$ $$\sum_{k=0}^\infty \left( {2n+1 \choose n+pk+p} - {2n+1 \choose n-q+pk+p} \right) =$$ $$=\sum_{k=0}^\infty \left( {2n+1 \choose n+p+pk} - {2n+1 \choose n+q+pk} \right).$$ This implies the first formula in the assert. \vspace{2mm}\textbf{Second case}: $p$ is odd: $p = 2q+1$. The denominators are $n-pk$ and $n-pk-q$, respectively. For $k\geq 0$ we have $$\sum_{k=0}^\infty \left( {2n+1 \choose n-pk} - {2n+1 \choose n-q-pk} \right) =$$ $$= \sum_{k=0}^\infty \left( {2n+1 \choose n+1+pk} - {2n+1 \choose n+q+1+pk} \right);$$ for $k< 0,$ changing $k \mapsto -k-1:$ $$\sum_{k=0}^\infty \left( {2n+1 \choose n+pk+p} - {2n+1 \choose n-q+pk+p} \right) =$$ $$= \sum_{k=0}^\infty \left( {2n+1 \choose n+p+pk} - {2n+1 \choose n+q+1+pk} \right).$$ This implies the second formula in the assert. \end{proof} \section{Andrews' generalizations} By using the results of the previous section we find the generating functions for the sums (\ref{mainsomme1}) and \ref{mainsomme2}) for any $p\in \mathbb{N}.$ In fact we have \begin{theorem} \label{abs} The generating functions $S^{[p]}(t)$ and $T^{[p]}(t)$ of the sequences $(S^{[p]}_n)_{n \in \N}$ and $(T^{[p]}_n)_{n \in \N}$ are rational and are given by the following formulas: $$S^{[p]}(t)=\widehat{S}^{[p]}(t^2)+t\overline{S}^{[p]}(t^2), $$ $$T^{[p]}(t)=t\widehat{T}^{[p]}(t^2)+t^2\overline{T}^{[p]}(t^2). $$ \end{theorem} Tables \ref{Tab1} and \ref{Tab2} summarize the generating functions corresponding to Theorem \ref{abs} for $p \leq 8.$ These expressions can be easily obtained by any system of symbolic computation as Maple. In particular, for $p=5$ we find again formulas (\ref{andrews1}) and (\ref{andrews2}), as expected. In the tables, we give a reference to the same (or simply related) sequence in the Encyclopedia of Integer Sequences (EIS) \cite{IS}. \begin{table}[H] \small $$ \begin{array}{|c|c|c|} \hline p & S^{[p]}(t) & \emph{EIS} \\ [4mm] \hline & & \\ 2 & -1 & \\ [4mm] 3 & 0 & \\ [4mm] 4 & \displaystyle{t \over 1-2t^2}=t+2t^3+4t^5+8t^7+16t^9+\cdots & \seqnum{A000079} \\[4mm] 5 & \displaystyle{t \over 1-t-t^2}=t+t^2+2t^3+3t^4+5t^5+8t^6+13t^7+\cdots & \seqnum{A000045} \\ [4mm] 6 & \displaystyle{t(1+t) \over 1-3t^2}=t+t^2+3t^3+3t^4+9t^5+9t^6+27t^7+27t^8+\cdots & {\seqnum{A108411} \atop \seqnum{A000244}} \\ [4mm] 7 & \displaystyle{t \over 1-t-2t^2+t^3}=t+t^2+3t^3+4t^4+9t^5+14t^6+28t^7+\cdots & \seqnum{A006053} \\ [4mm] 8 & \displaystyle{t(1+t-t^2) \over 1-4t^2+2t^4}=t+t^2+3t^3+4t^4+10t^5+14t^6+34t^7+\cdots & \seqnum{A121720} \\ \hline \end{array} $$ \caption{\label{Tab1}Function $S^{[p]}(t)$ for $p\leq 8$} \end{table} \begin{table}[H] \small $$ \begin{array}{|c|c|c|} \hline p & T^{[p]}(t) & \emph{EIS} \\ [4mm] \hline & & \\ 2 & t & \\ [4mm] 3 & \displaystyle{t \over 1-t}=t+t^2+t^3+t^4+\cdots & \seqnum{A000012} \\[4mm] 4 & \displaystyle{t(1+t) \over 1-2t^2}=t+t^2+2t^3+2t^4+4t^5+4t^6+\cdots & \seqnum{A016116} \\[4mm] 5 & \displaystyle{t \over 1-t-t^2}=t+t^2+2t^3+3t^4+5t^5+8t^6+13t^7+\cdots & \seqnum{A000045} \\[4mm] 6 & \displaystyle{t(1+t-t^2) \over 1-3t^2}=t+t^2+2t^3+3t^4+6t^5+9t^6+18t^7+27t^8+\cdots & {\seqnum{A038754} \atop \seqnum{A000244}} \\[4mm] 7 & \displaystyle{t(1-t^2) \over 1-t-2t^2+t^3}=t+t^2+2t^3+3t^4+6t^5+10t^6+19t^7+33t^8+\cdots & \seqnum{A028495} \\ [4mm] 8 & \displaystyle{t(1+t-2t^2-t^3) \over 1-4t^2+2t^4}=t+t^2+2t^3+3t^4+6t^5+10t^6+20t^7+\cdots & \seqnum{A030436}\\ \hline \end{array} $$ \caption{\label{Tab2}Function $T^{[p]}(t)$ for $p\leq 8$} \end{table} \section{Some new identities} Formulas (\ref{mainsomme1}) and (\ref{mainsomme2}) concern alternating sums: what can we say about the corresponding non-alternating sums: $$\mathbf{S}^{[5]}_n = \sum_{j=-\infty}^\infty {n \choose \lfloor(n-1-5j)/2 \rfloor} \quad {\rm and} \quad \widehat{\mathbf{T}}^{[5]}_n = \sum_{j=-\infty}^\infty {n-1 \choose \lfloor(n-1-5j)/2 \rfloor}?$$ Let us begin with the first sum; clearly, the generating functions of even and odd positioned elements are $$\widehat{\mathbf{S}}^{[5]}(t) = L^{[5,1]}(t) + L^{[5,2]}(t) + L^{[5,3]}(t) + L^{[5,4]}(t)$$ $$\overline{\mathbf{S}}^{[5]}(t) = M^{[5,1]}(t) + M^{[5,2]}(t) + M^{[5,4]}(t) + M^{[5,5]}(t).$$ By using Maple, we obtain $$\widehat{\mathbf{S}}^{[5]}(t) = {\frac {t-2\,{t}^{2}}{1-7\,t+13\,{t}^{2}-4\,{t}^{3}}} \qquad \qquad \overline{\mathbf{S}}^{[5]}(t) = {\frac {1-3\,t}{1-7\,t+13\,{t}^{2}-4\,{t}^{3}}};$$ the complete generating function is therefore: $$\mathbf{S}^{[5]}(t) = \widehat{\mathbf{S}}^{[5]}(t^2) + t\,\overline{\mathbf{S}}^ {[5]}(t^2) = {\frac {t}{1-t-3\,{t}^{2}+2\,{t}^{3}}} = \frac{1}{5} \left( \frac{2}{1-2t} - \frac{2+t}{1+t-t^2} \right),$$ where we performed a partial fraction expansion. We recognize the generating function of the Fibonacci numbers with alternating signs, and so we have the closed formula: $$\mathbf{S}^{[5]}_n = \frac{2^{n+1} + (-1)^n (F_n - 2F_{n+1})}{5}.$$ For what concerns the second sum, we have $$\mathbf{T}^{[5]}(t) = L^{[5,0]}(t) + L^{[5,2]}(t) + L^{[5,3]}(t) + L^{[5,5]}(t)$$ $$\overline{\mathbf{T}}^{[5]}(t) = M^{[5,1]}(t) + 2M^{[5,3]}(t) + M^{[5,5]}(t).$$ By passing these expressions to Maple, we obtain $$\mathbf{T}^{[5]}(t) = \frac{1-5t+6t^2}{1-7t+13t^2-4t^3} \qquad \qquad \overline{\mathbf{T}}^{[5]}(t) = \frac{1-4t+4t^2}{1-7t+13t^2-4t^3};$$ the complete generating function is therefore: $$\widehat{\mathbf{T}}^{[5]}(t) = 1+ t^2\,\mathbf{T}^{[5]}(t^2) + t\,\overline{\mathbf{T}}^ {[5]}(t^2) =$$ $$= {\frac {1-3t^2}{1-t-3\,{t}^{2}+2\,{t}^{3}}} = \frac{1}{5} \left( \frac{1}{1-2t} + \frac{4+7t}{1+t-t^2} \right),$$ where we performed a partial fraction expansion. We have the closed formula: $$\widehat{\mathbf{T}}^{[5]}_n = \frac{2^n + (-1)^n (4F_{n+1} - 7F_n)}{5}.$$ Tables \ref{Tab3} and \ref{Tab4} summarize the generating functions corresponding to the non-alternating versions $\mathbf{S}^{[p]}_n$ and $\mathbf{T}^{[p]}_n$ of the sums (\ref{mainsomme1}) and (\ref{mainsomme2}) with $p \leq 8.$ \begin{table}[H] \small $$ \begin{array}{|c|c|c|} \hline p & \mathbf{S}^{[p]}(t) & \emph{EIS} \\ [4mm] \hline & & \\ 2 & \displaystyle{1 \over 1-2t}=1+2t+4t^2+8t^3+16t^4+32t^5+\cdots & \seqnum{A000079} \\ [4mm] 3 & \displaystyle{2t \over 1-t-2t^2}=2t+2t^2+6t^3+10t^4+22t^5+42t^6+\cdots & \seqnum{A001045} \\ [4mm] 4 & \displaystyle{t \over 1-2t}=t+2t^2+4t^3+8t^4+16t^5+32t^6+\cdots & \seqnum{A000079} \\[4mm] 5 & \displaystyle{t \over 1-t-3t^2+2t^3}=t+t^2+4t^3+5t^4+15t^5+22t^6+\cdots & \seqnum{A084179} \\ [4mm] 6 & \displaystyle{t \over 1-t-2t^2}=t+t^2+3t^3+5t^4+11t^5+21t^6+\cdots & \seqnum{A001045} \\ [4mm] 7 & \displaystyle{t(1-2t^2) \over 1-t-4t^2+3t^3+2t^4}=t+t^2+3t^3+4t^4+11t^5+16t^6\cdots & \\ [4mm] 8 & \displaystyle{t(1-t-t^2) \over 1-2t-2t^2+4t^3}=t+t^2+3t^3+4t^4+10t^5+16t^6+36t^7+\cdots & \\ \hline \end{array} $$ \caption{\label{Tab3}Function $\mathbf{S}^{[p]}(t)$ for $p\leq 8$} \end{table} \begin{table}[H] \small $$ \begin{array}{|c|c|c|} \hline p & \mathbf{T}^{[p]}(t) & \emph{EIS} \\ [4mm] \hline & & \\ 2 & \displaystyle{t \over 1-2t}=t+2t^2+4t^3+8t^4+16t^5+32t^6+\cdots & \seqnum{A000079} \\ [4mm] 3 & \displaystyle{t \over 1-t-2t^2}=t+t^2+3t^3+5t^4+11t^5+21t^6+\cdots & \seqnum{A001045} \\ [4mm] 4 & \displaystyle{t(1-t) \over 1-2t}=t+t^2+2t^3+4t^4+8t^5+16t^6+\cdots & \seqnum{A000079} \\[4mm] 5 & \displaystyle{t(1-2t^2) \over 1-t-3t^2+2t^3}=t+t^2+2t^3+4t^4+7t^5+12t^6+\cdots & \seqnum{A099163} \\ [4mm] 6 & \displaystyle{t(1-t-t^2) \over 1-2t-t^2+2t^3}=t+t^2+2t^3+3t^4+6t^5+11t^6+\cdots & \seqnum{A005578} \\ [4mm] 7 & \displaystyle{t(1-3t^2) \over 1-t-4t^2+3t^3+2t^4}=t+t^2+2t^3+3t^4+6t^5+10t^6+21t^7+\cdots & \\ [4mm] 8 & \displaystyle{t(1-t-2t^2+t^3) \over 1-2t-2t^2+4t^3}=t+t^2+2t^3+3t^4+6t^5+10t^6+20t^7+\cdots & \\ \hline \end{array} $$ \caption{\label{Tab4}Function $ \mathbf{T}^{[p]}(t)$ for $p\leq 8$} \end{table} In both cases, for $p=7,8,$ we did not find a simple relation with a sequence in \cite {IS}. However, for $p=8$ we have the following explicit formulas: $$\mathbf{S}^{[8]}_n={1 \over 4}2^n+ \left\{ \begin{array}{ll} {1 \over 2}2^{(n-1)/2}, & \mbox{if } n \mbox{ is odd;} \\ [2mm] 0, & \mbox{otherwise.} \end{array} \right. $$ $$\mathbf{R}^{[8]}_n={1 \over 8}2^n+{1 \over 4} \left\{ \begin{array}{ll} 2^{n/2}, & \mbox{if } n \mbox{ is even;} \\ [2mm] 2^{(n-1)/2+1}, & \mbox{otherwise.} \end{array} \right. $$ We note that the first formula is valid for $n>0,$ while the second one for $n>1.$ \section{Conclusions} We have shown how Andrews' formulas can be obtained and generalized in terms of generating functions. We also obtained results for non-alternating sums, and it is easily seen that many other identities could be proved by performing suitable linear combinations of the rational generating functions considered in Theorems \ref{teoL} and \ref{teoM}. \section{Acknowledgements} We wish to thank Antony Sofo and an anonymous referee for their useful comments and suggestions. \begin{thebibliography}{1} \bibitem{And69} G.~H. Andrews. \newblock Some formulae for the {F}ibonacci sequence with generalizations. \newblock {\em Fibonacci Quart.} \textbf{7} (1969), 113--130. \bibitem{Bri06} E.~M. Brietzke. \newblock Generalization of an identity of {A}ndrews. \newblock {\em Fibonacci Quart.} \textbf{44} (2006), 166--171. \bibitem{Cig01} J. Cigler. \newblock Recurrences for some sequences of binomial sums. \newblock {\em \"Osterreich. Akad. Wiss. Math.-Natur. Kl. Sitzungsber. II} \textbf{210} (2001), 61--83. \bibitem{GJ83} I.~P. Goulden and D.~M. Jackson. \newblock {\em Combinatorial {E}numeration}. \newblock Wiley, New York, 1983. \bibitem{Gup78} H.~Gupta. \newblock The {A}ndrews formula for {F}ibonacci numbers. \newblock {\em Fibonacci Quart.} \textbf{16} (1978), 552--555. \bibitem{Hir81} M.~D. Hirschhorn. \newblock The {A}ndrews formula for {F}ibonacci numbers. \newblock {\em Fibonacci Quart.} \textbf{19} (1981), 1--2. \bibitem{Hir02} M.~D. Hirschhorn. \newblock Solution to problem 1621. \newblock {\em Math. Mag.} \textbf{75} (2002), 149--250. \bibitem{IS} N.~Sloane. \newblock On-line {E}ncyclopedia of {I}nteger {S}equences. \newblock \href{http://www.research.att.com/~njas/sequences}{\tt http://www.research.att.com/\char'176njas/sequences}. \bibitem{Spr94} R.~Sprugnoli. \newblock Riordan arrays and combinatorial sums. \newblock {\em Discrete Math.} \textbf{132} (1994), 267--290. \end{thebibliography} \vspace{1cm} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A15; Secondary 05A19. \noindent \emph{Keywords: } Andrews sums, Fibonacci numbers, generating functions. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000012}, \seqnum{A000045}, \seqnum{A000079}, \seqnum{A000129}, \seqnum{A000225}, \seqnum{A000244}, \seqnum{A001045}, \seqnum{A005578}, \seqnum{A006053}, \seqnum{A016116}, \seqnum{A028495}, \seqnum{A030436}, \seqnum{A038754}, \seqnum{A084179}, \seqnum{A099163}, \seqnum{A108411}, and \seqnum{A121720}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received July 13 2007; revised version received September 21 2007. Published in {\it Journal of Integer Sequences}, September 23 2007. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}