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.


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!

This entry was posted in Puzzles. Bookmark the permalink.

One Response to Solution to the summing problem

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.