Mathematical Memorandum: Binomial coefficients

A student came and asked me to compute the following finite series in part time job yesterday: let n be an arbitrary natural number, then show
$\begin{array}{cl} \textrm{(i)} & \displaystyle{ \binom{n}{0} + \binom{n + 1}{1} + \cdots + \binom{n + k}{k} = \binom{n + k + 1}{k} } ; \\ \textrm{(ii)} & \displaystyle{ \binom{k}{k} + \binom{k + 1}{k} + \cdots + \binom{n}{k} = \binom{n + 1}{k + 1}, \textrm{ for } n \geq k. } \\ \end{array}$

It is easy to show both (i) and (ii) by induction. However, some smart people know that a binomial polynomial expansion yields the results. I refer to only (i) and leave (ii) the readers as an exercise.

Note that

$\displaystyle{ (x + 1)^{n + l} = \cdots + \binom{n + l}{l} x^n + \cdots, \mathrm{ for } 0 \leq l \leq k. }$

Summing over,

$\displaystyle{ \sum_{0 \leq l \leq k} (x + 1)^{n + l} = \cdots + \sum_{0 \leq l \leq k} \binom{n + l}{l} x^n + \cdots. }$

The left hand side in the above equality is

$\displaystyle{ \frac{(x + 1)^{n} \{ 1 - (x + 1)^{k + 1} \} }{1 - (x + 1)} = \frac{(x + 1)^{n + k + 1} - (x + 1)^n}{x}. }$

The coefficient of x to the pover of n in the right hand side is equal to

$\displaystyle{ \binom{n + k + 1}{n + 1} = \binom{n + k + 1}{k}. }$

Binomial coefficients

0 comments: