In rock climbing, a CRUX MOVE is a body contortion that gets you to the top of a rock. In mathematics, a crux move is a mental contortion that gets you to the solution of a problem. Keeping a collection of them at your fingertips will up your math game.
The dirty little secret about infinite series is that we can't sum very many of them. It's true! Go back and look through the six weeks you spent on series in Calc II. The integral test, the comparison test, the limit comparison test, the ratio test, the root test? All these provide are a yes/no (or, all too often, a shrug) on convergence. None of them tell you what the series sums to when it does.
It's a conspicuous hole in calculus. A strange inversion, Fiona Apple sings. It's like Newton put a sticky note on his laptop write down all that cool stuff you discovered about finding series sums before you die and then forgot to read it.
Suddenly: plague.
The problem in a nutshell: you have stumbled upon an infinite series in the wild, some mess hiding behind a big sigma. You want to find what it sums to. A number, an expression, an equation. Something useful. What to do?
Alas, there is no magic bullet. If you want the sum of a series, you'll have to face it in single combat. Some will come along peaceably. But usually the series is belligerent. And usually the series wins. This is calculus, not a fairy tale. And like a legitimate massage therapist, calculus doesn't believe in happy endings.
However, there are some general guidelines for series wrangling:
(1) The Three Good Witches. The geometric, telescoping, and harmonic series are your friends, because we know what they sum to (or don't). To refresh your memory:
Geometric: Σk=1,∞ a ⋅ xk–1 = a / (1–x) ; (–1 < x < +1)
Telescoping: Σ [ wawa(k) – thing ] + [ thing – wawa(k+1) ]
Harmonic: Σ 1/k (diverges)
Footnote: Requisite LabKitty disclaimer about equation formatting weirdness: Σk=a,b (...) is "sum on k from a to b" (b is usually written as a superscript on sigma). Also, I'll often omit the index stuff if it's clear from context. Also, as always, "wawa" is just a placeholder for some to-be-specified argle-bargle.
Footnote: We can write out the geometric series as: a + a⋅x + a⋅x2 + a⋅x3 + ... . We can also write it as: a + x⋅a + x (a⋅x) + x (a⋅x2) + ... . The latter form is useful in deriving the geometric series representing a physical process like discrete growth or a bouncing ball. Each term is an effect (x) applied to the contents of the preceding term, and the whole thing starts with "a."
Footnote: The harmonic series diverges. If the series to be summed is harmonic or bigger, you can give up immediately. Your horse is dead and beating it will come to no good.
(2) Given a series and what it sums to, we can do things to it to get new a series and what the new series sums to as long as we do the same thing to both sides. By "do things," we mean substitute, differentiate, or integrate. The key to turning this concept into a crux move is being able to recognize a derived series from the get-go.
Footnote: Funky things can happen at the endpoints of the radius of convergence after integrating or differentiating a series. Go look them up in your calculus text. Consider yourself warned.
(3) Basic series algebra can be helpful: Σ c ⋅ foo = c ⋅ Σ foo, Σ foo – bar = Σ foo – Σ bar, and Σ foo Σ bar = ΣΣ foo ⋅ bar, for well-behaved (read: convergent) foo series and bar series.
(4) The integral test is a false god. You may recall the integral test for convergence, in which you convert your series into an equivalent integral and test the integral for convergence. I would remind you: the value of the integral (if it exists) is (usually) not the sum of the series. This is easy to forget in a haze of half-remembered calculus.
(5) Finally, don't forget other crux moves. We saw how to sum the geometric series back in Crux Move #3 (Assume a Solution). To save you some clicking, let's reuse that trick here as our first example.
E X A M P L E 1
Compute: Σk=1,∞ xk–1 ( –1 < x < +1)
Assume a solution. Call it S. We have:
S = 1 + x + x2 + x3 + ...
Multiply both sides by x:
xS = x + x2 + x3 + x4 + ...
Subtract the second expression from the first
S – xS = 1
And we obtain S(1 – x) = 1 or S = 1/(1 – x). Easy peasy.
E X A M P L E 2a
Compute: 1 + 2x + 3x2 + 4x3 + ...
This is the classic differentiated geometric series, obtained by differentiating 1 + x + x2 + x3 + ... term by term. If you spot this, the solution is easy. The sum of the geometric series is 1/(1–x), so the sum of the differentiated geometric series is d/dx 1/(1–x) = 1/(1–x)2. The radius of convergence remains unchanged.
Let's apply this result to do something mildly interesting.
E X A M P L E 2b
Show that the mean of the geometric distribution with parameter p is 1/p.
In words: the geometric distribution describes the number of trials (X) required for first success. In symbols: P(X = k) = (1–p)k–1 ⋅ p. For example, the probability it will take three flips of a coin having p = 0.9 to get the first heads is 0.12 ⋅ 0.9 (aka: a tails, another tails, and then the first heads) or 0.009 (aka: not bloody likely). We get the mean by finding the weighted sum over all possible values of k
E(X) = Σk=1,∞ k ⋅ P(X=k) = Σk=1,∞ k (1–p)k–1p
We can take p outside the summation:
E(X) = = p ⋅ Σk=1,∞ k (1–p)k–1
Recognize the sum is a differentiated geometric series with (1–p) playing the role of x. Hence, it sums to 1/(1–[1–p])2 = 1/p2. Multiplying this by the p we moved out front gives E(X) = 1/p. QED.
Sanity check: for p = 0.9, E(X) is very close to one, as we would expect if the probably of throwing a heads is so high.
E X A M P L E 3
Find the sum of:
(x–1) – (x–1)2 / 2 + (x–1)3 / 3 + ...
We can write this as Σ (–1)k(x–1)k+1 / k+1. Noting k+1 appears as both power and denominator, taking a derivative will simplify things: Σ (–1)k(x–1)k = Σ (1–x)k which we recognize as a geometric series with (1–x) playing the role of x. Ergo, the sum of the derivative of the given series is 1/(1–(1–x)) = 1/x. Integrating 1/x gives ln(x). Ergo, the given series sums to ln(x). You may have recognized this all along, in which case my ruthless subterfuge was for naught.
Footnote: We should have included a constant of integration in the last step. Show that it is zero. Also, what is the radius of convergence?
E X A M P L E 4
Find the sum of: 1/2 + 1/6 + 1/12 + 1/20 + ...
One way to attack this is to consider partial sums. S1 = 1/2. S2 = 1/2 + 1/6 = 2/3. S3 = 2/3 + 1/12 = 3/4. In general, Sn = n/(n+1) and by letting n go to infinity we have S = 1. However, there is a telescoping series hiding here. Rewrite the series as 1/2 + 1/(2⋅3) + 1/(3⋅4) + 1/(4*5) + ... which can be factored as (1/1 – 1/2) + (1/2 – 1/3) + (1/3 – 1/4) and so on. All terms after the first cancel in pairs, we arrive again at the result S = 1.
E X A M P L E 5
Find: Σk=2,∞ 1 / ln(k)
Note ln(x) ≤ x for all x. Hence 1/ln(x) ≥ 1/x for x ≥ 2 . This series is bigger than the harmonic series, so it does not have a sum. Abandon ship.
Our final example demonstrates some nice improvisation I came across in Hwei Hsu's Schaum's Outline on Random Processes. Even if you're unfamiliar with probability, I think you can still follow the solution.
E X A M P L E 6
Let X be a Poisson random variable. What is the probability that X is even?
"X is a Poisson random variable" means P(X = k) = e–λ λk / k!, where "P(X = k)" means "the probability that X is equal to k" (k ≥ 0), and λ is a constant chosen so that Σk=0,∞ e–λ λk / k! = 1. We need to compute Σ e–λ λk / k! with k restricted to even integers. The crux is to break the original series into the sum over evens and the sum over odds:
Σevens e–λ λk / k! + Σodds e–λ λk / k!
= Σ e–λ λk / k!
= 1
Σevens e–λ λk / k! – Σodds e–λ λk / k!
= e–λ Σ (–λ)k / k!
= e–λ ⋅ e–λ
= e–2λ
Add the second line to the first. The sums over odds cancel and we're left with: 2 ⋅ Σ evens e–λ λk / k! = 1 + e–2λ. Hence the probability that X is even = (1 + e–2λ ) / 2.
Previous Move: Special Snowflakes
Next Move: foo=sqrt(foo^2)
The dirty little secret about infinite series is that we can't sum very many of them. It's true! Go back and look through the six weeks you spent on series in Calc II. The integral test, the comparison test, the limit comparison test, the ratio test, the root test? All these provide are a yes/no (or, all too often, a shrug) on convergence. None of them tell you what the series sums to when it does.
It's a conspicuous hole in calculus. A strange inversion, Fiona Apple sings. It's like Newton put a sticky note on his laptop write down all that cool stuff you discovered about finding series sums before you die and then forgot to read it.
Suddenly: plague.
Crux Move #7
Infinite Series Fu
Infinite Series Fu
The problem in a nutshell: you have stumbled upon an infinite series in the wild, some mess hiding behind a big sigma. You want to find what it sums to. A number, an expression, an equation. Something useful. What to do?
Alas, there is no magic bullet. If you want the sum of a series, you'll have to face it in single combat. Some will come along peaceably. But usually the series is belligerent. And usually the series wins. This is calculus, not a fairy tale. And like a legitimate massage therapist, calculus doesn't believe in happy endings.
However, there are some general guidelines for series wrangling:
(1) The Three Good Witches. The geometric, telescoping, and harmonic series are your friends, because we know what they sum to (or don't). To refresh your memory:
Geometric: Σk=1,∞ a ⋅ xk–1 = a / (1–x) ; (–1 < x < +1)
Telescoping: Σ [ wawa(k) – thing ] + [ thing – wawa(k+1) ]
Harmonic: Σ 1/k (diverges)
Footnote: Requisite LabKitty disclaimer about equation formatting weirdness: Σk=a,b (...) is "sum on k from a to b" (b is usually written as a superscript on sigma). Also, I'll often omit the index stuff if it's clear from context. Also, as always, "wawa" is just a placeholder for some to-be-specified argle-bargle.
Footnote: We can write out the geometric series as: a + a⋅x + a⋅x2 + a⋅x3 + ... . We can also write it as: a + x⋅a + x (a⋅x) + x (a⋅x2) + ... . The latter form is useful in deriving the geometric series representing a physical process like discrete growth or a bouncing ball. Each term is an effect (x) applied to the contents of the preceding term, and the whole thing starts with "a."
Footnote: The harmonic series diverges. If the series to be summed is harmonic or bigger, you can give up immediately. Your horse is dead and beating it will come to no good.
(2) Given a series and what it sums to, we can do things to it to get new a series and what the new series sums to as long as we do the same thing to both sides. By "do things," we mean substitute, differentiate, or integrate. The key to turning this concept into a crux move is being able to recognize a derived series from the get-go.
Footnote: Funky things can happen at the endpoints of the radius of convergence after integrating or differentiating a series. Go look them up in your calculus text. Consider yourself warned.
(3) Basic series algebra can be helpful: Σ c ⋅ foo = c ⋅ Σ foo, Σ foo – bar = Σ foo – Σ bar, and Σ foo Σ bar = ΣΣ foo ⋅ bar, for well-behaved (read: convergent) foo series and bar series.
(4) The integral test is a false god. You may recall the integral test for convergence, in which you convert your series into an equivalent integral and test the integral for convergence. I would remind you: the value of the integral (if it exists) is (usually) not the sum of the series. This is easy to forget in a haze of half-remembered calculus.
(5) Finally, don't forget other crux moves. We saw how to sum the geometric series back in Crux Move #3 (Assume a Solution). To save you some clicking, let's reuse that trick here as our first example.
E X A M P L E 1
Compute: Σk=1,∞ xk–1 ( –1 < x < +1)
Assume a solution. Call it S. We have:
S = 1 + x + x2 + x3 + ...
Multiply both sides by x:
xS = x + x2 + x3 + x4 + ...
Subtract the second expression from the first
S – xS = 1
And we obtain S(1 – x) = 1 or S = 1/(1 – x). Easy peasy.
E X A M P L E 2a
Compute: 1 + 2x + 3x2 + 4x3 + ...
This is the classic differentiated geometric series, obtained by differentiating 1 + x + x2 + x3 + ... term by term. If you spot this, the solution is easy. The sum of the geometric series is 1/(1–x), so the sum of the differentiated geometric series is d/dx 1/(1–x) = 1/(1–x)2. The radius of convergence remains unchanged.
Let's apply this result to do something mildly interesting.
E X A M P L E 2b
Show that the mean of the geometric distribution with parameter p is 1/p.
In words: the geometric distribution describes the number of trials (X) required for first success. In symbols: P(X = k) = (1–p)k–1 ⋅ p. For example, the probability it will take three flips of a coin having p = 0.9 to get the first heads is 0.12 ⋅ 0.9 (aka: a tails, another tails, and then the first heads) or 0.009 (aka: not bloody likely). We get the mean by finding the weighted sum over all possible values of k
E(X) = Σk=1,∞ k ⋅ P(X=k) = Σk=1,∞ k (1–p)k–1p
We can take p outside the summation:
E(X) = = p ⋅ Σk=1,∞ k (1–p)k–1
Recognize the sum is a differentiated geometric series with (1–p) playing the role of x. Hence, it sums to 1/(1–[1–p])2 = 1/p2. Multiplying this by the p we moved out front gives E(X) = 1/p. QED.
Sanity check: for p = 0.9, E(X) is very close to one, as we would expect if the probably of throwing a heads is so high.
E X A M P L E 3
Find the sum of:
(x–1) – (x–1)2 / 2 + (x–1)3 / 3 + ...
We can write this as Σ (–1)k(x–1)k+1 / k+1. Noting k+1 appears as both power and denominator, taking a derivative will simplify things: Σ (–1)k(x–1)k = Σ (1–x)k which we recognize as a geometric series with (1–x) playing the role of x. Ergo, the sum of the derivative of the given series is 1/(1–(1–x)) = 1/x. Integrating 1/x gives ln(x). Ergo, the given series sums to ln(x). You may have recognized this all along, in which case my ruthless subterfuge was for naught.
Footnote: We should have included a constant of integration in the last step. Show that it is zero. Also, what is the radius of convergence?
E X A M P L E 4
Find the sum of: 1/2 + 1/6 + 1/12 + 1/20 + ...
One way to attack this is to consider partial sums. S1 = 1/2. S2 = 1/2 + 1/6 = 2/3. S3 = 2/3 + 1/12 = 3/4. In general, Sn = n/(n+1) and by letting n go to infinity we have S = 1. However, there is a telescoping series hiding here. Rewrite the series as 1/2 + 1/(2⋅3) + 1/(3⋅4) + 1/(4*5) + ... which can be factored as (1/1 – 1/2) + (1/2 – 1/3) + (1/3 – 1/4) and so on. All terms after the first cancel in pairs, we arrive again at the result S = 1.
E X A M P L E 5
Find: Σk=2,∞ 1 / ln(k)
Note ln(x) ≤ x for all x. Hence 1/ln(x) ≥ 1/x for x ≥ 2 . This series is bigger than the harmonic series, so it does not have a sum. Abandon ship.
Our final example demonstrates some nice improvisation I came across in Hwei Hsu's Schaum's Outline on Random Processes. Even if you're unfamiliar with probability, I think you can still follow the solution.
E X A M P L E 6
Let X be a Poisson random variable. What is the probability that X is even?
"X is a Poisson random variable" means P(X = k) = e–λ λk / k!, where "P(X = k)" means "the probability that X is equal to k" (k ≥ 0), and λ is a constant chosen so that Σk=0,∞ e–λ λk / k! = 1. We need to compute Σ e–λ λk / k! with k restricted to even integers. The crux is to break the original series into the sum over evens and the sum over odds:
Σevens e–λ λk / k! + Σodds e–λ λk / k!
= Σ e–λ λk / k!
= 1
Σevens e–λ λk / k! – Σodds e–λ λk / k!
= e–λ Σ (–λ)k / k!
= e–λ ⋅ e–λ
= e–2λ
Add the second line to the first. The sums over odds cancel and we're left with: 2 ⋅ Σ evens e–λ λk / k! = 1 + e–2λ. Hence the probability that X is even = (1 + e–2λ ) / 2.
Previous Move: Special Snowflakes
Next Move: foo=sqrt(foo^2)
No comments:
Post a Comment