AppliedMultiple choice

What does the identity $\sum_{i=k}^{n}\binom{i}{k} = \binom{n+1}{k+1}$ say combinatorially?

AChoosing $k+1$ items from $n+1$ , split by where the largest one falls
BChoosing $k$ items from $n$ , split by whether the first item is chosen
CIt is the symmetry $\binom{n}{k} = \binom{n}{n-k}$ in disguise
DIt holds only when $k$ divides $n$

The worked solution is in Premium

The answer, the full working and the one idea to take away – for this and all 1,322 questions in the bank. Answer it in practice and your working is marked, with a known mistake named when you make one.

Start the 7-day free trial Practise it with Premium

Learn the method

Binomial identities, and proving them by counting twice

Reported in interviews at

Jane Street, SIG (Susquehanna)

What does the identity ∑i=kn(ik)=(n+1k+1)\sum_{i=k}^{n}\binom{i}{k} = \binom{n+1}{k+1}∑i=kn​(ki​)=(k+1n+1​) say combinatorially?

More counting and combinatorics questions

What does the identity $\sum_{i=k}^{n}\binom{i}{k} = \binom{n+1}{k+1}$ say combinatorially?