# Mathematical Induction with binomial sum

• issacnewton
issacnewton
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##

##p## is bounded by ##m+n## from above, so induction on ##p## might be problematic. How about an induction on ##n+m##? The case ##n+m=0## is true.
\begin{align*}
\sum_{k=0}^{p} \binom{m+1}{k}\binom{n}{p-k}&=\binom{n}{p}+\sum_{k=1}^{p} \binom{m+1}{k}\binom{n}{p-k}\\
&=\binom{n}{p}+\sum_{r=0}^{p-1} \binom{m+1}{r+1}\binom{n}{p-r-1}\\
&=\binom{n}{p}+\sum_{r=0}^{p-1}\left(\binom{m}{r}+\binom{m}{r+1}\right)\binom{n}{p-r-1}\\
&=\binom{n}{p}+\sum_{r=0}^{p-1}\binom{m}{r}\binom{n}{p-r-1}+\sum_{r=0}^{p-1}\binom{m}{r+1}\binom{n}{p-r-1}\\
&\text{etc.}
\end{align*}
I'm not sure whether this will be the solution but at least it looks as if the induction hypothesis can be applied. You just have to be careful with the two ends of the summation when you shift the summation index by one. That's why I separated the ##\binom{n}{p}## term, to have room for my substitution ##k=r+1## avoiding a negative index. Note that the induction hypothesis can also be applied as
$$\sum_{k=1}^{p-1} \binom{m}{k}\binom{n}{p-k}=\binom{n}{p}+\binom{m+n}{p}+\binom{m}{p}$$
or similar expressions. The case, if ##n## is increased by one instead of ##m##, is symmetric and must not be written out.

issacnewton
Thanks for your input. The link given by you is same question I asked on that forum. As you can guess by similar wording

The following identity $$\sum_{k=0}^{p}\binom{m}{k}\binom{n}{p-k}=\binom{m+n}{p}$$ is called Vandermonde convolution.
Mathematical induction can be done on ## m ## and can be done on ## n ## as two separate proofs.

dextercioby and issacnewton
Gavran said:
The following identity ∑k=0p(mk)(np−k)=(m+np) is called Vandermonde convolution.
The meaning is simple and clear. Take k elements from set of m elements and take p-k elements from set of n elements. Multiplying the number of cases and take thier sum for k. The number of cases is same as that of taking p elements from set of m+n elements, which is made of independent subsets of n and m.

Last edited:
issacnewton
@fresh_42 The link you posted has solution where he has taken##m## as the variable on which induction will be done. So, in that case ##n,p## are fixed. Its been assumed that ##P(m,n,p)## is true, so

$$\sum_{k=0}^p \binom{m}{k}\binom{n}{p-k} = \binom{m+n}{p} \cdots\cdots (A)$$

And he is trying to prove ##P(m+1, n, p)##. Let me post the rest of the solution from there.

\begin{align} \sum_{k=0}^p \binom{m+1}{k}\binom{n}{p-k} &= \binom{m+1}{0}\binom{n}{p} +\sum_{k=1}^p \binom{m+1}{k}\binom{n}{p-k}\\ & = \binom{m+1}{0}\binom{n}{p} +\sum_{k=1}^p \binom{m}{k}\binom{n}{p-k}+\sum_{k=1}^p \binom{m}{k-1}\binom{n}{p-k}\\ & = \sum_{k=0}^p \binom{m}{k}\binom{n}{p-k}+\sum_{l=0}^{p-1} \binom{m}{l}\binom{n}{p-1-l}~\quad (l = k-1)\\ & \overset{\text{true for}~ m,n}{=} \binom{m+n}{p}+\binom{m+n}{p-1}\\ & = \binom{m+1+n}{p} \end{align}

Now, in the second last step, he applied eq (A) for ##p-1## to conclude

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

My question is, if ##n,p## are fixed before starting the induction, how can we use eq (A) for ##p-1## ?

issacnewton said:
@fresh_42 The link you posted has solution where he has taken##m## as the variable on which induction will be done. So, in that case ##n,p## are fixed. Its been assumed that ##P(m,n,p)## is true, so

$$\sum_{k=0}^p \binom{m}{k}\binom{n}{p-k} = \binom{m+n}{p} \cdots\cdots (A)$$

And he is trying to prove ##P(m+1, n, p)##. Let me post the rest of the solution from there.

