Collection of Maths Problems

Sums of binomial coefficients

Task number: 3418

• Variant

  \(\binom{n-1}{k-1}+\binom{n-1}{k}=\binom{n}{k}\)

• Solution

  \( \binom{n-1}{k-1}+\binom{n-1}{k} =\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}= \\ =\frac{(n-1)!k+(n-1)!(n-k)}{k!(n-k)!} =\frac{n!}{k!(n-k)!} =\binom{n}{k}\)

  From an \(n\)-element set we choose an element \(a\). Then the first term represents choosing \((k-1)\)-element subsets from the remaining elements; we can expand these to \(k\)-element sets by adding \(a\). The second term corresponds to \(k\)-element subsets from the remainder, i.e. those to which \(a\) does not belong. These two groups of sets form all \(k\)-element sets on \(n\) elements, which is the expression on the right side.

• Variant

  \( \sum\limits_{k=0}^n {n \choose k} = 2^n\)

• Solution

  By the binomial theorem:

  \( \sum\limits_{k=0}^n {n \choose k} = \sum\limits_{k=0}^n {n \choose k} 1^k = (1+1)^n = 2^n\)

  Both sides of the equality give the number of subsets of an \(n\)-element set; on the left side they are grouped according to the number of elements \(k\).

• Variant

  \( \sum\limits_{k=0}^n (-1)^k \binom{n}{k} = 0\)

• Solution

  By the binomial theorem:

  \( \sum\limits_{k=0}^n (-1)^k \binom{n}{k} = (1-1)^n = 0\)

  This corresponds to the sum of the \(n\)-th row in Pascal’s triangle with alternating signs. Because every number in the \((n-1)\)-th row contributes the same amount to one number in an odd position in the \(n\)-th row and to one number in an even position, the sum must come out to zero.

• Variant

  \( \binom{n}{m}\binom{m}{r}=\binom{n}{r}\binom{n-r}{m-r}\)

• Solution

  \( \binom{n}{m}\binom{m}{r} = \frac{n!}{m!(n-m)!}\cdot\frac{m!}{r!(m-r)!} = \frac{n!}{(n-m)!(m-r)!r!} = \frac{n!}{r!(n-r)!}\cdot\frac{(n-r)!}{(n-m)!(m-r)!} =\binom{n}{r}\binom{n-r}{m-r}\)

  The expression on the left corresponds to the choice of an \(m\)-element subset \(A\) from a \(n\)-element set, followed by the choice of an \(r\)-element \(B\) from \(A\). On the right side we first choose \(B\) and then we expand it with \(m-r\) elements to \(A\).

• Variant

  \( \sum\limits_{k=0}^r \binom{n}{k}\binom{m}{r-k} = \binom{m+n}{r}\)

• Solution

  From an \(n\)-element set \(A\) we choose \(k\) elements and extend them with \(r-k\) elements from another, \(m\)-element set \(B\), always yielding \(r\) elements from the \((m+n)\)-element union \(A\cup B\). Because we are combining every appropriate subset from \(A\) with every subset of \(B\) of the correct size, and the parameter \(k\) represents all possible sizes of the intersection of \(A\) with the resulting chosen subset, we end up with all possible choices of an \(r\)-element set from \(A\cup B\) (and each choice exactly once).

• Variant

  \( \sum\limits_{k=r}^n \binom{k}{r} = \binom{n+1}{r+1} \)

• Solution

  By induction on \(n\).

  For \(n=r\) we have: \( \binom{k}{r} = 1= \binom{n+1}{r+1} \)

  Otherwise, by the inductive hypothesis for \(n-1\):
  \( \sum\limits_{k=r}^n \binom{k}{r} = \left(\sum\limits_{k=r}^{n-1} \binom{k}{r} \right) + \binom{n}{r} = \binom{n}{r+1} + \binom{n}{r} = \binom{n+1}{r+1} \)