Iron-Fisted Recurrence-Summation

If $F_n(x)$ is the generating function of the coefficients $f(n,k)$ , so that $F_n(x) \; = \; \sum_{k \in \mathbb{Z}}f(n,k)x^k$ then it is clear from the definition that $F_0(x) = 1+x$ and that $F_n(x) \; = \; (1 + x^{2n})F_{n-1}(x) \hspace{1cm} n \ge 1 \;.$ Thus we deduce that $F_n(x)$ is a polynomial for each $n \ge 0$ , and indeed that $F_n(x) \; = \; (1 + x)\prod_{j=1}^n(1 + x^{2j}) \hspace{1cm} n \ge 1 \;.$ From this it is clear that the polynomial $F_n(x)$ has degree $n^2+n+1$ , so that $f(n,k) = 0$ for $k < 0$ or $k > n^2+n+1$ , and it follows that $\sum_{k=0}^{n^2+n+1}f(n,k) \; = \; F_n(1) \; = \; 2^{n+1} \hspace{1cm} n \ge 1 \; .$ A simple induction on $n$ also shows that $F_n(x) \; = \; x^{n^2+n+1}F_n\big(x^{-1}\big)$ so that there is symmetry in the coeffcients $f(n,k)$ , with $f(n,k) \; = \; f(n,n^2+n+1-k) \hspace{1cm} 0 \le k \le n^2+n+1$ and hence $\sum_{k=0}^{\binom{n+1}{2}}f(n,k) \; = \; \sum_{k=0}^{\frac12(n^2+n)}f(n,k) \; = \; \tfrac12\sum_{k=0}^{n^2+n+1}f(n,k) \; = \; \tfrac12F_n(1) \; = \; 2^n$ For this problem, $n = 2008$ . Thus the sum is $2^{2008}$ , and the answer is $2008 - 2 = \boxed{2006}$ .