Recursion - Data Structures and Problem Solving Using Java - page 296

Proof of
Theorem 7.1

(continued from previous page)

By assumption, the theorem is true for k , so we may replace the sum on the right-
hand side of Equation 7.1 with kk 1 ( + ) ⁄ 2 , obtaining

k + 1

(7.2)

∑

i = ( k + 1 ) + ( kk 1 ( + ) ⁄ 2 )

i = 1

Algebraic manipulation of the right-hand side of Equation 7.2 now yields

∑

k + 1

i = ( k + 1 ) ( k + 2 ) ⁄ 2

i = 1

This result confirms the theorem for the case k + 1 . Thus by induction, the theorem is

true for all integers N 1 ≥ .

Why does this constitute a proof? First, the theorem is true for N = 1,
which is called the basis . We can view it as being the basis for our belief that
the theorem is true in general. In a proof by induction, the basis is the easy
case that can be shown by hand. Once we have established the basis, we use
inductive hypothesis to assume that the theorem is true for some arbitrary k and
that, under this assumption, if the theorem is true for k, then it is true for k + 1.
In our case, we know that the theorem is true for the basis N = 1, so we know
that it also is true for N = 2. Because it is true for N = 2, it must be true for N =
3. And as it is true for N = 3, it must be true for N = 4. Extending this logic, we
know that the theorem is true for every positive integer beginning with N = 1.

In a proof by induc-
tion, the basis is the
easy case that can
be shown by hand.

Let us apply proof by induction to a second problem, which is not quite as
simple as the first. First, we examine the sequence of numbers , ,
, , , and so on. Each mem-
ber represents the sum of the first N squares, with alternating signs. The
sequence evaluates to 1, 3, 6, 10, and 15. Thus, in general, the sum seems to
be equal to the sum of the first N integers, which, as we know from Theorem
7.1, would be

The inductive
hypothesis
assumes that the
theorem is true for
some arbitrary case
and that, under this
assumption, it is
true for the next
case.

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

NN 1 ( + ) ⁄ 2 . Theorem 7.2 proves this result.

…

∑

1

The sum -() 1

Ni -

i 2 = N 2 - ( N 1 - )

2

+ ( N 2 - )

2

- is NN 1 ( + ) ⁄ 2 .

Theorem 7.2

i N =

Proof

The proof is by induction.

Basis: Clearly, the theorem is true for N = 1 .

( continued on next page)