IMO shortlist 1998/A4 solution

39th IMO 1998 shortlist

Problem A4

Define the numbers c(n, k) for k = 0, 1, 2, ... , n by c(n, 0) = c(n, n) = 1, c(n+1, k) = 2^kc(n, k) + c(n, k-1). Show that c(n, k) = c(n-k, k).

Solution

The first few numbers are:

n=0	               1
n=1	            1     1
n=2	         1     3     1
n=3	      1     7     7     1
n=4	   1    15    35    15     1
n=5	1    31   155   155    31     1

Let f(n) = (2 - 1)(2² - 1)(2³ - 1) ... (2ⁿ - 1) for n > 0 and f(0) = 1. We show that c(n, k) = f(n)/( f(k) f(n-k) ). Put b(n, k) = f(n)/( f(k) f(n-k) ). Then b(n, 0) = b(n, n) = 1. Also 2^kb(n, k ) + b(n, k-1) = f(n)/( f(k) f(n+1-k) ) x (2^k(2^n+1-k - 1) + (2^k - 1) ) = f(n)/( f(k) f(n+1-k) ) x (2ⁿ⁺¹ - 1) = f(n+1)/( f(k) f(n+1-k) ) = b(n+1, k). So b(n, k) satisfies the same recurrence relation and initial conditions as c(n, k). So a simple induction shows that they are the same.

39th IMO shortlist 1998