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  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 .
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  use this representation to determine the average height of
plane trees.
В

80
Greene and Knuth (p. 30 of ) 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
.) 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
 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  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 . 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 ,
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 , who ob-
 << Пред. стр. страница 11(всего 24)ОГЛАВЛЕНИЕ След. стр. >>