The sequence of non-negative integers c1, c2, ... , c1997 satisfies c1 ≥ 0 and cm + cn ≤ cm+n ≤ cm + cn + 1 for all m, n > 0 with m + n < 1998. Show that there is a real k such that cn = [nk] for 1 ≤ n ≤ 1997.
Solution
Any such k must satisfy cn/n ≤ k < cn/n + 1/n for all n. Hence we must have cm/m < cn/n + 1/n or n cm < m cn + m for all m, n. Conversely, if this inequality holds, then such k exist. For example, we could take k = max cn/n.
It is tempting to argue that n cm < (n-1) cm + c2m < (n-2) cm + c3m < ... < cmn ≤ cmn-n + cn + 1 ≤ ... ≤ m cn + m. But this does only works for small m, n, because otherwise mn may be out of range. Instead we use induction on m+n. It is obviously true for m = n = 1 and indeed any m = n. Now suppose m < n (and it is true for smaller m + n). Then by induction (n - m) cm < m cn-m + m. But cm ≤ cn - cn-m, so m cm ≤ m cn - m cn-m. Adding, we get n cm < m cn + m as required. Similarly, if m > n (and the result is true for smaller m + n), then by induction, n cm-n < (m - n) cn + (m - n). But n cm <= n cn + n cm-n + n, so adding n cm < m cn + m, as required.
© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002