LINEBURG


<< . .

 11
( 24)



. . >>

Then an satis¬es the linear recurrence

2 1
an+2 ’ 2 ’ an+1 + 1 ’ an = 0, n≥0. (9.37)
n n

The methods of [244] can be used to show that for some constants c and φ

an = cn’1/4 sin(2n1/2 + φ) + o(n’1/4 ) as n’∞, (9.38)

which is a much more precise estimate than the crude one mentioned in Example 10.1.
Another, in some ways preferable method for obtaining asymptotic expansions for a n is
mentioned in Example 12.8. It is based on an explicit form for the generating function of
an z n . An interchange of orders of summation (easily justi¬ed for |z| small, say
an , f (z) =
|z| < 1/2) shows that
∞ ∞
(’1)k nn
f (z) = z
k! k
k=0 n=k


(’1)k zk 1 z
= = exp ’ . (9.39)
k! (1 ’ z)k+1 1’z 1’z
k=0

The saddle point method can then be applied to obtain asymptotic expansions for a n .
 




9.3. Linear recurrences in several variables

Linear recurrences in several variables that have constant coe¬cients can be attacked by
methods similar to those used in a single variable. If we have


d d
am,n = ci,j am’i,n’j (9.40)
i=0 i=0
i+j>0


for m, n ≥ d, say, then the generating function
∞ ∞
am,n xm y n
f (x, y) = (9.41)
m=0 n=0




78
satis¬es the relation
« 
¬ ·
∞ ∞
d d
ci,j xi y j · = am,n xm y n
¬ ·
f (x, y) ¬1 ’
¬ ·
i=0 i=0 m=0 n=0
 
i+j>0 m>d n>d
or

(9.42)

d d
am,n xm y n .
cij xi y j

m,n
i=0 i=0 m¤d’i
i+j>0 or n¤d’i


If am,n = 0 for 0 ¤ m < d and n ≥ d as well as for 0 ¤ n < d and m ≥ d (so that all the a m,n
are fully determined by am,n for 0 ¤ m < d, 0 ¤ n < d), then f (x, y) is a rational function. If
this condition does not hold, f (x, y) can be complicated.
The paragraph above shows that under common conditions, constant coe¬cient recurrences
lead to generating functions that are rational even in several variables. However, even when
the rational function is determined, there is no equivalent of partial fraction decomposition to
yield elegant asymptotics of the coe¬cients. Coe¬cients of multivariate generating functions
are much harder to handle than those of univariate functions. There are tools (discussed in
Section 13), that are usually adequate to handle rational generating functions, but they are
not simple.
When the coe¬cients of the multivariate recurrences vary, available knowledge is extremely
limited. Even if the coe¬cients are polynomials, we obtain a partial di¬erential equation for
the generating function. Sometimes there are tricks that lead to a simple solution (cf. Exam-
ple 15.6), but this is not common.

9.4. Nonlinear recurrences

Nonlinear recurrences come in a great variety of shapes, and the methods that are used
to solve them are diverse, depending on the nature of the problem. This section presents a
sample of the most useful techniques that have been developed.
Sometimes a nonlinear recurrence has a simple solution because of a nice algebraic factor-
ization. For example, suppose that z 0 is any given complex number, and
2
zn+1 = zn ’ 2 for n≥0. (9.43)

If we set
w = (z0 + (z0 ’ 4)1/2 )/2 ,
2
(9.44)

79
we have z0 = w + w’1 , and more generally
n n
zn = w2 + w’2 for n≥0. (9.45)

Eq. (9.45) is easily established through induction. However, this is an exceptional instance, and
2
already recurrences of the type zn+1 = zn + c for c a complex constant lead to deep questions
about the Mandelbrot set and chaotic behavior [91].
Since linear recurrences are well understood, the best that one can hope for when confronted
with a nonlinear recurrence is that it might be reducible to a linear one. This works in many
situations.

Example 9.5. Planted plane trees. Let a n,h be the number of planted plane trees with n
nodes and height ¤ h [64, 177], and let

an,h z n .
Ah (z) = (9.46)
n=0

Since a tree of height ¤ h + 1 has a root and any number of subtrees, each of height ¤ h,

Ah+1 (z) = z(1 + Ah (z) + Ah (z)2 + · · ·)

= z(1 ’ Ah (z))’1 . (9.47)

Iterating this recurrence, we obtain a ¬nite continued fraction that looks like
z
Ah+1 (z) = . (9.48)
z
1’ z
1’ 1...

