Solution for TAOCP exercise 1.2.1-7

https://liron.tilde.team

January 5, 2026

In this document I would like to offer my solution for exercise number 7 of section 1.2.1 in Donald Knuth’s “The Art of Computer programming”. The reason is that the author included as a solution in the book only the final result, without any explanation, and it took me a bit to get there. The exercise is rated 23, which indicates one should need no more than a quarter hour to complete it. I needed about 6 hours, so that might say a lot about my level of intelligence.

1 Introduction

The task is to prove by induction a rule for the sums 1^{2}, 2^{2}−1, 3^{2}−2^{+}1^{,}4^{2}−3^{2}+2^{2}−1^{2}, 5^{2}−4^{2}+3^{2}−2^{2}+1^{2}, ...; Of course the first step is to detect any kind of pattern for these sums, so that we can derive a relationship and then a good guess for some non-recursive function P (n) = ... to calculate the sums for any positive integer n. With a bit of work, we can calculate the result for the given sums:

\begin{matrix}n & P (n) \\ 1 & 1^{2} = 1 \\ 2 & 2^{2} − 1^{2} = 3 \\ 3 & 3^{2} − 2^{2} + 1^{2} = 6 \\ 4 & 4^{2} − 3^{2} + 2^{2} − 1^{2} = 10 \\ 5 & 5^{2} − 4^{2} + 3^{2} − 2^{2} + 1^{2} = 15 \\ 6 & 6^{2} − 5^{2} + 4^{2} − 3^{2} + 2^{2} − 1^{2} = 21 \end{matrix}

There is no obvious relationship between the numbers 1, 3, 6, ... (at least not obvious to me). But when we look at how the values are calculated, we see that the calculation for P (6) contains the calculation for P (4) verbatim. Furthermore, P (5) contains P (3), P (4) contains P (2) and P (3) contains P (1). So we can say:

P (1) = 1
P (2) = 2
P (n) = n^{2} − (n − 1)^{2} + P (n − 2), n > 2

This rule is simple enough to write a short program that calculates P (n):

#!/usr/bin/python3
import math
def f(n):
    if n == 1: return 1
    if n == 2: return 3
    return math.pow(n, 2) - math.pow(n-1, 2) + f(n-2)

for i in range(2,20):
   print(f"{i:>3}: {f(i):>5}")

Output:

 2:     3
 3:   6.0
 4:  10.0
 5:  15.0
 6:  21.0
 7:  28.0
 8:  36.0
 9:  45.0
10:  55.0
11:  66.0
12:  78.0
13:  91.0
14: 105.0
15: 120.0
16: 136.0
17: 153.0
18: 171.0
19: 190.0

Such a small program is useful to confirm our initial calculations^{1}.

2 First guess

Looking at the results, it may strike you that P (11) − P (10) = 11; that is, to get from n = 10 to n = 11, we must add 11 to P (n). So we may suspect that P (n) = P (n − 1) + n. We can confirm this by adding a column for P (n) − P (n − 1) to the table:

\begin{matrix}n & P (n) & P (n) − P (n − 1) \\ 1 & 1^{2} = 1 & - \\ 2 & 2^{2} − 1^{2} = 3 & 3 − 1 = 2 \\ 3 & 3^{2} − 2^{2} + 1^{2} = 6 & 6 − 3 = 3 \\ 4 & 4^{2} − 3^{2} + 2^{2} − 1^{2} = 10 & 10 − 6 = 4 \\ 5 & 5^{2} − 4^{2} + 3^{2} − 2^{2} + 1^{2} = 15 & 15 − 10 = 5 \\ 6 & 6^{2} − 5^{2} + 4^{2} − 3^{2} + 2^{2} − 1^{2} = 21 & 21 − 15 = 6 \end{matrix}

So indeed this is the case; looking at the first values for n:

P (3) = P (2) + 3 = 3 + 3 = 6
P (4) = P (3) + 4 = P (2) + 3 + 4 = 3 + 3 + 4 = 10
P (5) = P (4) + 5 = P (2) + 3 + 4 + 5 = 3 + 3 + 4 + 5 = 15

And using the relationship we discovered above, we see that we can write P (n) as:

1at least if you are making as much mistakes as I usually do, when trying to do this by hand.

P (n) = 3 + (n − (n − 3)) + (n − (n − 4)) + ...(n − (n − n)) = 3 + ∑_{i=3}^{n} i n > 2

