INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #A18

TWO VERY SHORT PROOFS OF A COMBINATORIAL IDENTITY

Roberto Anglani

Dipartimento Interateneo di Fisica “Michelangelo Merlin”, Università degli Studi di Bari, Via Amendola 173, 70126 Bari, Italy

                       roberto.anglani@ba.infn.it

Margherita Barile^{1}

Dipartimento di Matematica, Università degli Studi di Bari, Via E. Orabona 4, 70125 Bari, Italy

                           barile@dm.uniba.it

Received: 3/21/05, Accepted: 7/31/05, Published: 8/8/05

Abstract

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.

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 first difference of f(x) (with respect to the increment 1) as Δf(x) = f(x+1)−f(x). He then defines, for all integers n ≥ 2, the n-th difference by the recursive formula Δ^{n}f(x) = ΔΔ^{n−1}f(x). This enables him to prove by induction (see [1], p. 5, (2)) that, for all positive integers n,

Δ^{n}x^{n} = n!.  (1)

Later on he introduces the operator E by setting Ef(x) = f(x + 1), so that Δ = E − 1 and, consequently (see [1], p. 19, (3)),

Δ^{n}f(x) = (E − 1)^{n}f(x) = ∑_{i=0}^{n} \binom{n}{i}(−1)^{n−i}E^{i}f(x) = ∑_{i=0}^{n} \binom{n}{i}(−1)^{n−i}f(x + i).

In particular one has that

Δ^{n}x^{n} = ∑_{i=0}^{n} \binom{n}{i}(−1)^{n−i}(x + i)^{n}.  (2)

1Partially supported by the Italian Ministry of Education, University and Research. All surface mail should be sent to the second author.

From (1) and (2) for x = 0 one can derive the identity

n! = ∑_{i=1}^{n}(−1)^{n−i}\binom{n}{i}i^{n}.  (3)

We want to give two alternate proofs of (3), which have the advantage of being direct, short and elementary and, moreover, show the close relation of (3) to differential calculus and combinatorics.

2. The proofs

Proposition 1 For every positive integer n,

n! = ∑_{i=1}^{n}(−1)^{n−i}\binom{n}{i}i^{n}.

Proof. Consider the first order Taylor expansion with Lagrange remainder of the exponential function about 0:

e^{x} = 1 + x + x^{2}g(x),

where g ∈ C^{∞}(R). We deduce that

(e^{x} − 1)^{n} = (x + x^{2}g(x))^{n} = x^{n} + x^{n+1}h(x),  (4)

for some h ∈ C^{∞}(R). The L.H.S. of (4) is

∑_{j=0}^{n}(−1)^{n−j}\binom{n}{j}e^{jx}.

Its n-th derivative is

∑_{j=0}^{n}(−1)^{n−j}\binom{n}{j}j^{n}e^{jx},

whose value at 0 is

∑_{j=1}^{n}(−1)^{n−j}\binom{n}{j}j^{n}.

This is equal to the value of the n-th derivative of the R.H.S. of (4) at 0, which is n!. This completes the proof. □

Proposition 1 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 1 in the following equivalent form:

Proposition 2 The number of words of length n containing at least one repeated letter from an alphabet of n letters is

− ∑_{i=1}^{n−1}(−1)^{n−i}\binom{n}{i}i^{n}.  (5)

Proof. Recall that, for all i = 1, …, n − 1, i^{n} is the number of words of length n which can be formed from a subset of i letters; \binom{n}{i} is the number of ways of choosing i letters from our alphabet. Hence the product \binom{n}{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 (5), for every integer k, 1 ≤ k ≤ 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 \binom{n−k}{i−k}. Therefore, in (5), each word with exactly k letters is counted − ∑_{i=k}^{n−1}(−1)^{n−i}\binom{n−k}{i−k} times in total. Hence the claim is proven once we have shown that

− ∑_{i=k}^{n−1}(−1)^{n−i}\binom{n − k}{i − k} = 1.  (6)

Setting j = i − k and making a change of indices, the L.H.S. of (6) becomes

− ∑_{j=0}^{n−k−1}(−1)^{n−k−j}\binom{n − k}{j} = − (∑_{j=0}^{n−k}(−1)^{n−k−j}\binom{n − k}{j} − 1)
= − ((1 − 1)^{n−k} − 1) = 1,

as was to be shown. □

References

[1] G. Boole, Calculus of Finite Differences, (J. F. Moulton, ed.), 4th Edition. Chelsea, New York. (n.d.)