The general theory of continued functions represents a convergent as a quotient of two sequences
satisfying recurrences involving the partial quotients. (For references, see [218, 319].) After
playing with this idea, one ¬nds that the substitution
zPh (z)
Ah (z) = (9.49)
Ph+1 (z)
gives
Ph+1 (z) = Ph (z) ’ zPh’1 (z) , h≥2,

where P0 (z) = 0, P1 (z) = 1. This is a linear recurrence when we regard z as ¬xed, and so the
theory presented before leads to the explicit representation
± 
 1 + (1 ’ 4z)1/2 h h
1 ’ (1 ’ 4z)1/2
’1/2
Ph (z) = (1 ’ 4z) ’ . (9.50)
2 2
 

De Bruijn, Knuth, and Rice [64] use this representation to determine the average height of
plane trees.
 




80
Greene and Knuth (p. 30 of [177]) note that the continued fraction method of replacing a
convergent by a quotient of elements of two sequences in general leads not to a single sequence
of polynomials like the Ph (z) of Example 9.5, but to two sequences. This is only slightly harder
to handle, and allows one to linearize more complicated recurrences.
There are many additional ways to linearize a recurrence. (A small list is given on p. 31 of
[177].) For example, a purely multiplicative relation a n = a2 /an’2 is transformed into the
n’1

linear log an = 2 log an’1 ’ log an’2 by taking logarithms. One of the most fruitful tricks of
this type is taking inverses. Thus a n = an’1 /(1 + an’1 ) is equivalent to

1 1
= +1 , (9.51)
an an’1

which has the obvious solution a’1 = a’1 + n. (This assumes a0 = ’1/k for any k ∈ +.)
n 0 ¢




Linearization works well, but is limited in applicability. More widely applicable, but pro-
ducing answers that are not as clear, is approximate linearization, where a given nonlinear
recurrence is close to a linear one. The following example combines approximate linearization
with bootstrapping.

Example 9.6. A quadratic recurrence. The study of the average height of binary trees in
[132] involves the recurrence

an = an’1 (1 ’ an’1 ) for n≥1, (9.52)

with a0 = 1/2. The an are monotone decreasing, so we try the inverse trick. We ¬nd

1 1 1 an’1
= = +1+ . (9.53)
an an’1 (1 ’ an’1 ) an’1 1 ’ an’1

Iterating this recurrence (but applying it only to the ¬rst term on the right-hand side of
Eq. (9.53)) we obtain
1 1 an’2 an’1
= +2+ +
an an’2 1 ’ an’2 1 ’ an’1

= ···

n’1
1 aj (9.54)
= +n+
a0 1 ’ aj
j=0

n’1
aj
= n+2+ .
1 ’ aj
j=0


81
Equation (9.54) shows that a’1 > n, so an < 1/n. Applying this bound to aj for 2 ¤ j ¤ n ’ 1
n

in the sum on the right-hand side of Eq. (9.54), we ¬nd that

n ¤ a’1 ¤ n + O(log n) . (9.55)
n


When we substitute this into (9.54), we ¬nd that a ’1 = n + log n + o(log n), and further
n

iterations produce even more accurate estimates.
 




Approximate linearization also works well for some rapidly growing sequences.

Example 9.7. Doubly exponential sequences. Many recurrences are of the form

an+1 = a2 + bn , (9.56)
n


where bn is much smaller than a2 (and may even depend on the an for k ¤ n, as in bn = an or
n

bn = an’1 ). Aho and Sloane [3] found that surprisingly simple solutions to such recurrences can
often be found. The basic idea is to reduce to approximate linearization by taking logarithms.
We ¬nd that if a0 is the given initial value, and an > 0 for all n, then the transformation

un = log an , (9.57)

δn = log(1 + bn a’2 ) , (9.58)
n


reduces (9.56) to
un+1 = 2un + δn , n≥0. (9.59)

Therefore

un = δn’1 + 2un’1 = δn’1 + 2δn’2 + 4un’2

= ...
n
2j’1 δn’j + 2n u0
=
j=1
= 2 (u0 + δ0 /2 + δ1 /4 + · · · + δn’1 /2n ) .
n
(9.60)

If we assume that the δk are small, then

δk 2’k’1
± = u0 + (9.61)
k=0

exists, and

n n
δk 2’k’1 .
rn = u n ’ 2 ± = 2 (9.62)
k=n


82
If the δk are su¬ciently small, the di¬erence r n in (9.62) will be small, and

an = exp(un ) = exp(2n ± ’ rn ) . (9.63)

