\documentclass[12pt]{article}
\textwidth= 6.25in
\textheight= 9.0in
\topmargin = -10pt
\evensidemargin=10pt
\oddsidemargin=10pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9 
\newtheorem{proposition}{Proposition}
\usepackage{latexsym}


\begin{document} 
\vspace*{-40pt} 
\centerline{\smalltt INTEGERS: 
 \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 5 
(2005), \#A18} 
\vskip 30pt 

\begin{center}
{\bf TWO VERY SHORT PROOFS OF A COMBINATORIAL IDENTITY}
\vskip 20pt
{\bf Roberto Anglani}\\
{\smallit Dipartimento Interateneo di 
Fisica ``Michelangelo Merlin'', Universit\`{a} degli Studi di Bari,\linebreak Via
 Amendola 173, 70126 Bari,
Italy}\\
{\tt roberto.anglani@ba.infn.it}\\ 
\vskip 10pt
{\bf Margherita Barile\footnote{Partially supported
 by the Italian Ministry of Education, University and 
Research. All surface mail should be sent to the second author.}}\\
{\smallit Dipartimento di Matematica, Universit\`{a} degli Studi 
di Bari, Via E. Orabona 4, 70125 Bari, Italy}\\
{\tt barile@dm.uniba.it}\\ 
\end{center}
\vskip 30pt
\centerline{\smallit Received: 3/21/05, Accepted: 7/31/05,
 Published: 8/8/05}
\vskip 30pt 

\centerline{\bf Abstract}


\noindent
We give two quick elementary proofs of a
 well-known additive formula for the factorial which arises from
 the calculus of finite differences. The first one is purely analytical,
 the second one purely combinatorial.
\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL 
OF COMBINATORIAL NUMBER THEORY \smalltt 5 (2005), \#A18\hfill}

\thispagestyle{empty} 
\baselineskip=15pt 
\vskip 30pt 

\section*{\normalsize 1. Introduction} In Chapter I of his work on 
the calculus of finite differences [1], Boole defines, for all 
real valued function of one real variable $f(x)$, the {\it first difference} of
 $f(x)$ (with respect to the increment 1) as $\Delta f(x)=f(x+1)-f(x)$. He 
then defines, for all integers $n\geq2$,
 the {\it n-th difference} by the recursive 
formula $\Delta^nf(x)=\Delta\Delta^{n-1}f(x).$
This enables him to prove by induction 
(see [1], p.~5, (2)) that, for all positive integers $n$, 
\begin{equation}\label{1}\Delta^nx^n=n!.\end{equation}
\noindent
Later  on  he introduces the operator $E$ by setting $Ef(x)=f(x+1)$,
 so that $\Delta=E-1$ and, consequently (see [1], p.~19, (3)),
$$\Delta^nf(x)=(E-1)^nf(x)=\sum_{i=0}^n{n\choose i}(-1)^{n-i}E^if(x)
=\sum_{i=0}^n{n\choose i}(-1)^{n-i}f(x+i).$$
\noindent In particular one has that
\begin{equation}\label{2} \Delta^nx^n=\sum_{i=0}^n{n\choose i}(-1)^{n-i}(x+i)^n.
\end{equation}
\noindent
{From} (1) and (2) for $x=0$ one can derive the
 identity
\begin{equation}\label{3}n!=\sum_{i=1}^n(-1)^{n-i}{n\choose i}i^n.\end{equation}
\noindent We want to give two alternate proofs of (\ref{3}),
 which have the advantage of being direct, short and 
elementary and, moreover, show the
 close relation of (\ref{3}) to differential calculus and combinatorics. 
\vskip 30pt
\section*{\normalsize 2. The proofs}
\begin{proposition}\label{p1}  For every positive integer $n$, 
$$n!=\sum_{i=1}^n(-1)^{n-i}{n\choose i} i^n.$$
\end{proposition}

\noindent
{\it Proof.} Consider the first order Taylor expansion with Lagrange
 remainder of the exponential function about 0:

$$e^x=1+x+x^2g(x),$$
\noindent
where $g\in C^{\infty}({\bf R})$. We deduce that

\begin{equation}\label{4}(e^x-1)^n=(x+x^2g(x))^n=x^n+x^{n+1}h(x),\end{equation}
for some $h\in C^{\infty}({\bf R})$. The L.H.S. of (\ref{4}) is 
$$\sum_{j=0}^n(-1)^{n-j}{n\choose j}e^{jx}.$$
\noindent
Its $n$-th derivative is
$$\sum_{j=0}^{n}(-1)^{n-j}{n\choose j}j^ne^{jx},$$
\noindent
whose value at 0 is 
$$\sum_{j=1}^{n}(-1)^{n-j}{n\choose j}j^n.$$
This is equal to the value of 
the $n$-th derivative of the R.H.S. of (\ref{4}) at 0, which is $n!$. 
This completes the proof.
\hfill $\Box$

\vskip\baselineskip\noindent
Proposition \ref{p1} admits a different 
 interpretation in terms of enumerative combinatorics. Fix  
an alphabet of $n$ letters. The
 number $n!$ counts the ways of 
forming a word of length $n$
 using all $n$ letters (i.e., a word having
 $n$ different letters), whereas $n^n$ is the 
total number of words of length $n$ (i.e., of all words,
 including the possibility of repeated letters).  
Hence $n^n-n!$ is the number of 
words of length $n$ containing at least 
one repeated letter. Thus we can restate
 Proposition \ref{p1} in the following equivalent form:
\begin{proposition} The number of words of
 length $n$ containing at least one repeated letter 
from an alphabet of $n$ letters is 
\begin{equation}\label{5}-\sum_{i=1}^{n-1}(-1)^{n-i}{n\choose i}i^n.
\end{equation}
\end{proposition}

\noindent
{\it Proof.}
Recall that, for all $i=1,\dots, n-1$, $i^n$ is the number
 of words of length $n$ which can be formed from
 a subset of $i$ letters; ${n\choose i}$ is the
 number of ways of choosing $i$ letters 
from our alphabet. 
Hence the product ${n\choose i}i^n$ counts
 the words of length $n$ containing at most
 $i$ different letters, but each word is counted
 more than once. Precisely, in the sum (\ref{5}), 
for every integer $k$, $1\leq k\leq n-1$, each word containing exactly $k$ letters is counted one time for each $i$-subset containing these $k$ letters. The number of these subsets is equal to the number of ways in which we can pick $i-k$ letters from the remaining $n-k$ letters of the alphabet, i.e., it is equal to ${n-k\choose i-k}$. Therefore, in (\ref{5}), each word with exactly $k$ letters is counted $-\sum_{i=k}^{n-1}(-1)^{n-i}{n-k\choose i-k}$ times in total. 
Hence the claim is proven once we have shown that
\begin{equation}\label{6}-\sum_{i=k}^{n-1}(-1)^{n-i}{n-k\choose i-k}=1.\end{equation}
\noindent
Setting $j=i-k$ and making a change of indices, the L.H.S. of (\ref{6}) becomes
\begin{eqnarray*}-\sum_{j=0}^{n-k-1}(-1)^{n-k-j}{n-k\choose j}&=&-\left(\displaystyle\sum_{j=0}^{n-k}(-1)^{n-k-j}{n-k\choose j}-1\right)\\
&=&-\left((1-1)^{n-k}-1\right)=1,\end{eqnarray*}
\noindent
as was to be shown.
\hfill $\Box$
\section*{\normalsize References}
[1] G.~Boole, Calculus of Finite Differences, (J. F. Moulton, ed.), 4th Edition. Chelsea, New York. (n.d.)



 

\end{document}