PRELIMINARY ALGEBRA
This is precisely the original assumption, but withNreplaced byN+ 1. To complete the
proof we only have to verify (1.60) forn= 1. This is trivially done and establishes the
result for all positiven. The same and related results are obtained by a different method
in subsection 4.2.5.
Our second example is somewhat more complex and involves two nested proofsby induction: whilst trying to establish the main result by induction, we find that
we are faced with a second proposition which itself requires an inductive proof.
Show thatQ(n)=n^4 +2n^3 +2n^2 +nis divisible by 6 (withoutremainder) for all positive
integer values ofn.Again we start by assuming the result is true for some particular valueNofn, whilst
noting that it is trivially true forn= 0. We next examineQ(N+ 1), writing each of its
terms as a binomial expansion:
Q(N+1)=(N+1)^4 +2(N+1)^3 +2(N+1)^2 +(N+1)
=(N^4 +4N^3 +6N^2 +4N+1)+2(N^3 +3N^2 +3N+1)
+2(N^2 +2N+1)+(N+1)
=(N^4 +2N^3 +2N^2 +N)+(4N^3 +12N^2 +14N+6).Now, by our assumption, the group of terms within the first parentheses in the last line
is divisible by 6 and clearly so are the terms 12N^2 and 6 within the second parentheses.
Thus it comes down to deciding whether 4N^3 +14Nis divisible by 6 – or equivalently,
whetherR(N)=2N^3 +7Nis divisible by 3.
To settle this latter question we try using a second inductive proof and assume that
R(N)isdivisible by 3 forN=M, whilst again noting that the proposition is trivially true
forN=M= 0. This time we examineR(M+1):
R(M+1)=2(M+1)^3 +7(M+1)
=2(M^3 +3M^2 +3M+1)+7(M+1)
=(2M^3 +7M)+3(2M^2 +2M+3)By assumption, the first group of terms in the last line is divisible by 3 and the second
group is patently so. We thus conclude thatR(N) is divisible by 3 for allN≥M,and
takingM= 0 shows that it is divisible by 3 for allN.
We can now return to the main proposition and conclude that sinceR(N)=2N^3 +7N
is divisible by 3, 4N^3 +12N^2 +14N+ 6 is divisible by 6. This in turn establishes that the
divisibility ofQ(N+ 1) by 6 follows from the assumption thatQ(N) divides by 6. Since
Q(0) clearly divides by 6, the proposition in the question is established for all values ofn.
1.7.2 Proof by contradictionThe second general line of proof, but again one that is normally only useful when
the result is already suspected, is proof by contradiction. The questions it can
attempt to answer are only those that can be expressed in a proposition that
is either true or false. Clearly, it could be argued that any mathematical result
can be so expressed but, if the proposition is no more than a guess, the chances
of success are negligible. Valid propositions containing even modest formulae
are either the result of true inspiration or, much more normally, yet another
reworking of an old chestnut!