Java Reference
In-Depth Information
n
2
n + 2n
2
=
n(n + 1)
2
=
:
Thus, by mathematical induction,
n
X
S(n) =
i = n(n + 1)=2:
i=1
2
Note carefully what took place in this example. First we cast S(n) in terms
of a smaller occurrence of the problem: S(n) = S(n 1) + n. This is important
because once S(n 1) comes into the picture, we can use the induction hypothesis
to replace S(n 1) with (n 1)(n)=2. From here, it is simple algebra to prove
that S(n 1) + n equals the right-hand side of the original theorem.
Example2.12
Here is another simple proof by induction that illustrates
choosing the proper variable for induction. We wish to prove by induction
that the sum of the first n positive odd numbers is n
2
. First we need a way
to describe the nth odd number, which is simply 2n 1. This also allows
us to cast the theorem as a summation.
Theorem2.3
P
i=1
(2i 1) = n
2
.
Proof:
The base case of n = 1 yields 1 = 1
2
, which is true. The induction
hypothesis is
n1
X
(2i 1) = (n 1)
2
:
i=1
We now use the induction hypothesis to show that the theorem holds true
for n. The sum of the first n odd numbers is simply the sum of the first
n 1 odd numbers plus the nth odd number. In the second line below, we
will use the induction hypothesis to replace the partial summation (shown
in brackets in the first line) with its closed-form solution. After that, algebra
takes care of the rest.
n
X
"
n
X
#
(2i 1)
=
(2i 1)
+ 2n 1
i=1
i=1
= [(n 1)
2
] + 2n 1
= n
2
2n + 1 + 2n 1
= n
2
:
Thus, by mathematical induction,
P
i=1
(2i 1) = n
2
.
2
