TAOCP 1.2.1 Exercise 7

Define S_n=n^2-(n-1)^2+(n-2)^2-\cdots+(-1)^{n-1}1^2 =\sum_{i=1}^n (-1)^{\,n-i} i^2.

taocpmathematicsalgorithmsvolume-1medium

Section 1.2.1: Mathematical Induction

Exercise 7. [23] Formulate and prove by induction a rule for the sums $1^2$, $2^2 - 1^2$, $3^2 - 2^2 + 1^2$, $4^2 - 3^2 + 2^2 - 1^2$, $5^2 - 4^2 + 3^2 - 2^2 + 1^2$, etc.

Verified: yes
Solve time: 1m46s

Define

$$ S_n=n^2-(n-1)^2+(n-2)^2-\cdots+(-1)^{n-1}1^2 =\sum_{i=1}^n (-1)^{,n-i} i^2. $$

Computing the first few values gives

$$ S_1=1,\qquad S_2=4-1=3,\qquad S_3=9-4+1=6, $$

$$ S_4=16-9+4-1=10,\qquad S_5=25-16+9-4+1=15. $$

These are the triangular numbers:

$$ 1,3,6,10,15,\dots $$

so we conjecture that

$$ S_n=\frac{n(n+1)}2. $$

We now prove this formula by induction on $n$.

First observe that the sums satisfy the recurrence

$$ S_{n+1}=(n+1)^2-S_n. $$

Indeed,

$$ S_{n+1} =(n+1)^2-n^2+(n-1)^2-\cdots+(-1)^n1^2, $$

while

$$ S_n =n^2-(n-1)^2+\cdots+(-1)^{n-1}1^2, $$

so subtracting $S_n$ from $(n+1)^2$ produces exactly $S_{n+1}$.

We prove that

$$ S_n=\frac{n(n+1)}2 $$

for all $n\ge1$.

Base case

For $n=1$,

$$ S_1=1^2=1, $$

and

$$ \frac{1(1+1)}2=1. $$

Thus the formula holds for $n=1$.

Induction step

Assume that for some $n\ge1$,

$$ S_n=\frac{n(n+1)}2. $$

Using the recurrence relation,

$$ S_{n+1}=(n+1)^2-S_n. $$

Substitute the induction hypothesis:

$$ S_{n+1} =(n+1)^2-\frac{n(n+1)}2. $$

Factor out $n+1$:

$$ S_{n+1} =(n+1)\left((n+1)-\frac n2\right). $$

Simplify the expression in parentheses:

$$ (n+1)-\frac n2 =\frac{2n+2-n}{2} =\frac{n+2}{2}. $$

Hence

$$ S_{n+1} =(n+1)\frac{n+2}{2} =\frac{(n+1)(n+2)}2. $$

This is exactly the desired formula with $n$ replaced by $n+1$. Therefore the statement holds for $n+1$.

By mathematical induction,

$$ \boxed{ 1^2-2^2+3^2-\cdots+(-1)^{n-1}n^2 =\frac{n(n+1)}2 } $$

in the ordering given by the exercise, namely

$$ \boxed{ n^2-(n-1)^2+(n-2)^2-\cdots+(-1)^{n-1}1^2 =\frac{n(n+1)}2. } $$