- #1

issacnewton

- 1,026

- 36

- Homework Statement
- Prove that

$$ \sum_{k=0}^p \binom{m}{k}\binom{n}{p-k} = \binom{m+n}{p} $$

for non-negative integers m,n,p

- Relevant Equations
- Mathematical Induction

I know that this can be proven with combinatorial proof. But, here I want to prove by induction. I fix ##m,n## and try to induction on ##p##. Let ##P(m,n,p)## be the statement which needs to be proven. Base case is ##p=0##. LHS (left hand side) becomes

$$ \sum_{k=0}^0 \binom{m}{k}\binom{n}{0-k} = \binom{m}{0}\binom{n}{0-0} = 1 $$

And RHS (right hand side) becomes

$$ \binom{m+n}{0} = 1 $$

Hence ##P(m,n,0)## is true. Now, I assume ##P(m,n, p)## and try to prove ##P(m,n,p+1)##. So, ##P(m,n,p)## states

$$ \sum_{k=0}^p \binom{m}{k}\binom{n}{p-k} = \binom{m+n}{p} $$

$$ \binom{m}{0}\binom{n}{p} + \binom{m}{1}\binom{n}{p-1} + \cdots + \binom{m}{p}\binom{n}{p-p} = \binom{m+n}{p} \cdots\cdots (1) $$

And, I need to prove that

$$ \sum_{k=0}^{p+1} \binom{m}{k}\binom{n}{p+1-k} = \binom{m+n}{p+1} $$

Consider the left hand side

$$ \binom{m}{0}\binom{n}{p+1} + \binom{m}{1}\binom{n}{p} + \cdots + \binom{m}{p+1}\binom{n}{p+1-(p+1)} $$

I tried using following binomial identity

$$ \binom{a}{b} = \frac{a-b+1}{b} \binom{a}{b-1} $$

for various terms in the sum but it lead to nowhere.

Thanks ##\smile##

$$ \sum_{k=0}^0 \binom{m}{k}\binom{n}{0-k} = \binom{m}{0}\binom{n}{0-0} = 1 $$

And RHS (right hand side) becomes

$$ \binom{m+n}{0} = 1 $$

Hence ##P(m,n,0)## is true. Now, I assume ##P(m,n, p)## and try to prove ##P(m,n,p+1)##. So, ##P(m,n,p)## states

$$ \sum_{k=0}^p \binom{m}{k}\binom{n}{p-k} = \binom{m+n}{p} $$

$$ \binom{m}{0}\binom{n}{p} + \binom{m}{1}\binom{n}{p-1} + \cdots + \binom{m}{p}\binom{n}{p-p} = \binom{m+n}{p} \cdots\cdots (1) $$

And, I need to prove that

$$ \sum_{k=0}^{p+1} \binom{m}{k}\binom{n}{p+1-k} = \binom{m+n}{p+1} $$

Consider the left hand side

$$ \binom{m}{0}\binom{n}{p+1} + \binom{m}{1}\binom{n}{p} + \cdots + \binom{m}{p+1}\binom{n}{p+1-(p+1)} $$

I tried using following binomial identity

$$ \binom{a}{b} = \frac{a-b+1}{b} \binom{a}{b-1} $$

for various terms in the sum but it lead to nowhere.

Thanks ##\smile##