DRMacIver's Notebook
Introducing a parameter to work out sums
Introducing a parameter to work out sums
In my last post I talked about the problem of working out \(\sum\limits_{i = 1}^n i\). In it, I strongly implied that there wasn’t a way to just work out the answer.
This isn’t actually true. There’s a quite straightforward way to just work out the answer. It still requires a little bit of spotting the trick, but the tricks in question are more like puzzle pieces that you have to fit together than genuine insights.
However, it requires a bunch more calculus than I wanted to assume in my last post, so I left it out. If you do know the calculus it might be informative though.
The idea is this: Rather than work out \(\sum\limits_{i = 1}^n i\), we work out \(f_n(x) = \sum\limits_{i = 1}^n i x^i\), and then evaluate \(f(1)\).
This will, weirdly, turn out to be easier.
How do we do this? Like so:
\[\begin{align*} f_n(x) & = \sum\limits_{i = 1}^n i x^i \\ & = x \sum\limits_{i = 1}^n i x^{i - 1} \\ & = x \frac{d}{dx} \sum\limits_{i = 1}^n x^i \\ & = x \frac{d}{dx} \frac{x^{n + 1} - 1}{x - 1} \\ & = x \left(\frac{(n + 1)x^n}{x - 1} - \frac{x^{n + 1} - 1}{(x - 1)^2} \right) \\ & = x \left(\frac{(n + 1)x^n(x - 1) - x^{n + 1} + 1}{(x - 1)^2} \right) \\ & = x \left(\frac{(n + 1)x^{n + 1} - (n + 1)x^n - x^{n + 1} + 1}{(x - 1)^2} \right) \\ & = x \left(\frac{nx^{n + 1} - (n + 1)x^n + 1}{(x - 1)^2} \right) \\ \end{align*}\]
We want to evaluate \(f_n(1)\), but this would require us to divide 0 by 0, so we have to take limits. We can do this with two applications of L’Hôpital’s rule.
\[\begin{align*} \lim_{x \to 1} x \frac{nx^{n + 1} - (n + 1)x^n + 1}{(x - 1)^2} &= \lim_{x \to 1} x \lim_{x \to 1} \frac{n (n + 1) x^n - (n + 1) n x^{n - 1}}{2(x - 1)} \\ & = \frac{n (n + 1) n x^{n - 1} - (n + 1) n (n - 1) x^{n - 2}}{2} \\ & = \lim_{x \to 1} \frac{n (n + 1) x^{n - 2} (n x - n + 1)}{2} \\ & = \frac{n (n + 1)}{2} \\ \end{align*}\]
Which is the desired result.
Now, I think it would be reasonable to consider this approach to be in almost every way worse than the last one. I don’t disagree. That was a whole bunch of symbol shuffling from which you cannot, I think, derive much insight about the nature of the problem.
But, on the other hand, I think it’s worth realising that sometimes that’s good actually. Sometimes you don’t really need the insight, or can’t find it, and you just want to shut up and calculate. This sort of tool is very useful to have handy for that.
For example, suppose you wanted to calculate \(\sum\limits_{i=1}^n i^2\) instead. Our previous methods don’t help us here because there are no nice sums to rearrange. But with this technique it’s actually quite straightforward (if, admittedly, ugly).
First, let’s make use of our previously solved problem to simplify this slightly. We’re actually going to calculate \(\sum\limits_{i=1}^n i(i - 1)\). We can then just add an extra \(\frac{n(n + 1)}{2}\) to the result to get our desired sum.
Now, let \(g(x) = \sum\limits_{i=1}^n i(i - 1) x^{i - 2}\). This is now the second derivative of \(\sum\limits_{i = 1}^n x^i\), which we can work outI asked Wolfram Alpha, because I was lazy, but you could do this by hand through the application of the usual rules for calculating derivatives if you can be bothered. I mostly didn’t because writing it up in my notebook software is a pain. is \(\frac{x^n (n^2 (x - 1)^2 - n x^2 + n + 2 x) - 2 x)}{(x - 1)^3 x}\)
Taking three derivatives with L’Hôpital’s ruleWolfram alpha again. Sorry. we get:
\[\begin{align*} g(1) &= \lim_{x \to 1} \frac{x^n (n^2 (x - 1)^2 - n x^2 + n + 2 x) - 2 x)}{((x - 1)^3 x)}\\ &= \lim_{x \to 1} \frac{ (n - 1) n (n + 1) x^(n - 3) (n^2 (x - 1)^2 + 2 n (x^2 - 1) + 2 x)}{6(4x - 3)} \\ & = \frac{ (n - 1) n (n + 1) (2)}{6} \\ & = \frac{ (n - 1) n (n + 1) }{3} \\ \end{align*}\]
This means that our desired result is
\[\begin{align*} \sum\limits_{i = 1}^n i^2 & = \frac{(n - 1) n (n + 1) }{3} + \frac{n(n + 1)}{2} \\ & = \frac{2 (n - 1) n (n + 1) + 3 n(n + 1) }{6} \\ & = \frac{n (n + 1) ( 2n - 2 + 3)}{6} \\ & = \frac{n (n + 1) ( 2n + 1)}{6} \\ \end{align*}\]
This isConveniently, because I really didn’t want to track down the error if I made one. the correct answer, as you can verify by checking the first couple results.
Now… Do you ever need to be able to do this? Honestly, not really. I get the impression that this used to be a much more important skill, and these days you can mostly use symbolic algebra packages to do it for you, and also you mostly don’t need it anyway, but mathematicians used to get very excited about this sort of formula, and I think they’re still important in a bunch of places. e.g. I bet people who do combinatorics care much more about being able to do calculations like this than I do, because you often reduce counting problems to this sort of calculation.
Personally, I like it at least partly for its illustrative value. It’s sometimes very helpful to know that you could solve a problem if you were just willing to shut up, sit down, and do the algebra. There’s also a satisfying sudoku-like quality to do it.
It’s also interesting having this sort of skillset at all because I get the feeling that basically nobody learns it any more. I learned it because I read “Schaum’s Outlines of Advanced Calculus” at a formative age, and it taught me all sorts of tricks like this, but it meant I went into university with this whole bag of tricks that nobody else had. They weren’t useful tricks to have exactly, but they were interesting, and I do feel like it shaped how I look at mathematics a fair bit.