The expression (9.63) might not seem satisfactory, since both a n and rn are expressed in terms
of all the ak , for k < n and for k ≥ n. The point of (9.63) is that for many recurrences, r n
is negligibly small, while ± is given by the rapidly convergent series (9.61), so that only the
¬rst few an are needed to obtain a good estimate for the asymptotic behavior of a n . We next
discuss a particularly elegant case.
Suppose that an ≥ 1 and |bn | < an /4 for all n ≥ 0. Then an+1 ≥ an and |δn+1 | ¤ |δn | for
n ≥ 0, and so |rn | ¤ |δn |. Hence

an exp(’|δn |) ¤ exp(2n ±) ¤ an exp(|δn |) (9.64)

and since
¤ 1 + |bn |a’2 < 1 + (4an )’1 ,
exp(|δn |) n
(9.65)
exp(’|δn |) ≥ (1 + (4an )’1 )’1 ≥ 1 ’ (3an )’1 ,
we ¬nd that
|an ’ exp(2n ±)| < (2an )’1 ¤ 1/2 . (9.66)

If an is an integer, then we can assert that it is the closest integer to exp(2 n ±).
The restriction |bn | < an /4 is severe. The basic method applies even without it, and the
expansion (9.63) is valid, for example, if we only require that |δ n+1 | ¤ |δn | for n ≥ n0 . However,
we will not in general obtain results as nice as (9.66) if we only impose these weak conditions.
The method outlined above can be applied to recurrences that appear to be of a slightly
di¬erent form. Sometimes only a trivial transformation is required. For example, Golomb™s
nonlinear recurrence,
an+1 = a0 a1 · · · an + b, a0 = 1 , (9.67)

for b a constant, is easily seen to be equivalent to

an+1 = (an ’ b)an + b, a0 = 1, a1 = b + 1 . (9.68)

The substitution
xn = an ’ b/2 (9.69)

transforms (9.68) into
xn+1 = x2 + (2 ’ b)b/4 , (9.70)
n


83
which is of the form treated above. (If the x n are integers, the inequality (9.66) with x n
replacing an might not apply to the xn because the condition |(2 ’ b)b/4| < |x k |/4 might fail
for some k. The trick to use here is to start the recurrence with some x k , say xk0 , so that the
condition |(2 ’ b)b/4| < |xk |/4 applies for k ≥ k0 . The new ± for which (9.66) holds will then
be de¬ned in terms of xk0 , xk0 +1 , . . . .)
In some situations the results presented above cannot be applied, but the basic method
can still be extended. That is the case for the recurrence

an+1 = an an’1 + 1, a 0 , a1 ≥ 1 (9.71)

of [3]. The result is that an is the nearest integer to

±Fn β Fn’1 , (9.72)

where ± and β are positive constants, and the F k are the Fibonacci numbers. What matters
is that the recurrence leads to doubly exponential (and regular) growth of a n . Example 15.3
shows how this principle can be applied even when the a n are not numbers, but polynomials
whose coe¬cients need to be estimated.
 




9.5. Quasi-linear recurrences

This section mentions some methods and results for studying recurrences that have lin-
earity properties, but are not linear. The most important of them are recurrences involving
minimization or maximization. They arise frequently in problems that use dynamic program-
ming approaches and in divide and conquer methods. An important example, treated in [147],
is that of a sequence fn , given by f0 = 1 and

fn+1 = gn+1 + min (±fk + βfn’k ) for n ≥ 0 , (9.73)
0¤k¤n

where ±, β > 0, and gn is some given sequence. Fredman and Knuth showed that if g n = 0 for
n ≥ 1 and ± + β < 1, then

fn ≥ cn1+1/γ for some c = c(±, β) > 0 , (9.74)

where γ is the solution to
±’γ + β ’γ = 1 . (9.75)




84
They proved that lim fn n’1’1/γ exists if and only if (log ±)/(log β) is irrational. They also
n’∞
presented analyses of this recurrence for ± + β ≥ 1, as well as of several recurrences that have
di¬erent gn .
The value of the Fredman-Knuth paper is less in the precise results they obtain for several
recurrences of the type (9.73) than in the methods they develop, which allow one to analyze
related problems. A crucial role in their approach is played by the observation that for the g n
they consider, the minimum in (9.73) can be located rather precisely. The conditions for such
localization are applicable to many other sequences as well.
Further work on the recurrence (9.73) was done by Kapoor and Reingold [220], who ob-

<< . .

 11
( 24)



. . >>

Copyright Design by: Sunlight webdesign