difficult problem about binomial coefficients

426 Views Asked by At

If $r,m,n\in \mathbb N$ so that $r\le \min \{n,m\}$, then $$\binom{n+m}{r} = \binom{n}{0}.\binom{m}{r}+\binom{n}{1}.\binom{m}{r-1}+...+\binom{n}{r}.\binom{m}{0}.$$

If $\min \{n,m\} < r$, then how would you fix the formula? I would really appreciate your help. :)

3

There are 3 best solutions below

0
On

No fix is needed, the formula is true no matter what size $r$ is compared to $n$ or $m$.

Note the binomial coefficient $\binom{n}{k}$ is $0$ if $n<k$. (There are zero $k$-subsets of $[n]$.)

In fact we can go even further. With the stipulation that $\binom{x}{k}:=x(x-1)\cdots/k!$ (with $k$ factors multiplied in the numerator), we can interpret $\binom{x}{k}$ as a polynomial in $x$. Then the equality becomes an identity in the polynomial ring $\Bbb Q[x]$. In particular we can then evaluate $n$ and $m$ not just at natural numbers, but at any elements of any chosen $\Bbb Q$-algebra. This generalization is known as the Chu-Vandermonde identity.

0
On

You don't have to go off the deep end here. Just have the condition that, for any whole numbers n and k, n choose k is zero when n < k. The formula will still work as written.

0
On

If $0\le n\lt k$ or $k\lt0$, then $\dbinom{n}{k}=0$. For example: $$ \begin{align} \binom{5}{3} &=\binom{3}{3}\binom{2}{0}+\binom{3}{2}\binom{2}{1}+\binom{3}{1}\binom{2}{2}+\binom{3}{0}\binom{2}{3}\\ &=\hspace{7mm}1\cdot1\hspace{7mm}+\hspace{7mm}3\cdot2\hspace{8mm}+\hspace{8mm}3\cdot1\hspace{7mm}+\hspace{8mm}1\cdot0\\[6pt] &=\hspace{8mm}10 \end{align} $$


I specify that $n\ge0$ since $\dbinom{n}{k}=(-1)^k\dbinom{k-n-1}{k}$ when $n\lt0$. This comes up when using the generalized binomial theorem for expansions like $$ (1+x)^{-2}=1-2x+3x^2-4x^3+\dots $$