16th Turkish Mathematical Olympiad

It can be shown by induction on $n\ge 0$ that $f(n,k)=0$ if $k<0$ or $n^2+n+1<k$, $f(n,n^2+n+1-k)=f(n,k)$ for all $k$, and ${\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: $$\begin{array}{rl}& 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,n^2+n+1-(k-2(n+1)))\\ & +f(n,n^2+n+1-k)\\ & =f(n,k-2(n+1))+f(n,k)\\ & =f(n+1,k)\end{array}$$ Therefore, $$\sum _{k=0}^{\left(\genfrac{}{}{0ex}{}{(2009)}{2}\right)}f(2008,k)=\frac{1}{2}\sum _{k=0}^{2008^2+2008+1}f(2008,k)=\frac{1}{2}{2}^{2009}=2^{2008}.$$