Chaitin. Algorithmic information theory

229

We now replace the above (n − 2)-term recurrence for Sn by a twoterm recurrence.3

The rst step is to eliminate the annoying middle term by completing the square. We replace the original generating function F by a new generating function whose coe cients are the same for all terms of degree 2 or higher:

G(x) F (x) + 12 (− x − 1) :

With this modi ed generating function, we have

where we introduce the notation P for the second degree polynomial on the right-hand side of this equation. I.e.,

G(x)2 = P (x):

Di erentiating with respect to x, we obtain

2G(x)G0(x) = P 0(x):

Multiplying both sides by G(x),

2G(x)2G0(x) = P 0(x)G(x);

and thus

2P (x)G0(x) = P 0(x)G(x);

from which we now derive a recurrence for calculating Sn from Sn−1 and Sn−2, instead of needing all previous values.

We have

G(x)2 = P (x);

that is,

G(x)2 = − x − x2 + 14 [− x − 1]2 :

3I am grateful to my colleague Victor Miller for suggesting the method we use to do this.

We have seen that

2P (x) X(n + 1)Sn+1xn = P 0(x) X Snxn;

where it is understood that the low order terms of the sums have been \modi ed." Substituting in P (x) and P 0(x), and multiplying through by 2, we obtain

h i h i

( 2 − 4)x2 − 2 x + 1 X(n + 1)Sn+1xn = ( 2 − 4)x − X Snxn:

I.e.,

P[( 2 − 4)(n − 1)Sn−1 − 2 nSn + (n + 1)Sn+1] xn

=P [( 2 − 4)Sn−1 − Sn] xn:

We have thus obtained the following remarkable recurrence for n 3:

h i

nSn = − ( 2 − 4)(n − 3) Sn−2 + [2 (n − 1) − ] Sn−1: (B.2)

If exact rather than asymptotic values of Sn are desired, this is an excellent technique for calculating them.

We now derive Sn ( + 2)2Sn−1 from this recurrence. For n 4 we have, since we know that Sn−1 is greater than or equal to Sn−2,

h i h i

Sn ( 2 + 4) + (2 + ) Sn−1 ( + 2)2 Sn−1:

In the special case that = 0, one of the terms of recurrence (B.2) drops out, and we have

n − 3

Sn = 4 n Sn−2:

Recurrences such as (B.3) are well known. See, for example, the discussion of \Recurring series," and \Solution of di erence equations," Exercises 15{16, Chapter VIII, pp. 392{393, Hardy (1952). The limiting ratio Sn=Sn−1 ! must satisfy the following equation:

( 2 − 4) − 2 x + x2 = 0:

This quadratic equation factors nicely:

(x − ( + 2)) (x − ( − 2)) = 0:

Thus the two roots are:

1 = − 2;2 = + 2:

The larger root 2 agrees with our previous asymptotic estimate for

Sn=Sn−1.

philosophy of mathematics and science, randomness, proof theory, chaos, information theory, computer complexity, diophantine analysis, and even the origin and evolution of life. If you haven't yet encountered his brilliant, clear, creative, wide-ranging mind, this is the book to read and absorb." Martin Gardner