Let P = C(k,0) + C(k+1,1) + C(k+2,2) + ... + C(2k,k) and Q = C(2k+1, k+1), where k is a positive integer. Then A. P = Q + k B. P = Q + k C. P = Q D. P = Q + 2k

GATE 2008 · Discrete Mathematics · Summation · easy

Answer: P = Q, so the answer is C.

1. Rewrite each term using symmetry: Since C(n,r) = C(n, n-r), we have C(k+i, i) = C(k+i, (k+i)-i) = C(k+i, k). So P = sum_{i=0}^{k} C(k+i, k).
2. Apply the Hockey Stick identity: Set r = k and j runs from k to k+k = 2k. So n = 2k. sum_{j=k}^{2k} C(j,k) = C(2k+1, k+1).
3. Compare with Q: Since Q is defined as C(2k+1, k+1) and we just showed P = C(2k+1, k+1), we conclude P = Q.