LINEBURG

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-

Copyright Design by: Sunlight webdesign