IMO 1973 SL 8

Origin: ROM

Problem

Prove that there are exactly
k [k/2]  arrays a1, a2, . . . , ak+1 of nonnegative integers such that a1 = 0 and |ai−ai+1| = 1 for i = 1, 2, . . . , k.

Solution

Let fn be the required total number, and let fn(k) denote the number of sequences a1, . . . , an of nonnegative integers such that a1 = 0, an = k, and |ai −ai+1| = 1 for i = 1, . . . , n −1. In particular, f1(0) = 1 and fn(k) = 0 if k < 0 or k \geqn. Since an−1 is either k −1 or k + 1, we have fn(k) = fn−1(k + 1) + fn−1(k −1) for k \geq1. (1)

By successive application of (1) we obtain fn(k) = r  i=0 r i  −  r i −k −1  fn−r(k + r −2i). (2) This can be verified by direct induction. Substituting r = n −1 in (2), we get at most one nonzero summand, namely the one for which i = k+n−1 . Therefore fn(n −1 −2j) =
n−1 j  −
n−1 j−1  . Adding up these equalities for j = 0, 1, . . ., / n−1 we obtain fn =
n−1 [ n−1 ]  , as required.