An array of rationals f(n, i) where n and i are positive integers with i > n is defined by f(1, i) = 1/i, f(n+1, i) = (n+1)/i ( f(n, n) + f(n, n+1) + ... + f(n, i - 1) ). If p is prime, show that f(n, p) has denominator (when in lowest terms) not a multiple of p (for n > 1).

**Solution**

Generating functions are always a technique to bear in mind for sequences. They are strongly suggested here by the form of the recurrence relation. So let us put f_{n}(x) = f(n, n) x^{n} + f(n, n+1) x^{n+1} + f(n, n+2) x^{n+2} + ... . We can get the sum f(n, n) + f(n, n+1) + ... + f(n, i - 1) by multiplying by (1 + x + x^{2} + x^{3} + ... ). For then the coefficient of x^{i-1} is f(n, n) + f(n, n+1) + ... + f(n, i-1). We can easily get the factor (n+1) by multiplying by it. This gives us a series where the coefficient of x^{i-1} is i f(n+1, i). In other words, it gives us f'_{n+1}(x). So f'_{n+1}(x) = (n+1) f_{n}(x) (1 + x + x^{2} + ... ).

Let us examine the special case n = 1: f'_{2}(x) = 2 (x + x^{2}/2 + x^{3}/3 + ... )(1 + x + x^{2} + ... ). At this point we need to spot that (1 + x + x^{2} + ... ) is in fact the *derivative* of (x + x^{2}/2 + x^{3}/3 + ... ). So integration gives simply (x + x^{2}/2 + x^{3}/3 + ... )^{2}. In fact it is now obvious that we can carry out a simple induction to get f_{n}(x) = (x + x^{2}/2 + x^{3}/3 + ... )^{n}.

This is all that we need. For the coefficient of x^{p} is a sum of terms a/b, where a is an integer and b is a product of n integers taken from {1, 2, ..., p-n+1}. Hence we may add these terms to get a fraction with denominator ( (p-n+1)! )^{n}. This has no factor p. A fortiori, when reduced to lowest terms.

© John Scholes

jscholes@kalva.demon.co.uk

16 Jan 2001

Last corrected/updated 21 Nov 02