Let $N_0$ denote the set of nonnegative integers and $Z$ the set of all integers. Let a function $f : N_0 \times Z \to Z$ satisfy the conditions (i) $f(0, 0) = 1$, $f(0, 1) = 1$ (ii) for all $k, k \ne 0, k \ne 1$, $f(0, k) = 0$ and (iii) for all $n \ge 1$ and $k, f(n, k) = f(n -1, k) + f(n- 1, k - 2n)$. Find the value of $$\sum_{k=0}^{2009 \choose 2} f(2008, k)$$
Problem
Source: Indian Postal Coaching 2009 set 5 p3
Tags: function, Sum, Combinations, recurrence relation