The Art and Craft of Problem Solving

5.3 SUMS AND PRODUCTS 159

The entire sum is

( 1 �) + (� �) + (� _ �) + ... + (� __

1

)

223 34 99 100 '

1

and all terms cancel except for the first and last. Our sum reduces to (^1) -
10 0'

The hard part above was discovering that each term could be written in a way that
telescopes. Will this always work? Sadly, no. The important thing is to be aware of
the possibility for telescoping, which is really just an application of the adding zero
creatively tool. And quite often, a telescoping attempt won't work perfectly, but will
reduce the complexity of a problem.

Example 5.3.2 Find a formula for the sum of the first n squares.

Solution: In other words, we seek a formula for

n

12 +2^2 +3^2 + .. ·+n^2 = � /.

J=l

If we were to get lucky as we did with the previous example, we'd discover a magical
sequence U l ,U 2 , ... with the property that

uk+l -Uk = k^2.

Then we'd be done; telescoping yields

n n

� / = � (Uj+l -Uj) = (U 2 - ud + (U 3 - U 2 ) + ... + (un+! - un) = Un+l -U l·

J=! J=!

But we need not get perfect telescoping. We just need to find a sequence Uk so that
consecutive differences look more or less like what we want. This is really nothing
more than pursuing a wishful thinking strategy. In this vein, let's experiment with
some simple sequences. The first thing to try is the naive guess Uk := k^2. We get

Uk+ 1 - Uk = k^2 + 2k + 1 - k^2 = 2k + (^1).
The quadratic terms canceled, leaving only a linear expression. The next guess, of
course, is to try Uk := k^3 , which yields
Uk+ 1 - Uk = (k + 1)^3 - k^3 = k^3 + 3k^2 + 3k + 1 - k^3 = 3k^2 + 3k + 1.
This is not quite k^2 , but it will do quite nicely, for now the telescope methods yields
n n
� ( 3/ + 3j + 1) = � ( Uj+l -Uj) = Un+l -Ul = (n +^1 )
(^3) - 13 = n (^3) + 3n (^2) + 3n.
J=l J=l
In other words,