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.
 
Search WWH ::




Custom Search