Example for n = 5:

P(n=5) = 3 + \underbrace{(n − (n − 3))}_{5−(5−3)=3} + \underbrace{(n − (n − 4))}_{5−(5−4)=4} + \underbrace{(n − (n − n))}_{5−(5−5)=5}
= 3 + 3 + 4 + 5
= 3 + ∑_{i=3}^{n} i
= 15

However, the addition of 3 and the constraint n > 2 is not very elegant. But since P (2) = 3, our equation still holds for n = 2, because by definition of the sum operation ∑_{i=3}^{2} i = 0. So we can say:

P (n) = 3 + ∑_{i=3}^{n} i n > 1

Of course, 3 = 1 + 2, or, more complicated, 3 = ∑_{i=1}^{n} i with n = 2. That means:

P (n) = ∑_{i=1}^{2} i + ∑_{i=3}^{n} i = ∑_{i=1}^{n} i n > 1

But note that ∑_{i=1}^{1} i = 1. That means our equation holds even for n = 1, and knowing that the task defines n as any positive integer, we can get rid of the constraint and simply write:

P (n) = ∑_{i=1}^{n} i

Now that we have a better understanding of P (n), we can try to make guesses on how to calculate this without recursion or summing. We can now write our initial table as:

n  P (n) n^{2}
1  1 = 1  1
2  2 + 1 = 3  4
3  3 + 2 + 1 = 6  9
4  4 + 3 + 2 + 1 = 10 16
5  5 + 4 + 3 + 2 + 1 = 15 25
6 6 + 5 + 4 + 3 + 2 + 1 = 21 36

...

10 10 + 9 + 8... + 2 + 1 = 55 100

I added a column for n^{2}, because we must make a guess on how to calculate P (n) for very big n without summing everything. Since looking at the value for n = 10 helped us earlier, I added this as well. The value 55 looks suspicious, since it is almost the half of 100. We could say that 100 = 50 + 5 = \frac{100}{2} + \frac{10}{2}. Since in this case n = 10, we can set \frac{100}{2} + \frac{10}{2} = \frac{n∗n}{2} + \frac{n}{2}.

So, as a first guess we could try P (n) = \frac{n^{2}}{2} + \frac{n}{2} = \frac{n^{2}+n}{2}. Does this work for other values of n?

\begin{matrix}n & P (n) & \frac{n^{2}+n}{2} \\ 1 & 1 = 1 & 1 \\ 2 & 2 + 1 = 3 & 3 \\ 3 & 3 + 2 + 1 = 6 & \frac{1}{2} · (9 + 3) = 6 \\ 4 & 4 + 3 + 2 + 1 = 10 & \frac{1}{2} · (16 + 4) = 10 \\ 5 & 5 + 4 + 3 + 2 + 1 = 15 & \frac{1}{2} · (25 + 5) = 15 \end{matrix}

Indeed it does. So for the induction step, we assume that P (n) = \frac{n^{2}+n}{2}.

3 Proof

If we assume that this formular holds for P (1)..P (n), we want to proof it for P (n + 1). That would be:

P (n + 1) = \frac{(n + 1)^{2} + (n + 1)}{2}

We know that we can write P (n) as P (n − 1) + n. Based on induction, we set

P (n) + (n + 1) = \frac{n^{2} + n}{2} + (n + 1)

So, to complete our proof, we need to show that:

\frac{(n + 1)^{2} + (n + 1)}{2} = \frac{n^{2} + n}{2} + (n + 1)

First, we can eliminate the division by 2:

\frac{(n + 1)^{2} + (n + 1)}{2} = \frac{n^{2} + n}{2} + \frac{2n + 2}{2}
(n + 1)^{2} + n + 1 = n^{2} + n + 2n + 2
(n + 1)^{2} + n + 1 = n^{2} + 3n + 2

Simplify:

\underbrace{(n + 1)^{2}}_{n^{2}+2n+1} +n + 1 = n^{2} + 3n + 2
n^{2} + 2n + 1 + n + 1 = n^{2} + 3n + 2
n^{2} + 2n + 2 = n^{2} + 3n + 2

And we see that, indeed, our assumption is correct: P (n) = \frac{n^{2}+n}{2}. As a last step, we factor out the n just to get the solution that is given in the book: P (n) = \frac{n^{2}+n}{2} = \frac{n(n+1)}{2}