Just for fun, an example of an application of partial fraction decomposition that doesn't involve taking integrals.
Consider the Fibonacci numbers 0, 1, 1, 2, 3, 5, 8, ... (with the convention that 0 and 1 are the 0th and 1st). Here's one way to get an explicit formula for them.
First, we package them up into what's called a "generating function": 0 x^0 + 1 x^1 + 1 x^2 + 2 x^3 + 3 x^4 + 5 x^5 + ... or, more concisely, the sum of F_n x^n over all nonnegative integers n. Call this thing F(x).
What happens if we add up F(x) and x F(x)? Well, x F(x) is just the same sum but with all the numbers shifted over by 1. It's the sum of x F_n x^n, or the sum of F_n x^(n+1), or the sum of F_(n-1) x^n, with the proviso that there isn't an x^0 term. So when we add this to the sum of F_n x^n, we get the sum of [F_(n-1) + F_n] x^n, with again the proviso that the x^0 term is just F_0 x^0 = 0.
But, aha!, F_(n-1)+F_n is just F_(n+1), at least when n >= 1. So this thing equals the sum of F_(n+1) x^n, except that once again we need to be careful about n=0; more precisely what we have is the sum of F_(n+1) x^n, minus 1. (Because F_1 is 1, but the actual x^0 term is 0.)
And the sum of F_(n+1) x^n equals the sum of F_n x^(n-1), or F(x)/x.
In other words, we have F(x) + x F(x) = F(x)/x - 1, or equivalently (1 - x - x^2) F(x) = x, or equivalently F(x) = x / (1 - x - x^2).
This is already pretty neat -- who would have thought that that big sum, involving the Fibonacci numbers which are defined in terms of a sort of recursive-adding process, would come out to something so simple?
Now comes the coup de grace, which is the bit that uses partial fractions. We can write that denominator as (1-ax) (1-bx) for some numbers a,b. We'll figure out what a,b actually are in a moment -- that's just solving a quadratic equation. For now, looking at the coefficients of x and x^2 we note that a+b=1 and ab=-1. And now we can do the partial-fractions thing. We know that we'll have x/(1-x-x^2) = p/(1-ax)+q/(1-bx) for some p,q. That means that x = p(1-bx)+q(1-ax), so p+q=0 and pb+aq=-1 or p=1/(a-b). That is, F(x) = 1/(a-b) [1/(1-ax) - 1/(1-bx)].
Why bother doing this? Because the fractions we now have are easy to expand in powers of x. We have 1/(1-ax) = 1 + ax + a^2x^2 + ... and 1/(1-bx) = 1 + bx + b^2x^2 + ... So F_n, the coefficient of x^n in F(x), is just 1/(a-b) [a^n - b^n].
Finally, we ought to work out what a,b actually are. It turns out that a = [1+sqrt(5)]/2 and b = [1-sqrt(5)]/2; that is, a is the famous "golden ratio" sometimes called phi, and b = 1-a = -1/a. So a-b is just sqrt(5).
So: the nth Fibonacci number is exactly (phi^n - (-1/phi)^n) / sqrt(5). Isn't that nice?
(Since |b|<1, the term b^n/sqrt(5) is always smaller than 1/2 in absolute value, which means that F_n is also always the closest integer to phi^n/sqrt(5).)
For the avoidance of doubt, none of this has anything at all to do with the disc embedding theorem. I just thought it was worth clarifying that partial fractions aren't just a one-trick pony used only for integrating rational functions; there are other situations in which representing something in terms of partial fractions gives useful insights into its behaviour.
Yup. I don't think the similarity is because I'm copying Knuth (I certainly wasn't deliberately doing so); this is a very well known argument and there isn't all that much scope for presenting it very differently.
(Oddly, I think the presentation in the later Concrete Mathematics is worse than in TAOCP; they're trying to make it more approachable but I think just make it a bit more roundabout.)
Oh, absolutely, I realize that. It’s just that I learned this from Knuth so I recognized the derivation, and I thought you’d like to see it, but I see you already know about it.
Consider the Fibonacci numbers 0, 1, 1, 2, 3, 5, 8, ... (with the convention that 0 and 1 are the 0th and 1st). Here's one way to get an explicit formula for them.
First, we package them up into what's called a "generating function": 0 x^0 + 1 x^1 + 1 x^2 + 2 x^3 + 3 x^4 + 5 x^5 + ... or, more concisely, the sum of F_n x^n over all nonnegative integers n. Call this thing F(x).
What happens if we add up F(x) and x F(x)? Well, x F(x) is just the same sum but with all the numbers shifted over by 1. It's the sum of x F_n x^n, or the sum of F_n x^(n+1), or the sum of F_(n-1) x^n, with the proviso that there isn't an x^0 term. So when we add this to the sum of F_n x^n, we get the sum of [F_(n-1) + F_n] x^n, with again the proviso that the x^0 term is just F_0 x^0 = 0.
But, aha!, F_(n-1)+F_n is just F_(n+1), at least when n >= 1. So this thing equals the sum of F_(n+1) x^n, except that once again we need to be careful about n=0; more precisely what we have is the sum of F_(n+1) x^n, minus 1. (Because F_1 is 1, but the actual x^0 term is 0.)
And the sum of F_(n+1) x^n equals the sum of F_n x^(n-1), or F(x)/x.
In other words, we have F(x) + x F(x) = F(x)/x - 1, or equivalently (1 - x - x^2) F(x) = x, or equivalently F(x) = x / (1 - x - x^2).
This is already pretty neat -- who would have thought that that big sum, involving the Fibonacci numbers which are defined in terms of a sort of recursive-adding process, would come out to something so simple?
Now comes the coup de grace, which is the bit that uses partial fractions. We can write that denominator as (1-ax) (1-bx) for some numbers a,b. We'll figure out what a,b actually are in a moment -- that's just solving a quadratic equation. For now, looking at the coefficients of x and x^2 we note that a+b=1 and ab=-1. And now we can do the partial-fractions thing. We know that we'll have x/(1-x-x^2) = p/(1-ax)+q/(1-bx) for some p,q. That means that x = p(1-bx)+q(1-ax), so p+q=0 and pb+aq=-1 or p=1/(a-b). That is, F(x) = 1/(a-b) [1/(1-ax) - 1/(1-bx)].
Why bother doing this? Because the fractions we now have are easy to expand in powers of x. We have 1/(1-ax) = 1 + ax + a^2x^2 + ... and 1/(1-bx) = 1 + bx + b^2x^2 + ... So F_n, the coefficient of x^n in F(x), is just 1/(a-b) [a^n - b^n].
Finally, we ought to work out what a,b actually are. It turns out that a = [1+sqrt(5)]/2 and b = [1-sqrt(5)]/2; that is, a is the famous "golden ratio" sometimes called phi, and b = 1-a = -1/a. So a-b is just sqrt(5).
So: the nth Fibonacci number is exactly (phi^n - (-1/phi)^n) / sqrt(5). Isn't that nice?
(Since |b|<1, the term b^n/sqrt(5) is always smaller than 1/2 in absolute value, which means that F_n is also always the closest integer to phi^n/sqrt(5).)
For the avoidance of doubt, none of this has anything at all to do with the disc embedding theorem. I just thought it was worth clarifying that partial fractions aren't just a one-trick pony used only for integrating rational functions; there are other situations in which representing something in terms of partial fractions gives useful insights into its behaviour.