Java Reference
In-Depth Information
Proof of
Theorem 7.2
(continued from previous page)
Inductive hypothesis: First we assume that the theorem is true for k :
kk 1
(
+
)
1
-()
1
ki
-
i 2
=
-------------------
.
i k
=
2
Then we must show that it is true for
k
+
1
, namely, that
(
k
+
1
)
(
k
+
2
)
1
-()
1
k
+
1
-
i
i 2
=
----------------------------------
2
i k 1
=
+
We write
1
(7.3)
-()
1
k
+
1
-
i
i 2
=
(
k
+
1
)
2
-
k 2
+
(
k
-
1
)
2
-
i k 1
=
+
If we rewrite the right-hand side of Equation 7.3, we obtain
( k 2
2
1
-()
1
k
+
1
-
i
i 2
=
(
k
+
1
)
2
-
-
(
k
-
1 )
+
)
i k 1
=
+
and a substitution yields
1
1
(7.4)
-()
1
k
+
1
-
i
i 2
=
(
k
+
1
)
2
-
(
-()
1
ki
-
i 2
)
i k 1
=
+
i k
=
If we apply the inductive hypothesis, then we can replace the summation on the right-
hand side of Equation 7.4, obtaining
1
(7.5)
()
-
1
k
+
1
-
i
i 2
=
(
k
+
1
)
2
-
kk 1
(
+
)
2
i k 1
=
+
Simple algebraic manipulation of the right-hand side of Equation 7.5 then yields
1
-()
1
i 2
=
(
k
+
1
)
(
k
+
2
)
2
k
+
1
-
i
i k 1
=
+
which establishes the theorem for
Nk 1
=
+
. Thus, by induction, the theorem is true
for all
N 1
.
basic recursion
7.3
Proofs by induction show us that, if we know that a statement is true for a
smallest case and can show that one case implies the next case, then we know
the statement is true for all cases.
Sometimes mathematical functions are defined recursively. For instance,
let S ( N ) be the sum of the first N integers. Then S (1) = 1, and we can write
S ( N ) = S ( N - 1) + N . Here we have defined the function S in terms of a smaller
instance of itself. The recursive definition of S ( N ) is virtually identical to the
closed form S ( N ) = N ( N + 1) / 2, with the exception that the recursive defini-
tion is only defined for positive integers and is less directly computable.
A recursive method
is defined in terms
of a smaller
instance of itself.
There must be
some base case
that can be com-
puted without
recursion.
 
 
Search WWH ::




Custom Search