Maths WorkshopMaths problems with full solutions
Exercise 1553Combinatorics › Binomial coefficientsOlympiadAdded 3 Nov 2026

Convolution of binomial rows

#convolution#binomial#Vandermonde

Statement

Compute ∑k=0n(kj)(n−ki)\sum_{k=0}^{n}\binom{k}{j}\binom{n-k}{i}.

Hint

Sum over kk from jj to n−in-i: (n+1i+j+1)\binom{n+1}{i+j+1}.

Show solutionHide solution

Solution

Vandermonde variant. Let m=k−jm=k-j, so ∑k(kj)(n−ki)=∑m(j+mj)(i+n−j−mi)\sum_{k}\binom{k}{j}\binom{n-k}{i}=\sum_m\binom{j+m}{j}\binom{i+n-j-m}{i}.

Using the generating function ∑m(j+mj)xm=1(1−x)j+1\sum_m\binom{j+m}{j}x^m=\frac{1}{(1-x)^{j+1}} and ∑m(i+mi)xm=1(1−x)i+1\sum_m\binom{i+m}{i}x^m=\frac{1}{(1-x)^{i+1}}, the convolution is 1(1−x)i+j+2\frac{1}{(1-x)^{i+j+2}}, whose coefficient is (n+1i+j+1)\binom{n+1}{i+j+1}.

Conclusion. ∑k(kj)(n−ki)=(n+1i+j+1)\sum_k\binom{k}{j}\binom{n-k}{i}=\binom{n+1}{i+j+1}.