Basic Sums

Transcript

0:00Introduction

Hello everyone! Okay, a small puzzle to start. Here is the first half of the row of Pascal's triangle for n equals eleven: one, eleven, fifty five, one hundred and sixty five, three hundred and thirty, and four hundred and sixty two. Can you add these six numbers in five seconds? Hard, right? Today you will get it without adding even one of them. Sums like this come up often in JEE, so let's begin.

0:28Put x=1 and x=-1

So, everything today comes from one expansion: one plus x, in round brackets, to the power n, where n is a positive integer. It equals C zero, plus C one times x, plus C two times x squared, and so on, the three dots, up to C n times x to the power n. Here C r, the capital C with a small r below, means n C r, with the small n at the top left. Okay? This is true for every value of x, so we put in convenient values. First, x equals one: every power of one is one. So C zero plus C one plus C two, and so on up to C n, equals one plus one, to the power n: two to the power n. Right? Next, x equals minus one. The signs alternate: C zero, minus C one, plus C two, and so on, ending with minus one to the power n, times C n. The left side becomes one minus one, to the power n: zero. Clear? Look at this alternating sum. Coefficients with an even number below get a plus, and the odd ones get a minus. So tell me: which is bigger, the even sum or the odd sum? Neither, exactly! The alternating sum is zero, so the two are equal, and together they make two to the power n. So C zero plus C two plus C four, and so on, equals C one plus C three plus C five, and so on, and each is two to the power, n minus one. Half and half! Got it?

1:58Any polynomial: use f(1) and f(-1)

The same trick works for any polynomial, f of x. Put x equals one, and every term becomes just its coefficient. So the sum of all the coefficients is f of one. With me? Put x equals minus one, and only the odd powers flip their sign. So adding gives the even powers: f of one plus f of minus one, over two. Subtracting gives the odd powers: f of one minus f of minus one, over two.

2:28Odd n: the first half is half of everything

Okay? Now something new. Suppose n is odd: n equals two m plus one. Then the row has n plus one, that is two m plus two coefficients: an even number. So it splits into two equal halves, with m plus one in each. Right? And by symmetry, n C r equals n C, n minus r. So C zero equals C n, C one equals C, n minus one, and so on, up to C m equals C, m plus one. Each coefficient in the first half has an equal partner in the second, so both halves have the same sum. Clear? Both halves together make two to the power n. So what is the sum of just the first half, C zero up to C m? Half of the total, yes! Two to the power, two m plus one, over two: two to the power two m. But careful, this needs n odd. When n is even, the middle coefficient has no partner, so the row does not split like this. Got it?

3:28Stop early: the partial alternating sum

Now, what if the alternating sum stops early, at C r? Then it is not zero any more. C zero minus C one, and so on, up to minus one to the power r times C r, equals minus one to the power r, times n minus one C r. We prove it in Example two. With me? Look closely at the answer: at the top left of that C sits n minus one, not n. Students often write n here. Don't do that! Okay?

3:56Example 1: 11C0 + 11C1 + ... + 11C5 without adding

Now, remember our puzzle from the start? Let's finish it. Find eleven C zero, plus eleven C one, and so on, up to eleven C five. Pause the video and try it. Done? Okay, let's check. Here n is eleven, which is odd: two times five, plus one. So m is five, and the sum runs from C zero to C m: exactly the first half of the row. Right? By symmetry, this first half equals the second half, eleven C six up to eleven C eleven. Clear? Both halves together are the whole row: two to the power eleven, which is two thousand and forty eight. With me? Now, our formula said two to the power two m, and m is five. So the answer is two to the power five, thirty two, right? No, no, careful! The power is two m, not m. So it is two to the power ten: half of two thousand and forty eight, which is one thousand and twenty four. Puzzle solved! Those six numbers add up to one thousand and twenty four, and we never added a single one. Perfect!

5:00Example 2: prove the partial alternating sum, n = 12

Now a harder one, in two parts. First, prove the partial alternating sum we just met. Then find twelve C zero, minus twelve C one, plus twelve C two, minus twelve C three, plus twelve C four. Pause the video and try it. Hint: use Pascal's rule. Done? Okay, let's check. Pascal's rule: C k equals n minus one C k, plus n minus one C, k minus one. So we break every coefficient into two pieces from the row above. Okay? Now write the sum in these pieces. C zero is just n minus one C zero, in round brackets: both are one. Then minus the bracket, n minus one C one plus n minus one C zero. Then plus n minus one C two plus n minus one C one, and so on. Right? Now look at the first two brackets. The piece n minus one C zero comes once with a plus, and once with a minus. So what happens to it? It cancels, yes! All along the line, each piece cancels with its neighbour. So the sum telescopes, and only the very last piece survives: minus one to the power r, times n minus one C r. Proved! Very good! Now the numbers. The sum stops at twelve C four, so the answer is twelve C four, right? Oh no, careful! The top left is n minus one, so it is eleven C four, not twelve C four. Here n is twelve and r is four, and minus one to the power four is plus one. So the answer is eleven C four: three hundred and thirty. Got it? Let's check by adding directly: one, minus twelve, plus sixty six, minus two hundred and twenty, plus four hundred and ninety five. Three hundred and thirty again! Neat, isn't it?

6:54Quick revision: 2^n, even and odd sums, half row, stop early

So, quick revision. One: all the C r add up to two to the power n, and the even sum equals the odd sum, two to the power, n minus one. Two: for any polynomial f of x, the sum of all the coefficients is f of one. Three: when n is odd, say n equals two m plus one, the first half of the row adds up to two to the power two m. Four: an alternating sum that stops at C r is minus one to the power r, times n minus one C r. Now go and try the practice problems on this page. All the best!