MathDB

sum_{k=0}^{2009 \choose 2} f(2008, k), if f(n, k) = f(n -1, k) + f(n- 1, k - 2n)

Source: Indian Postal Coaching 2009 set 5 p3

May 26, 2020

functionSumCombinationsrecurrence relation

Problem Statement

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)