\begin{align} \sum_{k=0}^p \binom{m+1}{k}\binom{n}{p-k} &= \binom{m+1}{0}\binom{n}{p} +\sum_{k=1}^p \binom{m+1}{k}\binom{n}{p-k}\\ & = \binom{m+1}{0}\binom{n}{p} +\sum_{k=1}^p \binom{m}{k}\binom{n}{p-k}+\sum_{k=1}^p \binom{m}{k-1}\binom{n}{p-k}\\ & = \sum_{k=0}^p \binom{m}{k}\binom{n}{p-k}+\sum_{l=0}^{p-1} \binom{m}{l}\binom{n}{p-1-l}~\quad (l = k-1)\\ & \overset{\text{true for}~ m,n}{=} \binom{m+n}{p}+\binom{m+n}{p-1}\\ & = \binom{m+1+n}{p} \end{align}

Now, in the second last step, he applied eq (A) for ##p-1## to conclude

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

My question is, if ##n,p## are fixed before starting the induction, how can we use eq (A) for ##p-1## ?
You do not need an induction along ##p.## We can take ##p## as an arbitrary number ##0\leq p\leq n+m+1## and ##0\leq p \leq n+m## in the induction hypothesis.

The induction along ##m \rightarrow m+1## is sufficient because the problem statement is symmetric in ##n,m,## they are exchangeable. So if we prove it for ##m## we can switch them and get a proof for ##n.##

issacnewton
So, since induction hypothesis is for ##0 \leq p \leq m+n ##, we can plug ##p-1## in that equation and use it. Correct ? sorry for bother but induction in many variables is not straight forward.

issacnewton said:
So, since induction hypothesis is for ##0 \leq p \leq m+n ##, we can plug ##p-1## in that equation and use it. Correct ? sorry for bother but induction in many variables is not straight forward.
Yes. My calculation was
\begin{align*}
\sum_{k=0}^{p} \binom{m+1}{k}\binom{n}{p-k}&=\binom{n}{p}+\sum_{k=1}^{p} \binom{m+1}{k}\binom{n}{p-k}\\
&=\binom{n}{p}+\sum_{r=0}^{p-1} \binom{m+1}{r+1}\binom{n}{p-r-1}\\
&=\binom{n}{p}+\sum_{r=0}^{p-1}\left(\binom{m}{r}+\binom{m}{r+1}\right)\binom{n}{p-r-1}\\
&=\binom{n}{p}+\sum_{r=0}^{p-1}\binom{m}{r}\binom{n}{p-r-1}+\sum_{r=0}^{p-1}\binom{m}{r+1}\binom{n}{p-r-1}\\
&=\binom{n}{p}+\sum_{r=0}^{p-1}\binom{m}{r}\binom{n}{(p-1)-r}+\sum_{s=1}^{p}\binom{m}{s}\binom{n}{p-s}\\ &\stackrel{I.H.}{=} \binom{n}{p} +\binom{m+n}{p-1}+\binom{m+n}{p}-\binom{m}{0}\binom{n}{p}\\
&=\binom{m+n}{p-1}+\binom{m+n}{p}\\
&=\binom{m+n+1}{p}
\end{align*}
The only formula I used here, and maybe you want to prove it, too, was
$$\binom{N+1}{K+1}=\binom{N}{K}+\binom{N}{K+1}$$
with the convention that ##\binom{K}{K+1}=0.##

This is what was left out in post #2 and what the SE link presumably had. I recommend reading this proof once, putting it away, and trying it on your own tomorrow in order to practice induction which is at least as important as the index shifts.

Other examples to practice induction are
\begin{align*}
&\sum_{k=0}^n \binom{n}{k}=2^n\\
&\sum_{k=0}^n (-1)^k\binom{n}{k}=0
\end{align*}
which can be proven in different ways, but you should practice induction.

issacnewton

• Precalculus Mathematics Homework Help
Replies
11
Views
537
• Precalculus Mathematics Homework Help
Replies
19
Views
568
• Precalculus Mathematics Homework Help
Replies
11
Views
2K
• Precalculus Mathematics Homework Help
Replies
10
Views
2K
• Calculus and Beyond Homework Help
Replies
15
Views
2K
• Precalculus Mathematics Homework Help
Replies
10
Views
514
• Calculus and Beyond Homework Help
Replies
6
Views
664
• Precalculus Mathematics Homework Help
Replies
15
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
892
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K