2.3. The Principle of Induction
Exercise 2.3.9:
Is the sum of the first
n square numbers equal to
(n + 2)/3 ?
Back
We might try to prove this statement via induction
 Property Q(n):

1^{2} + 2^{2} + 3^{2} + ... + n^{2} = (n + 2) / 3
 Check Q(1):
 1^{2} = 3/3 is true
 Assume Q(n) is true:
 Assume that
1^{2} + 2^{2} + 3^{2} + ... + n^{2} = (n + 2) / 3
 Check Q(n+1):

1^{2} + 2^{2} + 3^{2} + ... + (n + 1)^{2} =
= (1^{2} + 2^{2} + 3^{2} + ... + n^{2}) +
(n+1)^{2} =
= (n + 2) / 3 + 3 (n + 1)^{2} / 3 =
= 1/3 (3 n^{2} + 7n + 5)
which is not equal to (n+3)/3
Hence, the induction proof failed. That does not, in principle, mean that the
statement is false. It is, however, a strong indication that property Q(n)
is false. Indeed, checking for
n = 2 gives:
so that the statement is indeed false by this counterexample.