\documentclass[12pt]{amsart}

%\usepackage{amsmath}
\newtheorem{theorem}{Theorem}


\begin{document}

\title{On a recursive formula for binomial coefficients}
\author{G. Berkolaiko}
\address{Department of Mathematics, Texas A\&M University, College
  Station, TX 77845-3368, U.S.A.}

\begin{abstract}
  We demonstrate that the binomial coefficients $B(n,k)$ satisfy the
  recursive formula
  \begin{equation*}
    B(n,k) = B(n-1, k-1) + B(n-1, k).
  \end{equation*}
  Moreover, we prove that together with the initial conditions $B(n,0)
  = B(n,n) = 1$ our formula can be used to calculate all binomial
  coefficients.
\end{abstract}

\maketitle

\section{Introduction}

The binomial coefficients $B(n,k)$ arise in the expansions of the
polynomial $(a+b)^n$.  In fact, $B(n,k)$ is the coefficient of the
term $a^kb^{n-k}$ is the said expansion.  The case $n=2$ dates back to
Euclid who expressed it in geometric terms \cite{Euclid}.  The general formula
\begin{equation}
  \label{eq:Newtons}
  B(n,k) = \frac{n!}{k!(n-k)!}  \qquad n\geq 0,\ 0 \leq k \leq n, 
\end{equation}
is attributed to Newton who reportedly published it on his gravestone,
although this claim is disputed by some authors \cite{Cajori}.

Formula (\ref{eq:Newtons}), although explicit, is not very convenient
in abacus computations, as one has to multiply and divide large
numbers.  In the present manuscript we prove that $B(n,k)$ satisfy certain
recurrence relation which, together with few initial values, reduce
the task of computing the binomial coefficients to a series of
additions.  Our main theorem can be formulated as follows

\begin{theorem}
  The binomial coefficients $B(n,k)$ defined by formula
  (\ref{eq:Newtons}) satisfy
  \begin{equation}
    \label{eq:recur}
    B(n,k) = B(n-1, k-1) + B(n-1, k), \qquad 1 \leq k \leq n-1.
  \end{equation}
  Together with the initial conditions $B(n,0)=B(n,n)=1$ recursion
  (\ref{eq:recur}) completely specifies the binomial coefficients.
\end{theorem}

\section{Proof of the main result}

\begin{proof}
  Using equation~(\ref{eq:Newtons}) we obtain
  \begin{align*}
    B(n-1,k-1) &= \frac{(n-1)!}{(k-1)!(n-k)!} =
    \frac{(n-1)!}{(k-1)!(n-k-1)!}\frac1{n-k}, \\
    B(n-1,k) &= \frac{(n-1)!}{k!(n-k-1)!} =
    \frac{(n-1)!}{(k-1)!(n-k-1)!}\frac1{k}.
  \end{align*}
  Adding the two together we calculate
  \begin{align*}
    B(n-1,k-1) + B(n-1,k) &= \frac{(n-1)!}{(k-1)!(n-k-1)!} 
    \left(\frac1{n-k} + \frac1k\right) \\
    &= \frac{(n-1)!}{(k-1)!(n-k-1)!} \frac{n}{k(n-k)} \\ 
    &= \frac{n!}{k!(n-k)!}\\
    &= B(n,k).
  \end{align*}
  This proves recursion~(\ref{eq:recur}).  We notice that the
  right-hand side of (\ref{eq:recur}) only makes sense when $1 \leq k
  \leq n-1$, since the original binomial $B(n,k)$ is only defined when
  $0 \leq k \leq n$.

  To demonstrate that the above recursion fully specifies the binomial
  coefficients when supplemented with the initial conditions
  $B(n,0)=B(n,n)=1$ we employ induction on $n$.  For $n=0$ and $n=1$
  all the binomial coefficients are specified by the initial data:
  \begin{equation*}
    B(0,0) = 1, \qquad B(1,0)=1, \qquad B(1,1)=1.
  \end{equation*}
  Assume all values for $n=N-1$ have been found.  Then we can find
  values of $B(N, k)$ for $k=1,\ldots, N-1$ from the recursion.  For
  the remaining values of $k$, $k=0$ and $k=N$, the values are again
  given by the initial data:
  \begin{equation*}
    B(N,0) = 1, \qquad B(N,N)=1.
  \end{equation*}
  This completes the proof of the theorem.
\end{proof}

\section{Conclusions and Outlook}

We have shown that the binomial coefficients satisfy a recurrence
relation which can be used to speed up abacus calculations.  Our
approach raises an important question: what can be said about
the solution of the recurrence (\ref{eq:recur}) if the initial data is
different?  For example, if $B(n, 0)=1$ and $B(n,n)=-1$, do
coefficients $B(n,k)$ stay bounded for all $n$ and $k$?

\section*{Acknowledgment}
Useful discussions with B.~Pascal regarding arrangements of $B(n,k)$
in a hexagonal pattern are gratefully acknowledged.

\begin{thebibliography}{9}
\bibitem{Euclid} Euclid, {\it Elements}, 34th ed., Macedonian Press,
  Thebes, 1976.
\bibitem{Cajori} F.~Cajori, {\it Was the binomial theorem engraven on
    Newton's monument?}, Bull.\ Amer.\ Math.\ Soc. {\bf 1} (1894),
  52--54 .
\end{thebibliography}


\end{document}
