Information Technology Reference
In-Depth Information
(
)
Step 1 is usually the easy step. Step 2 is typically handled as follows:
assume
that
S
n
(
+
)
is true for an arbitrary choice of
n
, and then use that to
prove
that
S
n
1
will also
be true.
To see this in action, let us do these proofs. The standard mathematical summation
notation (with the Greek letter
sigma
)
n
i
=
0
i
means “the sum of the natural numbers from
0
to
n
.” So the following statement is to
be proved by mathematical induction:
n
i
=
0
i
=
(
+
)
n
n
1
For all natural numbers
n
,
.
2
Here is the proof:
1.
Consider the case where
n
=
0.Wehave
0
i
=
0
i
=
0
=
×
0
1
.
2
(
)
So
S
0
is true.
(
)
(
+
)
2.
Prove that whenever
S
n
is true, then
S
n
1
is also true.
(
)
Assume that for some arbitrary
n
,
S
n
is true. This means that
n
i
=
0
i
=
(
+
)
n
n
1
.
2
If this is true, we have
n
n
i
=
0
i
1
i
=
0
+
n
(
n
+
1
)
=
+(
+
)=
+(
+
)
i
n
1
n
1
.
2
But
n
2
+
1
n
(
n
+
)
)
(
n
+
)
1
2
+(
+
)=(
+
)
=(
+
n
1
n
1
n
1
.
2
2
Combining this with the previous equation, we have
+
n
1
i
=
0
=
(
+
)(
+
)
n
1
n
2
i
.
2
So this proves that
S
(
n
+
1
)
is true.
That completes the proof.