Java Reference
In-Depth Information
By direct inspection of the second line of the table, we might recognize the
pattern f(n) =
2
n
1
2
n
. A simple induction proof can then prove that this
always holds true. Alternatively, consider if we hadn't noticed the pattern
for the form of f(n). We might observe that f(n) appears to be reaching
an asymptote at one. In which case, we might consider looking at the dif-
ference between f(n) and the expected asymptote. This result is shown in
the last line of the table, which has a clear pattern since the ith entry is of
1=2
i
. From this we can easily deduce a guess that f(n) = 1
1
2
n
. Again,
a simple induction proof will verify the guess.
Example14.3
Solve the summation
n
X
ar
i
= a + ar + ar
2
+ + ar
n
:
f(n) =
i=0
This is called a geometric series. Our goal is to find some function g(n)
such that the difference between f(n) and g(n) one from the other leaves
us with an easily manipulated equation. Because the difference between
consecutive terms of the summation is a factor of r, we can shift terms if
we multiply the entire expression by r:
n
X
ar
i
= ar + ar
2
+ ar
3
+ + ar
n+1
:
rf(n) = r
i=0
We can now subtract the one equation from the other, as follows:
f(n) rf(n) = a + ar + ar
2
+ ar
3
+ + ar
n
(ar + ar
2
+ ar
3
+ + ar
n
) ar
n+1
:
The result leaves only the end terms:
f(n) rf(n)
n
n
X
X
ar
i
r
ar
i
:
=
i=0
i=0
= aar
n+1
:
(1 r)f(n)
Thus, we get the result
f(n) =
aar
n+1
1 r
where r 6= 1:
