Mathematical Induction with binomial sum

[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$

 

[fresh_42]

$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.

 

[fresh_42]

Guess, I was right.

https://math.stackexchange.com/questions/4949937/mathematical-induction-involving-binomial-sum

 

[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

 

[Gavran]

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.

 

[anuttarasammyak]

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 their 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.

 

[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$ ?

 

[fresh_42]

@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.

 

[fresh_42]

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.