26 2. Combinatorial Tools
this for the first 10 values ofn; can we be sure that it is valid for all? Well,
I’d say we can be reasonably sure, but not with mathematical certainty.
How can weprovethe assertion?
Consider the sum for a generaln. Thenth odd number is 2n−1 (check!),
so we want to prove that
1+3+···+(2n−3)+(2n−1) =n^2. (2.1)If we separate the last term in this sum, we are left with the sum of the
first (n−1) odd numbers:
1+3+···+(2n−3) + (2n−1) =(
1+3+···+(2n−3))
+(2n−1).Now, here the sum in the large parenthesis is (n−1)^2 , since it is the sum
of the firstn−1 odd numbers. So the total is
(n−1)^2 +(2n−1) = (n^2 − 2 n+1)+(2n−1) =n^2 , (2.2)just as we wanted to prove.
Wait a minute! Aren’t we using in the proof the statement that we are
trying to prove? Surely this is unfair! One could prove everything if this
were allowed!
In fact, we are not quite using the assertion we are trying to prove.
What we were using, was the assertion about the sum of the firstn− 1
odd numbers; and we argued (in (2.2)) that this proves the assertion about
the sum of the firstnodd numbers. In other words, what we have actually
shown is that if the assertion is true for a certain value (n−1), then it is
also true for the next value (n).
This is enough to conclude that the assertion is true for everyn.We
have seen that it is true forn= 1; hence by the above, it is also true for
n= 2 (we have seen this anyway by direct computation, but this shows
that this was not even necessary: It follows from the casen= 1). In a
similar way, the truth of the assertion forn= 2 implies that it is also true
forn= 3, which in turn implies that it is true forn= 4, etc. If we repeat
this sufficiently many times, we get the truth for any value ofn. So the
assertion is true foreveryvalue ofn.
This proof technique is calledinduction(or sometimesmathematical in-
duction, to distinguish it from a notion in philosophy). It can be summa-
rized as follows.
Suppose that we want to prove a property of positive integers. Also
suppose that we can prove two facts:
(a) 1 has the property, and(b) whenevern−1 has the property, thennalso has the property (n>1).