Products and Squares: Vandermonde's Identity

Transcript

0:00Introduction

Hello everyone! Okay, a small puzzle to start. Take row five of Pascal's triangle: one, five, ten, ten, five, one. Now square every number, and add up the squares. Is there a shortcut, one single n C r that gives the answer? Today we find it, by multiplying two expansions. Sums of products like this come up often in JEE, so let's begin.

0:28Multiply two expansions, compare coefficients

So, start with two expansions: one plus x, in round brackets, to the power m, times one plus x, to the power n. Add the powers, and that is one plus x, to the power, m plus n. Here m and n are positive integers. Okay? The two sides are equal, so their coefficients match. Pick one power, x to the power k. On the left side, how can x to the power k be made? Yes, exactly! Take x to the power i from the first bracket, and x to the power, k minus i, from the second. Multiply them, and the powers add up to k. Right? So, the coefficient of x to the power k on the left. The first bracket gives m C i: the capital C with a small m at the top left, and a small i below. The second gives n C, k minus i. Multiply, and add over every possible i. The big Greek letter, sigma, with the small i below it, means add up over all i. Clear? On the right, the coefficient of x to the power k is simply m plus n, C, k. With me? Equate the two, and we get Vandermonde's identity. The sum over i of m C i, times n C, k minus i, equals m plus n, C, k. Most of today's results come from this one line. Got it?

1:51Why it is true: choose a committee

Now, the same identity has a beautiful counting proof. In the picture: m boys on the left, n girls in the middle. We want a committee of k people from all m plus n of them. Directly, that is m plus n, C, k ways. Okay? Can we count the same committees another way? Yes, split them by the number of boys! Say the committee has i boys. Then it has k minus i girls. Choose the boys in m C i ways, and the girls in n C, k minus i ways: that is m C i times n C, k minus i committees. In the picture, three boys and two girls are circled, so i is three, and k minus i is two. Right? Every committee has exactly one value of i, so add over every i. Both ways count the same committees, so the answers are equal. That is Vandermonde's identity again, with no algebra at all! Perfect.

2:44Squares of one row: 2nCn

Now, a famous special case. As usual, C r, with a small r below, means n C r. By symmetry, C r equals C, n minus r. So C r squared, with the small two on top, can be written as C r times C, n minus r. Okay? So the sum of the squares, C zero squared, plus C one squared, and so on, the three dots, up to C n squared, becomes C zero C n, plus C one times C, n minus one, and so on, up to C n C zero. Right? Now look at the indices in each product. Zero and n. One and n minus one. What do they add up to? It is n, every time! Correct! So the sum is the coefficient of x to the power n, in one plus x to the power n, times one plus x to the power n, which is one plus x to the power two n. Clear? So the squares of one row add up to two n C n. This is just Vandermonde with m and k both equal to n. Got it?

3:44Topper's trick: look at the indices

Now let me share a trick that toppers use. When you see a sum of products, C i times C j, look at the indices first. If i plus j is the same in every term, the sum is the coefficient of x to the power, i plus j, in one plus x to the power m, times one plus x to the power n. Okay? Now, suppose j minus i is the same in every term. Then first replace C j by C, n minus j. Symmetry turns a fixed difference into a fixed sum. With me? Try it on this sum: C zero C k, plus C one times C, k plus one, and so on, up to C, n minus k, times C n. Here the indices differ by k every time. So in the term C r times C, r plus k, replace C, r plus k, by C, n minus r minus k. Right? Now, r and n minus r minus k. What do they add up to? They add up to n minus k, yes! So the sum is the coefficient of x to the power, n minus k, in one plus x to the power two n. That is two n C, n minus k, and by symmetry, also two n C, n plus k.

4:53Example 1: sum of the squares of 5Cr

Clear? Now, remember our puzzle? Let's finish it. Find the sum, sigma, for r from zero at the bottom to five at the top, of five C r, in round brackets, squared. Pause the video and try it. Done? Okay, let's check. The numbers in row five add up to two to the power five. So the sum of the squares is two to the power five, squared: one thousand and twenty four, right? No, no, careful! It is not one thousand and twenty four. That squares the whole sum, and the square of the sum is not the sum of the squares. This is a common trap. Clear? Use our result with n equal to five. The sum of the squares is two n C n, that is ten C five: two hundred and fifty two. Right? Let's check with our puzzle: one, plus twenty five, plus one hundred, plus one hundred, plus twenty five, plus one. Two hundred and fifty two! Puzzle solved, with just ten C five! Perfect!

5:55Example 2: sum of 10Cr times 20Cr

Now a harder one. Find the sum, for r from zero to ten, of ten C r, times twenty C r. Pause the video and try it. Hint: look at the indices. Done? Okay, let's check. Both coefficients have the same index below: r and r. Do they add up to a constant? No! r plus r is two r, and that changes from term to term. But the difference, r minus r, is zero every time: a constant difference. Okay? So use the trick. By symmetry, twenty C r equals twenty C, twenty minus r. Now the indices are r and twenty minus r, and they add up to twenty. With me? So the sum is the coefficient of x to the power twenty, in one plus x to the power ten, times one plus x to the power twenty. That product is one plus x, to the power thirty. Right? So the answer is the coefficient of x to the power twenty in one plus x to the power thirty: thirty C twenty. But your friend writes thirty C ten. Who is right? You are both right! By symmetry, thirty C twenty equals thirty C ten, so both answers are the same number. Very good!

7:12Quick revision: Vandermonde, squares, the index trick

So, quick revision. One: Vandermonde. The sum over i of m C i, times n C, k minus i, is m plus n, C, k. Two: the squares of one row add up to two n C n. Three: for a sum of products, make the sum of the indices constant, using symmetry if needed, then read off one coefficient. Now go and try the practice problems on this page. All the best!