Canadian Mathematical Olympiad

Solution:
The number of ways of distributing $k$ candies to $2006$ children is equal to the number of ways of distributing $0$ to a particular child and $k$ to the rest, plus the number of ways of distributing $1$ to the particular child and $k-1$ to the rest, plus the number of ways of distributing $2$ to the particular child and $k-2$ to the rest. Thus $f(2006, k) = f(2005, k) + f(2005, k-1) + f(2005, k-2)$, so that the required sum is
$$1 + \sum_{k=1}^{1003} f(2005, k)$$
In evaluating $f(n, k)$, suppose that there are $r$ children who receive $2$ candies; these $r$ children can be chosen in $\binom{n}{r}$ ways. Then there are $k-2r$ candies from which at most one is given to each of $n-r$ children. Hence
$$f(n, k) = \sum_{r=0}^{\lfloor k/2 \rfloor} \binom{n}{r} \binom{n-r}{k-2r} = \sum_{r=0}^{\infty} \binom{n}{r} \binom{n-r}{k-2r}$$
with $\binom{x}{y} = 0$ when $x < y$ and when $y < 0$. The answer is
$$\sum_{k=0}^{1003} \sum_{r=0}^{\infty} \binom{2005}{r} \binom{2005-r}{k-2r} = \sum_{r=0}^{\infty} \binom{2005}{r} \sum_{k=0}^{1003} \binom{2005-r}{k-2r}$$

Solution:
The desired number is the sum of the coefficients of the terms of degree not exceeding $1003$ in the expansion of $\left(1+x+x^{2}\right)^{2005}$, which is equal to the coefficient of $x^{1003}$ in the expansion of
$$\left(1+x+x^{2}\right)^{2005}\left(1+x+\cdots+x^{1003}\right) = \left[\left(1-x^{3}\right)^{2005}(1-x)^{-2005}\right]\left(1-x^{1004}\right)(1-x)^{-1}$$
$$= \left(1-x^{3}\right)^{2005}(1-x)^{-2006} - \left(1-x^{3}\right)^{2005}(1-x)^{-2006} x^{1004}$$
Since the degree of every term in the expansion of the second member on the right exceeds $1003$, we are looking for the coefficient of $x^{1003}$ in the expansion of the first member:
$$\left(1-x^{3}\right)^{2005}(1-x)^{-2006} = \sum_{i=0}^{2005} (-1)^i \binom{2005}{i} x^{3i} \sum_{j=0}^{\infty} (-1)^j \binom{-2006}{j} x^j$$
$$= \sum_{i=0}^{2005} \sum_{j=0}^{\infty} (-1)^i \binom{2005}{i} \binom{2005+j}{j} x^{3i+j}$$
$$= \sum_{k=0}^{\infty} \left( \sum_{i=1}^{2005} (-1)^i \binom{2005}{i} \binom{2005+k-3i}{2005} \right) x^k$$
The desired number is
$$\sum_{i=1}^{334} (-1)^i \binom{2005}{i} \binom{3008-3i}{2005} = \sum_{i=1}^{334} (-1)^i \frac{(3008-3i)!}{i!(2005-i)!(1003-3i)!}$$
(Note that $\binom{3008-3i}{2005} = 0$ when $i \geq 335$.)