Recurrences, Pairing and Exponential Series

Transcript

0:00Introduction

Hello everyone! The equation x squared minus x minus one equals zero has two roots: one plus root five, all over two, and one minus root five, all over two. I want the fifth power of the first root, plus the fifth power of the second. Will you expand those brackets five times? Horrible, right? Today we do it in a few quick additions, with no root five at all. Tools like this come up often in JEE, so let's begin!

0:30Powers of the roots, without the roots

So, alpha and beta, two Greek letters, are the roots of x squared minus p x plus q equals zero. The small two up top means squared. Look at the signs: minus p, plus q. So alpha plus beta is p, and alpha times beta is q. Clear? Now, capital P with a small n below it equals alpha to the power n, plus beta to the power n. The n up top is the power, so P n adds the n th powers of the roots. Okay? Here is the key question. Alpha is a root. So which equation does alpha itself satisfy? The equation itself, exactly! Alpha squared equals p alpha minus q. Multiply both sides by alpha to the power n minus one. The double arrow means so. Alpha to the power n plus one equals p times alpha to the power n, minus q times alpha to the power n minus one. With me? Beta is also a root, so the same holds for beta. Add the two, and we get: P n plus one equals p times P n, minus q times P n minus one. Only p and q, no roots! Beautiful, right?

1:46Linear recurrences

Now the bigger picture. Here, a n plus two equals p times a n plus one, plus q times a n, with p and q fixed numbers. Each term comes from the two before it: a linear recurrence. Got it? And our rule for P n is one of these, with fixed numbers p and minus q. Right? To add up such a sequence, multiply the recurrence by x to the power n, and add over all n. That sum, with powers of x, is called a generating function. Okay?

2:17The exponential series

Alright, the exponential series. The number e equals sigma of one over n factorial, with n greater than or equal to zero, as written below it. Sigma, the Greek capital letter, means add them all, and the exclamation mark means factorial: one times two times three, up to n. So, one over zero factorial, plus one over one factorial, and so on, and zero factorial is one. Clear? Now, what is n over n factorial, in a simpler form? Very good! Just cancel the n: one over n minus one factorial, for n at least one. So the sum is the series for e again, just shifted. Okay? Next, n squared over n factorial. Cancel one n, and write the n that is left as n minus one, plus one. Each piece gives e again. So, e plus e, two e. Got it? Only odd factorials: one over one factorial, plus one over three factorial, and so on. The sum is e minus e to the minus one, over two, and e to the minus one is one over e. It is called s i n h one, the hyperbolic sine of one. With me? Only even factorials: e plus e to the minus one, over two, called c o s h one, the hyperbolic cosine of one. But careful! This sum starts at one over zero factorial, which is one. If yours starts at one over two factorial, subtract that one. Right?

3:49Pairing terms from the two ends

And now, a beautiful trick: pairing. Suppose f of x, plus f of c minus x, is a constant, the same for every x, where c is a fixed number. Okay? Then, in a sum of f of k over n, pair the first term with the last, the second with the second last, and so on. As long as the two inputs in each pair add up to c, every pair gives that constant. Clear? Topper's check: a strange looking f, at inputs like k over n? First test f of x plus f of one minus x. Constant? Then the sum is almost done. Got it?

4:27Example 1: alpha^5 + beta^5 for roots of x^2 - x - 1 = 0

Now, back to our puzzle. Alpha and beta are the roots of x squared minus x minus one equals zero, and P n is alpha to the power n, plus beta to the power n. Find P five. Pause the video and try it. Done? Okay, let's check. Compare with x squared minus p x plus q. What is q here? Many students say q is one. Is that right? No, no, careful! The middle term gives p equal to one, but the constant term is minus one, so q is minus one. Minus q is plus one, so P n plus one equals P n, plus P n minus one. One sign decides the whole answer. Okay? Now the starting values. P one is alpha plus beta, which is p, so one. Right? P two is alpha squared plus beta squared: alpha plus beta, whole squared, minus two alpha beta. That is one, minus two times minus one: one plus two, three. Clear? Now keep adding the last two. P three is three plus one, four. P four is four plus three, seven. With me? And P five is seven plus four: eleven! See, no root five anywhere. Our puzzle, solved in a few additions.

5:49Example 2: sum of f(k/1996) for f(x) = 9^x/(9^x + 3)

Now a harder one, JEE level. f of x equals nine to the power x, over nine to the power x plus three. Find the sum, k from one to nineteen ninety five, of f of k over nineteen ninety six. Pause and try it. Hint: think pairing. Done? Okay, let's check. The inputs run from one over nineteen ninety six up to nineteen ninety five over nineteen ninety six. The first and the last add up to what? To one, correct! So c is one. Now f of one minus x: nine to the power one minus x is nine over nine to the power x. Multiply the top and the bottom by nine to the power x, and divide by three: three over three plus nine to the power x. Okay? Now add f of x. Look, the same denominator! Nine to the power x plus three, over nine to the power x plus three: exactly one, for every x. Beautiful! So pair k over nineteen ninety six with nineteen ninety six minus k, over nineteen ninety six. Each pair gives one. Nine hundred and ninety seven pairs, so the answer is nine hundred and ninety seven, right? No, no, wait! Nineteen ninety five is odd. So we get nine hundred and ninety seven pairs, and one middle term with no partner: k equals nine hundred and ninety eight. And nine ninety eight over nineteen ninety six is exactly one half. With me? Now f of one half. Nine to the power half is three, so it is three over three plus three: one half. Right? So the sum is nine hundred and ninety seven, plus one half: nine hundred and ninety seven point five. Done in a few lines!

7:41Quick revision: root power recurrence, pairing, e series

So, quick revision. Powers of roots: P n plus one equals p times P n, minus q times P n minus one, with p and q read from x squared minus p x plus q. Pairing: check f of x plus f of c minus x, and watch for a middle term. Exponential: one over n factorial and n over n factorial add to e, n squared over n factorial to two e, starting from zero factorial. Now try the practice problems on this page. All the best!