15th Chinese 2000 Problem A2 The sequence a n is defined by a 1 = 0, a 2 = 1, a n = (n a n-1 + n(n-1) a n-2 + (-1) n-1 n)/2 + (-1) n . Find a n + 2 nC1 a n-1 + 3 nC2 a n-2 + ... + n nC(n-1) a 1 , where nCm is the binomial coefficient n!/(m! (n-m)! ). Solution
: 2 n! - (n + 1). Solution by Laurent Lessard Put b n = a n + 2 nC1 a n-1 + 3 nC2 a n-2 + ... + n nC(n-1) a 1 . We calculate the first few terms: n 1 2 3 4 5 6 7 8 a n 0 1 2 9 44 265 1854 14833 b n 0 1 8 43 234 1433 10072 80631 We notice that a n = n a n-1 + (-1) n . This is an almost trivial induction, once noticed. We next show that b n = n b n-1 + n 2 - n - 1. We have b n - n b n-1 = ∑ 0 n-2 (k+1) nCk a n-k - n(k+1) (n-1)C k a n- k-1 = ∑ (k+1) nCk (a n-k - (n-k) a n-k-1 ) = ∑ (k+1) nCk (-1) n-k . We have nC0 - nC1 x + nC2 x 2 - ... + (-1) n nCn x n = (1 - x) n , so nC0 x - nC1 x 2 + nC2 x 3 - ... + (-1) n nCn x n+1 = x(1 - x) n . Differentiating and setting x = 1 gives: nC0 - 2 nC1 + 3 nC2 - ... + (-1) n-2 (n-1) nC(n-2) + (-1) n-1 n nC(n-1) + (-1) n (n+1) nCn = 0. Hence nC0 - 2 nC1 + 3 nC2 - ... + (-1) n-2 (n-1) nC(n-2) = (-1) n (n 2 - n - 1). So, finally, b n - n b n-1 = n 2 - n - 1, as promised. If we put c n = b n + n + 1, then c 0 = 2 and c n = n c n . So by a trivial induction c n = 2 n! and hence b n = 2 n! - (n+1). Differentiation is outside the syllabus, but we can use k nCk = n (n-1)C(k-1) for k > 0. Thus we start with (n-1)C0 - (n-1)C1 + (n-1)C2 - ... (-1) n-1 (n-1)C(n-1) = 0. Multiplying by n gives nC1 - 2 nC2 + 3 nC3 - ... + (-1) n n nCn = 0. Subtracting from nC0 - nC1 + nC2 - ... = 0 gives nC0 - 2 nC1 + 3 nC2 - ... + (-1) n (n+1) nCn = 0, as required. Rob Pratt noticed that a n is the number of derangements of 1, 2, ... , n, in other words, the number of permutations of 1, 2, ... , n with no fixed points. That leads to an alternative solution based on calculating the average number of fixed points over all permutations. 15th Chinese 2000 © John Scholes jscholes@kalva.demon.co.uk 5 June 2002