Math & Data Science Q&A - Get answers from our AI that are verified by human experts
First time here? Checkout the FAQs!
x

*Math Image Search only works best with zoomed in and well cropped math screenshots. Check DEMO

0 like 0 dislike
37 views
Prove the Vandermonde identity.

For integers \(N, M, n \geq 0\), the following identity holds:
\[
\sum_{k=0}^n\left(\begin{array}{l}
N \\
k
\end{array}\right)\left(\begin{array}{c}
M \\
n-k
\end{array}\right)=\left(\begin{array}{c}
N+M \\
n
\end{array}\right)
\]
in Data Science & Statistics by Platinum (163,814 points) | 37 views

1 Answer

0 like 0 dislike
Best answer
Proof: Sums of the form
\[
\sum_{k=0}^n a_k b_{n-k}
\]
are reminiscent of polynomial multiplication: If two polynomials \(A(x)=\sum_{k=0}^N a_k x^k\) and \(B(x)=\sum_{l=0}^M b_l x^l\) are given, then one obtains for the product of the two
\[
A(x) \cdot B(x)=\sum_{k=0}^N \sum_{l=0}^M a_k b_l x^{k+l} .
\]
The coefficient of \(x^n\) is obtained from those terms for which \(k+l=n\), or equivalently \(l=n-k\). It follows that the coefficient of \(x^n\) equals
\[
\sum_{k=0}^n a_k b_{n-k}
\]
where we set \(a_k=0\) if the degree \(N\) of the polynomial \(A\) is less than \(k\) (and likewise \(b_l=0\) if \(l>M\) ). The same argument is also used later in Section 4.3.

In the present case the problem can be solved by applying the binomial theorem to the polynomial \((1+x)^{N+M}\), which is also the product of the two polynomials \((1+x)^N\) and \((1+x)^M\)
\[
(1+x)^{N+M}=(1+x)^N \cdot(1+x)^M=\left(\sum_{k=0}^N\left(\begin{array}{c}
N \\
k
\end{array}\right) x^k\right)\left(\sum_{l=0}^M\left(\begin{array}{c}
M \\
l
\end{array}\right) x^l\right)
\]

\[
=\sum_{k=0}^N \sum_{l=0}^M\left(\begin{array}{c}
N \\
k
\end{array}\right)\left(\begin{array}{c}
M \\
l
\end{array}\right) x^{k+l}=\sum_{n=0}^{N+M} \sum_{k=0}^n\left(\begin{array}{c}
N \\
k
\end{array}\right)\left(\begin{array}{c}
M \\
n-k
\end{array}\right) x^n .
\]
Now we obtain the desired identity upon comparing coefficients with
\[
(1+x)^{N+M}=\sum_{n=0}^{N+M}\left(\begin{array}{c}
N+M \\
n
\end{array}\right) x^n .
\]
Once again, it is possible to prove the identity by means of a simple counting argument: consider a set of \(N+M\) elements, and divide it into two parts with \(N\) and \(M\) elements respectively. If one wants to select \(n\) elements, one can do so by first choosing \(k\) elements from the first part \((k \leq n)\) and the remaining \(n-k\) elements from the second part. For each \(k\), there are precisely \(\left(\begin{array}{c}N \\ k\end{array}\right)\left(\begin{array}{c}M \\ n-k\end{array}\right)\) possibilities. Summing over all \(k\), we obtain the above expression for \(\left(\begin{array}{c}N+M \\ n\end{array}\right)\).
by Platinum (163,814 points)

Related questions

0 like 0 dislike
0 answers
0 like 0 dislike
0 answers
0 like 0 dislike
0 answers
0 like 0 dislike
0 answers
1 like 0 dislike
1 answer
0 like 0 dislike
1 answer
0 like 0 dislike
0 answers
0 like 0 dislike
0 answers

Join MathsGee, where you get expert-verified math and data science education support from our community fast.


On the MathsGee, you can:


1. Ask and answer questions


2. Get expert-verified answers


3. Vote on questions and answers


4. Tip your favorite community members


5. Join expert live video sessions (Paid/Free)


6. Earn points by participating


7. Start a Fundraiser



Posting on MathsGee


1. Remember the human


2. Act like you would in real life


3. Find original source of content


4. Check for duplicates before publishing


5. Read the community guidelines




MathsGee Rules


1. Answers to questions will be posted immediately after moderation


2. Questions will be queued for posting immediately after moderation


3. Depending on the number of messages we receive, you could wait up to 24 hours for your message to appear. But be patient as posts will appear after passing our moderation.




MathsGee Android Q&A

MathsGee Android Q&A