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 fn(x) = f(n, n) xn + f(n, n+1) xn+1 + f(n, n+2) xn+2 + ... . We can get the sum f(n, n) + f(n, n+1) + ... + f(n, i - 1) by multiplying by (1 + x + x2 + x3 + ... ). For then the coefficient of xi-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 xi-1 is i f(n+1, i). In other words, it gives us f'n+1(x). So f'n+1(x) = (n+1) fn(x) (1 + x + x2 + ... ).
Let us examine the special case n = 1: f'2(x) = 2 (x + x2/2 + x3/3 + ... )(1 + x + x2 + ... ). At this point we need to spot that (1 + x + x2 + ... ) is in fact the derivative of (x + x2/2 + x3/3 + ... ). So integration gives simply (x + x2/2 + x3/3 + ... )2. In fact it is now obvious that we can carry out a simple induction to get fn(x) = (x + x2/2 + x3/3 + ... )n.
This is all that we need. For the coefficient of xp 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