\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 A Note on Nested Sums } \vskip 1cm \large Steve Butler\footnote{Supported by an NSF postdoctoral fellowship.} \\ Department of Mathematics\\ UCLA\\ Los Angeles, CA 90095\\ USA \\ \href{mailto:butler@math.ucla.edu}{\tt butler@math.ucla.edu}\\ \ \\ Pavel Karasik\\ Santa Monica College\\ Santa Monica, CA 90405\\ USA\\ \href{mailto:Karasik__Pavel@smc.edu}{\tt Karasik\_Pavel@smc.edu} \\ \end{center} \vskip .2 in \begin{abstract} We consider several nested sums, and show how binomial coefficients, Stirling numbers of the second kind and Gaussian binomial coefficients can be written as nested sums. We use this to find the rate of growth for diagonals of Stirling numbers of the second kind, as well as another proof of a known identity for Gaussian binomial coefficients. \end{abstract} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{defin}[theorem]{Definition} \newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}} \newtheorem{examp}[theorem]{Example} \newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}} \newtheorem{rema}[theorem]{Remark} \newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}} \section{Introduction} In this note we are interested in looking at nested sums and finding simple closed form expressions for them. Our motivation for looking at these sums was the following identity. \begin{eqnarray}\label{eq:basic} \sum_{k_p=0}^n\sum_{k_{p-1}=0}^{k_p}\cdots\sum_{k_1=0}^{k_2}1={n+p\choose n} \end{eqnarray} One way to see this is to note that on the left hand side we count the number of occurrences of $n\geq k_p\geq k_{p-1}\geq\cdots\geq k_1\geq 0$. There is a one-to-one correspondence between these and nonnegative $(p+1)$-tuples which sum to $n$, i.e., $(n-k_p,k_p-k_{p-1},\ldots,k_1-0)$. The number of such tuples is the same as the number of ways to put $n$ identical balls into $p+1$ distinct bins. This can be counted by arranging the $n$ balls and $p$ dividers between bins in a row which can be done in ${n+p\choose n}$, the right hand side. More generally one can ask for closed formed expressions for sums of the form \[ \sum_{k_p=0}^n\sum_{k_{p-1}=0}^{k_p}\cdots\sum_{k_1=0}^{k_2}f(k_1,\ldots,k_p). \] We will show in Section~\ref{sec:binomial} that when $f(k_1,\ldots,k_p)={k_i\choose j}$ the sum has a simple closed expression, and in Section~\ref{sec:prod} we consider functions of the form $f(k_1,\ldots,k_p)=g(k_1)\cdots g(k_p)$ and show how to get Stirling numbers of the second kind, the central factorial numbers and Gaussian binomial coefficients as nested sums. \section{Sums involving binomial coefficients}\label{sec:binomial} When the function being summed is a binomial coefficient then the sum has a simple closed form. \begin{lemma}\label{lem:binomial} For $1\leq i\leq p$ and $j\geq 0$ we have \[ \sum_{k_p=0}^n\sum_{k_{p-1}=0}^{k_p}\cdots\sum_{k_1=0}^{k_2}{k_i\choose j}={j+i-1\choose i-1}{n+p\choose p+j}. \] \end{lemma} For the proof of Lemma~\ref{lem:binomial} we will make use of two basic identities for binomial coefficients (see~\cite{concrete}). The first is a way to rewrite the product of binomial coefficients, \begin{equation}\label{eq1} {q\choose b}{q+d\choose d}={b+d\choose d}{q+d\choose b+d}, \end{equation} and the second is a way to sum on the upper index \begin{equation}\label{eq2} \sum_{k=0}^m{k+n\choose d}={m+n+1\choose d+1}, \end{equation} where more generally we can start our sum at any $k=a$ for $a\leq d-n$. \begin{proof}[Proof of Lemma~\ref{lem:binomial}] We have \begin{eqnarray*} \sum_{k_p=0}^n\sum_{k_{p-1}=0}^{k_p}\cdots\sum_{k_1=0}^{k_2}{k_i\choose j} &=&\sum_{k_p=0}^n\sum_{k_{p-1}=0}^{k_p}\cdots\sum_{k_i=0}^{k_{i+1}}{k_i\choose j}\sum_{k_{i-1}=0}^{k_i}\cdots\sum_{k_1=0}^{k_2}1\\ &=&\sum_{k_p=0}^n\sum_{k_{p-1}=0}^{k_p}\cdots\sum_{k_i=0}^{k_{i+1}}{k_i\choose j}{k_i+i-1\choose i-1}\\ &=&\sum_{k_p=0}^n\sum_{k_{p-1}=0}^{k_p}\cdots\sum_{k_i=0}^{k_{i+1}}{j+i-1\choose i-1}{k_i+i-1\choose i-1+j}\\ &=&{j+i-1\choose i-1}\sum_{k_p=0}^n\sum_{k_{p-1}=0}^{k_p}\cdots\sum_{k_i=0}^{k_{i+1}}{k_i+i-1\choose i-1+j}\\ &=&{j+i-1\choose i-1}\sum_{k_p=0}^n\sum_{k_{p-1}=0}^{k_p}\cdots\sum_{k_{i+1}=0}^{k_{i+2}}{k_{i+1}+i\choose i+j}\\ &=&\cdots\\ &=&{j+i-1\choose i-1}{n+p\choose p+j}, \end{eqnarray*} where we used \eqref{eq:basic} in going from the first to the second line, \eqref{eq1} in going from the second to the third line, and repeated application of \eqref{eq2} from the fifth line down. \end{proof} \begin{theorem} For $j\geq 0$ we have \begin{eqnarray} \sum_{k_p=0}^n\sum_{k_{p-1}=0}^{k_p}\cdots\sum_{k_1=0}^{k_2}\bigg({k_1\choose j}+{k_2\choose j}+\cdots +{k_p\choose j}\bigg)&=&{p\over j+1}{n\choose j}{n+p\choose n},\label{eq:corA} \end{eqnarray} \end{theorem} \begin{proof} We have \begin{multline*} \sum_{k_p=0}^n\sum_{k_{p-1}=0}^{k_p}\cdots\sum_{k_1=0}^{k_2}\bigg({k_1\choose j}+{k_2\choose j}+\cdots +{k_p\choose j}\bigg)~=~\sum_{q=1}^p\bigg(\sum_{k_p=0}^n\sum_{k_{p-1}=0}^{k_p}\cdots\sum_{k_1=0}^{k_2}{k_q\choose j}\bigg)\\ ~=~\sum_{q=1}^p{j+q-1\choose q-1}{n+p\choose p+j} ~=~{n+p\choose p+j}\sum_{q=1}^p{j+q-1\choose j} ~=~{n+p\choose p+j}{j+p\choose j+1}\\ ~=~{p\over j+1}{n\choose j}{n+p\choose n}.\qedhere \end{multline*} \end{proof} Putting $j=1$ into \eqref{eq:corA} we have \[ \sum_{k_p=0}^n\sum_{k_{p-1}=0}^{k_p}\cdots\sum_{k_1=0}^{k_2}\big(k_1+k_2+\cdots+k_p\big)={pn\over2}{n+p\choose n}. \] When $p=2$ this generates the sequence \seqnum{A027480} and when $p=3$ this generates the sequence \seqnum{A033487} in Sloane's {\it Encyclopedia} \cite{OEIS}. Using that $k_i^2=2{k_i\choose 2}+{k_i\choose 1}$ and \eqref{eq:corA} we have \[ \sum_{k_p=0}^n\cdots\sum_{k_1=0}^{k_2}\big(k_1^2+\cdots+k_p^2\big)=\bigg(2{p\over 3}{n\choose 2}+{p\over 2}{n\choose 1}\bigg){n+p\choose n}={p(2n^2+n)\over6}{n+p\choose n}. \] Since any polynomial can be written as a sum of binomial coefficients we can use Lemma~\ref{lem:binomial} to give a simple expression for functions of the form \[ f(k_1,k_2,\ldots,k_p)=f_1(k_1)+f_2(k_2)+\cdots+f_p(k_p), \] where each $f_i$ is a polynomial. \section{Sums of products}\label{sec:prod} Looking at the proof of Lemma~\ref{lem:binomial} we see that the two main ingredients were the identities which allowed us to write a sum of binomial coefficients as a single binomial coefficient and rewrite a product of two binomial coefficients so that we could pull one term out. When our function is no longer a single binomial coefficient then we might no longer be able to rewrite the product so simply, though the general technique of summing, rewriting and repeating still works. In this section we consider functions of the form $f(k_1,\ldots,k_p)=g(k_1)\cdots g(k_p)$. We begin with the function $g(k)=k$. \begin{theorem}\label{thm:prod} Let $a(p,k)$ be defined by $a(1,1)=1$, $a(1,i)=0$ for $i\neq 1$ and \[ a(p+1,k)=k\big(a(p,k-2)-a(p,k-1)\big)\qquad\mbox{for $p\geq 1$}. \] Then \[ \sum_{k_p=0}^n\sum_{k_{p-1}=0}^{k_p}\cdots\sum_{k_1=0}^{k_2}k_1k_2\cdots k_p= \sum_ka(p,k){n+k\choose k+1}. \] \end{theorem} The first few rows for a table of $a(p,k)$ are given below \[ \begin{array}{c|cccccccccccc} a(p,k)&k{=}1&k{=}2&k{=}3&k{=}4&k{=}5&k{=}6&k{=}7&k{=}8&k{=}9&k{=}10&k{=}11\\ \hline p{=}1&1\\ p{=}2&&-2&3\\ p{=}3&&&6&-20&15\\ p{=}4&&&&-24&130&-210&105\\ p{=}5&&&&&120&-924&2380&-2520&945\\ p{=}6&&&&&&-720&7308&-26432&44100&-34650&10395 \end{array} \] Using this table we can now see, for example, that \[ \sum_{k_4=0}^n\sum_{k_3=0}^{k_4}\sum_{k_2=0}^{k_3}\sum_{k_1=0}^{k_2}k_1k_2k_3k_4= -24{n+4\choose 5}+130{n+5\choose 6}-210{n+6\choose 7}+105{n+7\choose 8}. \] Looking at the table we see that the row sums are $1$, this is easily verified by Theorem~\ref{thm:prod} by putting $n=1$ into both sides. Similarly it is easy to see that the terms on the diagonals are the signed factorials and the rightmost term in the $p$th row is the product of the first $p$ odd numbers. The values in the rows are closely related to \seqnum{A111999} in Sloane's {\it Encyclopedia} \cite{OEIS} which are defined with a similar recurrence (though in that table the rows are written in reverse order and shifted to the left as well as differing in the signs). \begin{proof}[Proof of Theorem~\ref{thm:prod}] We proceed by induction on $p$. For $p=1$ we have by a simple application of \eqref{eq2} that \[ \sum_{k_1=0}^nk_1={n+1\choose 2}=\sum_ka(1,k){n+k\choose k+1}. \] So now we assume it is true for $p$ and consider the case $p+1$. By our induction hypothesis we have \begin{equation}\label{eq:tore} \sum_{k_{p+1}=0}^n\sum_{k_p=0}^{k_{p+1}}\cdots\sum_{k_1=0}^{k_2}k_1k_2\cdots k_pk_{p+1}= \sum_{k_{p+1}=0}^nk_{p+1}\sum_ka(p,k){k_{p+1}+k\choose k+1}. \end{equation} Since \begin{eqnarray*} k_{p+1}{k_{p+1}+k\choose k+1} &=&(k_{p+1}+k+1){k_{p+1}+k\choose k+1}-(k+1){k_{p+1}+k\choose k+1}\\ &=&(k+2){k_{p+1}+k+1\choose k+2}-(k+1){k_{p+1}+k\choose k+1}, \end{eqnarray*} we can use this to rewrite \eqref{eq:tore} to get \begin{multline*} \sum_{k_{p+1}=0}^n\sum_ka(p,k)\bigg((k+2){k_{p+1}+k+1\choose k+2}-(k+1){k_{p+1}+k\choose k+1}\bigg)\\ =~\sum_ka(p,k)\bigg((k+2){n+k+2\choose k+3}-(k+1){n+k+1\choose k+2}\bigg)\\ =~\sum_\ell\underbrace{\big(\ell a(p,\ell-2)-\ell a(p,\ell-1)\big)}_{=a(p+1,\ell)}{n+\ell\choose \ell+1}.\qedhere \end{multline*} \end{proof} For fixed values of $p$ this summand produces diagonals for Stirling numbers of the second kind. For instance $p=1,2,3,4,5$ corresponds (respectively) to the sequences \seqnum{A000217}, \seqnum{A001296}, \seqnum{A001297}, \seqnum{A001298} and \seqnum{A112494} in Sloane's {\it Encyclopedia} \cite{OEIS} which are the second, third, fourth, fifth and sixth diagonals in the table of Stirling numbers of the second kind. In general we have for $p\geq 1$ \begin{equation}\label{eq:stirling} \sum_{k_p=0}^n\sum_{k_{p-1}=0}^{k_p}\cdots\sum_{k_1=0}^{k_2}k_1k_2\cdots k_p=\bigg\{{n+p \atop n}\bigg\}. \end{equation} To see this we use the recurrence relationship for the Stirling numbers of the second kind (see \cite{concrete}) to get \begin{multline*} \bigg\{{n\atop k}\bigg\}=k\bigg\{{n-1\atop k}\bigg\}+\bigg\{{n-1\atop k-1}\bigg\}=k\bigg\{{n-1\atop k}\bigg\}+(k-1)\bigg\{{n-2\atop k-1}\bigg\}+\bigg\{{n-2\atop k-2}\bigg\}\\ =~\cdots~=~\sum_{j=0}^kj\bigg\{{n-k-1+j\atop j}\bigg\}. \end{multline*} Now for $p=1$ we have \[ \sum_{k_1=0}^nk_1={n+1\choose 2}=\bigg\{{n+1\atop n}\bigg\}, \] and by induction we have \begin{eqnarray*} \sum_{k_p=0}^n\sum_{k_{p-1}=0}^{k_p}\cdots\sum_{k_1=0}^{k_2}k_1k_2\cdots k_p &=&\sum_{k_p=0}^nk_p\bigg\{{k_p+p-1\atop k_p}\bigg\}\\ &=&\sum_{k_p=0}^nk_p\bigg\{{n+p-n-1+k_p\atop k_p}\bigg\}~=~\bigg\{{n+p\atop n}\bigg\}. \end{eqnarray*} We can also prove this directly. Since $\big\{{n+p\atop n}\big\}$ counts the number of ways to partition $1,2,\ldots,n+p$ into $n$ sets, for each such partition there will be exactly $p$ elements which are {\em not}\/ the first element in their partition. Fix the elements which are not first as \[ 1\le a_1