Olympiad Maths Prep

Library / /2 of 4

Combinatorics Difficulty 6.5 National olympiad Prove it Turkey

Let NN denote the set of nonnegative integers, and ZZ denote the set of all integers. If a function f:N×Z→Zf: N \times Z \rightarrow Z satisfies the conditions that
i. f(0,0)=1, f(0,1)=1, i.\ f(0, 0) = 1,\ f(0, 1) = 1,
ii. for all k∉{0,1}, f(0,k)=0 and ii.\ \text{for all}\ k \notin \{0, 1\},\ f(0, k) = 0\ \text{and}
iii. for all n≥1 and k, f(n,k)=f(n−1,k)+f(n−1,k−2n), iii.\ \text{for all}\ n \ge 1\ \text{and}\ k,\ f(n, k) = f(n-1, k) + f(n-1, k-2n),
find the value of the sum ∑k=0((2009)2)f(2008,k)\sum_{k=0}^{(2009) \choose 2} f(2008, k).

Solution

It can be shown by induction on n≥0n \ge 0 that f(n,k)=0f(n, k) = 0 if k<0k < 0 or n2+n+1<kn^2+n+1 < k, f(n,n2+n+1−k)=f(n,k)f(n, n^2+n+1-k) = f(n, k) for all kk, and ∑k=0n2+n+1f(n,k)=2n+1\sum_{k=0}^{n^2+n+1} f(n, k) = 2^{n+1}. For example,
the induction step for the second claim can be verified as follows:
f(n+1,(n+1)2+(n+1)+1−k)=f(n,(n+1)2+(n+1)+1−k)+f(n,(n+1)2+(n+1)+1−k−2(n+1))=f(n,n2+n+1−(k−2(n+1)))+f(n,n2+n+1−k)=f(n,k−2(n+1))+f(n,k)=f(n+1,k) \begin{align*} & f(n + 1, (n + 1)^2 + (n + 1) + 1 - k) \\ &= f(n, (n + 1)^2 + (n + 1) + 1 - k) \\ &\quad + f(n, (n + 1)^2 + (n + 1) + 1 - k - 2(n + 1)) \\ &= f(n, n^2 + n + 1 - (k - 2(n + 1))) \\ &\quad + f(n, n^2 + n + 1 - k) \\ &= f(n, k - 2(n + 1)) + f(n, k) \\ &= f(n + 1, k) \end{align*}
Therefore,
∑k=0((2009)2)f(2008,k)=12∑k=020082+2008+1f(2008,k)=1222009=22008. \sum_{k=0}^{(2009) \choose 2} f(2008, k) = \frac{1}{2} \sum_{k=0}^{2008^2+2008+1} f(2008, k) = \frac{1}{2} 2^{2009} = 2^{2008} .

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.