# Iron-Fisted Recurrence-Summation

$\begin{eqnarray} f(0,k) &=& \begin{cases} 1 , k = 0 , 1 \\ 0 , \text{otherwise} \end{cases} \\ f(n,k) &=& f(n-1,k) + f(n-1,k-2n), \qquad n = 1,2,3,\ldots \end{eqnarray}$

A function $$f:\mathbb{N}_0\times \mathbb{Z}\mapsto\mathbb{Z}$$ satisfies the conditions above.

If $$\large\displaystyle \sum_{k=0}^{\binom{2009}2} f(2008,k)$$ can be expressed as $$a^b$$, where $$a$$ and $$b$$ are positive integers with $$a$$ prime, find $$b-a$$.

Notation: $$\dbinom MN$$ denotes the binomial coefficient, $$\dbinom MN = \dfrac{M!}{N!(M-N)!}$$.

×