DRMacIver's Notebook
More ways to work out sums
More ways to work out sums
Sorry, still on different ways to calculate the sum of the first n integers. I’ll get bored eventually.
My last post Introducing a parameter to work out sums was originally called “Using generating functions to work out sums”, but the things I was using in it weren’t generating functions, and doing it with a generating function ends up much nicer, in a way that is obvious in retrospect.
The generating function of a series \(a_n\) is \(\sum\limits_{n \geq 0} a_n x^n\). Often you can work out the generating function then take its power series expansion to calculuate jhe original series.
Here’s how it works:
\[\begin{align*} f(x) &= \sum\limits_{n >= 0} \sum\limits_{i = 1}^n i x^n \\ &= \sum\limits_{i >= 1} \sum\limits_{n \geq i} i x^n \\ &= \sum\limits_{i >= 1} i \sum\limits_{n \geq i} x^n \\ &= \sum\limits_{i >= 1} \frac{i x^i}{1 - x} \\ &= \frac{x}{1-x} \sum\limits_{i >= 1} i x^{i - 1}\\ &= \frac{x}{1-x} \frac{d}{dx} \sum\limits_{i >= 1} x^i \\ &= \frac{x}{1-x} \frac{d}{dx} \sum\limits_{i >= 0} x^i \\ &= \frac{x}{1-x} \frac{d}{dx} \frac{1}{1 - x} \\ &= \frac{x}{(1-x)^3} \\ \end{align*}\]
Rearranging order of sums like this is a fairly standard trick for working out doubly infinite sums. It’s technically justified whenever the sums absolutely converge.
Now, to get the power series, we just need to work out the kth derivative of \(\frac{1}{(1 - x)^3}\). This is \(\frac{3 (3 + 1) \ldots (3 + k - 1)}{(1 - x)^{3 + k}} = \frac{(k + 2)!}{(1 - x)^{3+k}}\).You can prove this with induction if you like. This is a good example of the sort of thing that induction is useful for, where you spot the pattern and just want to go “and so on”. But you can also just go “and so on” if you feel like it.
So, plugging in \(x = 0\) to get the derivates at 0 we get
\[\begin{align*} f(x) &= \frac{x}{(1-x)^3} \\ &= x \sum\limits_{n \geq 0} \frac{(n + 2)!}{2 n!} x^n \\ &= \sum\limits_{n \geq 0} \frac{(n + 1)(n + 2}{2} x^{n + 1} \\ &= \sum\limits_{n \geq 1} \frac{n (n + 1)}{2} x^{n + 1} \\ \end{align*}\]
Giving us, once again, the desired result.
You could use a basically similar argument to calculate \(\sum\limits_{n \geq k} n (n - 1) \ldots (n - k)\), and from that work out \(\sum i^k\) for any \(k\), but I can’t be bothered at present.
In order to not salami slice this topic over too many more posts, here’s another proof I spotted yesterday, which uses a standard combinatorial trick of counting the same thing two different ways:
Consider all distinct pairs of numbers drawn from \(\{1, \ldots, n + 1\}\). Counted one way, this is just \({{n + 1}\choose 2} = \frac{n (n + 1)}{2}\).
Now, count it another way: If the smaller number in the pair is \(k\), then there are exactly \(n + 1 - k\) choices for the larger number. Therefore there are \(\sum\limits_{k=1}^n (n + 1 - k) = \sum\limits_{k = 1}^n k\) choices in total, so \(\sum\limits_{k = 1}^n k = \frac{n (n + 1)}{2}\) as desired.
As an additional note, one thing I’ve been noticing when working these out is just how much better penI know, I know, a true mathematician would use a pencil. and paper is for working these out than trying to type them up on the computer is. Part of this is that my notebook doesn’t have the best affordances around LaTeX, but I think a lot of it is genuine ease. Mathematics really still feels like it’s best done by hand to me.
I think that if I were using an actual interactive theorem prover, or even just a symbolic algebra library in Python, or the like that might stop being the case, but writing LaTeX feels too obviously like a presentation tool, not a tool for actually working things out.