## Solution to the summing problem

Remember that wee summing problem we introduced last week? The task was to prove that

$S_{n+1} = 1 + \dfrac{1}{n+1}\displaystyle\sum_{k=1}^nS_k \quad \forall \ n \in \mathbb{N}$, where $S_n = \displaystyle\sum_{k=1}^n\dfrac{1}{k}$.

How you prefer to tackle problems like this will depend on your mathematical “personality” and on the tools you have available. For example, you may well see “$\forall n \in\mathbb{N}$” and immediately suspect that there’s a proof by induction lurking… and it’s certainly possible to prove this result by induction. However, there’s also a quicker and sneakier way.

For brevity, let’s write $\displaystyle\sum_{k=1}^nS_k = T_n$. Then $T_n$ is a double sum:

$T_n = \displaystyle\sum_{k=1}^n\sum_{j=1}^k\dfrac{1}{j} = 1 + \left( 1 + \dfrac{1}{2}\right) + \left( 1 + \dfrac{1}{2} + \dfrac{1}{3}\right) + \dots + \left( 1 + \dfrac{1}{2} + \dots \dfrac{1}{n}\right)$.

The sneaky bit is to spot that we can rewrite this double sum in a different way, by collecting first all the 1s ($n$ of them), then all the $\frac{1}{2}$s ($n-1$ of them), and so on up to the single $\frac{1}{n}$. Thus

$T_n = n + (n-1)\dfrac{1}{2} + (n-2)\dfrac{1}{3} + \dots + 1\cdot\dfrac{1}{n}$.

But we can rewrite this more compactly, and thus tidy it up:

$T_n = \displaystyle\sum_{k=1}^n\dfrac{n+1-k}{k} =(n+1)\displaystyle\sum_{k=1}^n\dfrac{1}{k} + \displaystyle\sum_{k=1}^n(-1) = (n+1)S_n - n$.

We’re nearly there now! Rearranging, we have

$S_n = \dfrac{1}{n+1}T_n + \dfrac{n}{n+1}$,

and so

$S_{n+1} = S_n + \dfrac{1}{n+1} = \dfrac{1}{n+1}T_n + \dfrac{n}{n+1} + \dfrac{1}{n+1} = 1 + \dfrac{1}{n+1}\displaystyle\sum_{k=1}^nS_k$,

as required.

(DP)

PS: I should say that there’s another way to tackle the problem, by setting up an iterative expression for $S_{n+1}$ in terms of $S_n$. See Rafael Tesoro’s comment on the original article for details!