The last Problem of the Week elicited some diverse and creative responses; many thanks to all those who submitted a solution!

Three basic approaches emerged from the solutions we received, each shedding different light on the problem, so Vishal and I thought it appropriate to give a representative example of each. (This is consonant with established practice in other fora, notably the Problems and Solutions section of the American Mathematical Monthly, which we look to as our model.) Here they are:

1. (Method based on Gamma and Beta functions; composite solution due to Philipp Lampe [U. Bonn], Jöel Duet, and Rod Carvalho) For integers n, k > 0, it is well-known that the Beta function

\displaystyle B(n, k+1) := \frac{\Gamma(n) \Gamma(k+1)}{\Gamma(n+k+1)} = \frac{(n-1)! k!}{(n+k)!}

admits an integral representation

\displaystyle B(n, k+1) = \int_{0}^{1} x^{n-1} (1-x)^k \ dx.

(See for instance Andrews, Askey, and Roy, Special Functions, pp. 4-5.) From the first equation we have \displaystyle \frac1{\binom{n+k}{k}} = nB(n, k+1). Now let n > 1; then we have

\displaystyle \sum_{k=0}^{\infty} \frac1{\binom{n+k}{k}} = n\sum_{k=0}^{\infty} \int_{0}^{1} x^{n-1} (1-x)^k \ dx.

Interchanging summation and integration, we get

\displaystyle n \int_{0}^{1} \sum_{k=0}^{\infty} x^{n-1} (1-x)^k\ dx = \int_{0}^{1} \frac{n x^{n-1}}{1 - (1-x)} dx = \int_{0}^{1} n x^{n-2} dx = \frac{n}{n-1}.

There is a slight difficulty with uniform convergence of the series (which would justify such interchange), at least in the case n = 2. There are various ways of handling this; for example, we may establish the result directly as follows: by change of variables x \leftrightarrow 1-x, we have

\displaystyle \int_{0}^{1} x^{n-1} (1-x)^k dx = \int_{0}^{1} (1-x)^{n-1} x^k dx = \int_{0}^{1} (1-x)^{n-2} (x^k - x^{k+1}) dx

and the partial sum \sum_{k=0}^m \int_{0}^{1} (1-x)^{n-2} (x^k - x^{k+1})\ dx telescopes to

\displaystyle \int_{0}^{1} (1-x)^{n-2}(1 - x^{m+1})\ dx = \frac1{n-1} - \int_{0}^{1} x^{m+1}(1-x)^{n-2}\ dx.

Since x(1-x) \leq \frac1{4} for 0 \leq x \leq 1, the last integral is bounded above by

\displaystyle \int_{0}^{1} x^{m+3-n} \frac1{4^{n-2}}\ dx = \frac1{(m+2-n) 4^{n-2}}

which tends to zero as m \to \infty. Putting all this together, it follows that

\displaystyle n \lim_{m\to \infty} \sum_{k=0}^m \int_{0}^1 x^{n-1} (1-x)^k \ dx = \frac{n}{n-1},

as claimed.

2. (Method of repeated integration, due to Gantumur Tsogtgerel, UC San Diego): Put \displaystyle a_{n k} = \frac1{(k+1)\ldots (k+n)}, and let \displaystyle s_n(x) = \sum_{k=0}^{\infty} a_{n k} x^{k+n}. We have a_{n k} \leq (k+1)^{-n}; thus for n > 1, the series defining s_n(x) converges for |x| \leq 1, and the series defining s_1(x) converges for |x| < 1. Observe that

\displaystyle \sigma_n := \sum_{k=0}^{\infty} \frac1{\binom{n+k}{k}} = n! s_n(1)

for n > 1.

We have s_1(x)=-\ln(1-x) for |x|<1. We also have

s_2(0)=0, \qquad \textrm{and} \qquad s_2'(x)=s_1(x) \qquad (|x|<1)

which gives s_2(x)=x+(1-x)\ln(1-x) for |x|<1. By continuity, we get s_2(1)=1. Further, for n>2 we have s_n(0) = 0 and

s_n'(x)=s_{n-1}(x) \qquad (|x|\leq 1).

Therefore

\displaystyle s_n(1)=\int_{0}^{1} \int_{0}^{x_{n-1}} \ldots \int_{0}^{x_3} s_2(x_2) dx_2 \ldots dx_{n-1}

\displaystyle \qquad =\frac1{(n-3)!} \int_{0}^{1} (1-y)^{n-3} s_2(y)dy,

where we have used the Cauchy formula for repeated integration. After a short integration by parts, this last expression evaluates to \displaystyle s_n(1) = \frac1{(n-1)!(n-1)}. This yields \displaystyle \sigma_n=\frac{n}{n-1} for n>1.

3. (Method of telescoping series, due to Nilay Vaish)

First, note that \displaystyle \, \frac1{\binom{n+k}{k}} = \frac{n!k!}{(n+k)!} = \frac{n!}{(k+1) (k+2) \cdots (k+n)}

