IMO 1998 SL 12

Origin: POL

Problem

Let n \geqk \geq0 be integers. The numbers c(n, k) are defined as follows: c(n, 0) = c(n, n) = 1 for all n \geq0; c(n + 1, k) = 2kc(n, k) + c(n, k −1) for n \geqk \geq1. Prove that c(n, k) = c(n, n −k) for all n \geqk \geq0.

Solution

The assertion is clear for n = 0. We shall prove the general case by induction on n. Suppose that c(m, i) = c(m, m −i) for all i and m \leqn. Then by the induction hypothesis and the recurrence formula we have c(n + 1, k) = 2kc(n, k) + c(n, k −1) and c(n + 1, n + 1 −k) = 2n+1−kc(n, n + 1 −k) + c(n, n −k) = 2n+1−kc(n, k −1) + c(n, k). Thus it remains only to show that (2k −1)c(n, k) = (2n+1−k −1)c(n, k −1). We prove this also by induction on n. By the induction hypothesis, c(n −1, k) = 2n−k −1 2k −1 c(n −1, k −1) and c(n −1, k −2) = 2k−1 −1 2n+1−k −1c(n −1, k −1). Using these formulas and the recurrence formula we obtain (2k−1)c(n, k)− (2n+1−k −1)c(n, k −1) = (22k −2k)c(n −1, k) −(2n −3 \cdot 2k−1 + 1)c(n − 1, k −1) −(2n+1−k −1)c(n −1, k −2) = (2n −2k)c(n −1, k −1) −(2n − 3 \cdot 2k−1 + 1)c(n −1, k −1) −(2k−1 −1)c(n −1, k −1) = 0. This completes the proof. Second solution. The given recurrence formula resembles that of binomial coefficients, so it is natural to search for an explicit formula of the form c(n, k) = F (n) F (k)F (n−k), where F(m) = f(1)f(2) \cdot \cdot \cdot f(m) (with F(0) = 1) and f is a certain function from the natural numbers to the real numbers. If there is such an f, then c(n, k) = c(n, n −k) follows immediately. After substitution of the above relation, the recurrence equivalently re- duces to f(n+1) = 2kf(n−k+1)+f(k). It is easy to see that f(m) = 2m−1 satisfies this relation. Remark. If we introduce the polynomial Pn(x) = n k=0 c(n, k)xk, the recurrence relation gives P0(x) = 1 and Pn+1(x) = xPn(x) + Pn(2x). As a consequence of the problem, all polynomials in this sequence are symmetric, i.e., Pn(x) = xnPn(x−1).