Java Reference
In-Depth Information
Dividing by both n and f(n 1) happen to give us useful patterns to
work with.
f(n)
n
f(n)
n+1
n+1
n1
. Of course, lots of other
guesses for function g do not work. For example, f(n) n = f(n
1). Knowing that f(n) = f(n 1) + n is not useful for determining the
closed form solution to this summation. Or consider f(n)f(n1) = n.
Again, knowing that f(n) = f(n 1) + n is not useful. Finding the right
combination of equations can be like finding a needle in a haystack.
In our first example, we can see directly what the closed-form solution
should be. Since
f(n)
n
=
n+1
2
, obviously f(n) = n(n + 1)=2.
Dividing f(n) by f(n 1) does not give so obvious a result, but it
provides another useful illustration.
=
2
, and
f(n1)
=
f(n)
f(n 1)
n + 1
n 1
=
f(n)(n 1)
=
(n + 1)f(n 1)
f(n)(n 1)
=
(n + 1)(f(n) n)
= nf(n) + f(n) n
2
n
nf(n) f(n)
= n
2
+ n = n(n + 1)
2f(n)
n(n + 1)
2
f(n)
=
Once again, we still do not have a proof that f(n) = n(n+ 1)=2. Why?
Because we did not prove that f(n)=n = (n + 1)=2 nor that f(n)=f(n
1) = (n + 1)(n 1). We merely hypothesized patterns from looking at a
few terms. Fortunately, it is easy to check our hypothesis with induction.
Example14.2
Solve the summation
n
X
1=2
i
:
i=1
We will begin by writing out a table listing the first few values of the sum-
mation, to see if we can detect a pattern.
n 1 2 3 4 5 6
f(n)
1
2
3
4
7
8
15
16
31
32
63
64
1 f(n)
1
2
1
4
1
8
1
16
1
32
1
64