\displaystyle = \frac{n!}{(n-1)} \left( \frac1{(k+1) \cdots (k+n-1)} - \frac1{(k+2) \cdots (k+n)} \right).

Therefore, \displaystyle \sum_{k=0}^{\infty} \frac1{\binom{n+k}{k}}

\displaystyle = \frac{n!}{(n-1)} \sum_{k=0}^{\infty} \left( \frac1{(k+1) \cdots (k+n-1)} - \frac1{(k+2) \cdots (k+n)} \right)

\displaystyle = \frac{n!}{(n-1)} \cdot \frac1{(n-1)!} = \frac{n}{n-1}.

Remarks:

Method 1 was the most popular; it has the advantage that provided one is already familiar with the Beta function, the calculation is essentially a triviality [modulo the slight technical bump in the road noted above]. For those unfamiliar with this function, I can strongly recommend the beautiful text by Andrews, Askey, and Roy, mentioned above, where the Beta function occupies a central place.

Method 2 was essentially how I accidentally discovered the calculation of the series to begin with: by considering iterated antiderivatives of \frac1{1-x}. This however was some years ago, and I am grateful to Gantumur for his elegant solution, which saved me the trouble of recalling the details! Incidentally, the Wikipedia article on the Cauchy formula (linked above) sketches a proof which implicitly invokes differentiation under the integral sign (a favorite technique of Feynman), but we can also think of it this way: the (n-1)-dimensional volume of the simplex y \leq \sigma_{n-1} \leq \ldots \leq \sigma_1 \leq x is \displaystyle \frac{(x-y)^{n-1}}{(n-1)!}, since there are (n-1)! possible linear orderings of coordinates of points in the (n-1)-cube [x, y] \times \ldots \times [x, y], and each ordering gives a simplex congruent to all the others. Then the result follows by an application of the Fubini theorem.

Method 3 is in some sense the most elementary solution [e.g., it avoids integration], if one is fortunate enough to see the trick of writing the summands as differences, so that the series telescopes. From one point of view this trick may seem awfully slick, like a magician pulling a rabbit out of a hat. But, it can be made to look utterly natural in the context of discrete calculus (dealing with sequences f: \mathbb{N} \to \mathbb{R} instead of continuous functions \mathbb{R} \to \mathbb{R}, and with the difference operator (\Delta f)(x) := f(x+1) - f(x) instead of the derivative).

Discrete calculus may be built up in analogy with continuous calculus; here are some basic terms of the analogy:

  • A basic identity of discrete calculus is \displaystyle \Delta \binom{x}{k} = \binom{x}{k-1}, the polynomial identity which restates the recursive identity that generates Pascal’s triangle: \displaystyle \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}. This is analogous to the identity of continuous calculus, \displaystyle D(\frac{x^k}{k!}) = \frac{x^{k-1}}{(k-1)!}.
  • The preceding observation suggests that the falling power \displaystyle x^{\underline{k}} := x(x-1)\ldots (x-k+1) is the discrete analogue of the ordinary power f(x) = x^k of continuous calculus. It satisfies the identity \displaystyle \Delta x^{\underline{k}} = kx^{\underline{k-1}}. The discrete analogue of the identity \displaystyle x^{k+l} = x^k \cdot x^l is the identity \displaystyle x^{\underline{k+l}} = x^{\underline{k}} \cdot (x-k)^{\underline{l}}.
  • The last identity may be used to motivate the definition of x^{\underline{k}} when k is negative: from \displaystyle 1 = x^{\underline{0}} = x^{\underline{k}}(x-k)^{\underline{-k}}, one quickly derives \displaystyle x^{\underline{-k}} = \frac1{(x+1)(x+2)\ldots (x+k)}. The identity \displaystyle \Delta x^{\underline{k}} = k x^{\underline{k-1}} holds for all integers k.
  • The analogue of continuous integration is finite summation. Formally, introduce the following symbolism for discrete integration: if a \leq b and b-a is integral, \textstyle \sum_{a}^{b} f(x) \delta x := f(a) + f(a+1) + \ldots + f(b-1). The fundamental theorem of discrete calculus is that \textstyle{\sum_{a}^{b}} f(x) \delta x = F(b) - F(a) if \Delta F(x) = f(x). This simply restates the method of telescoping sums.

Using discrete calculus, the solution could be expressed compactly as follows:

\displaystyle \sum_{k=0}^{N-1} \frac{n! k!}{(n+k)!} = n! \textstyle{\sum_{0}^{N}} x^{\underline{-n}} \delta x = n! \left. \displaystyle \frac{x^{\underline{1-n}}}{1-n} \right|_{0}^{N} = \displaystyle \frac{n!}{1-n}(N^{\underline{1-n}} - 0^{\underline{1-n}}).

Letting N \to \infty, our answer is: \displaystyle -\frac{n!}{1-n} 0^{\underline{1-n}} = \frac{n}{n-1}.

About these ads