[ Pobierz całość w formacie PDF ]
a recurrence for calculating
andSn;2, instead of needing all previous values.
We have
G(x)2P(x)
=
that is,
1
G(x)2 x;x2 x;:
= ; + [; 1]2
4
3
I am grateful to my colleague Victor Miller for suggesting the method we use
to do this.
230 APPENDIX B. S-EXPRESSIONS OF SIZE N
Expanding the square,
h i
1
P(x) x;x2 2x2 x+1:
= ; + +2
4
Collecting terms,
1 1
P(x) 2x2x+:
= ; 1 ;
4 2 4
Di erentiating,
1
P(x) 2x;:
= ; 2
2 2
We have seen that
X( X
2P(x)n+1)Sn+1xn=P(x)Snxn
where it is understood that the low order terms of the sums have been
\modi P(x)P(x), and multiplying through
ed." Substituting in and
by 2, we obtain
h i h i
X( X
( 2x2 x+1n+1)Sn+1xn= 2x; Snxn:
; 4) ; 2 ( ; 4)
I.e.,
P ;n;S; nS+(n+1)S]x
2
[(n;1nn+1n
4)( 1)
P2
= 2Sn;1 Sn]xn:
[( ; 4) ;
We have thus obtained the followingn 3:
remarkable recurrence for
h i
nSn= 2n;Sn;2 (n; ]Sn;1:(B.2)
; ( ; 4)( 3) +[2 1) ;
If exact ratherSnare desired, this is an
than asymptotic values of
excellent technique for calculating them.
WeSn +2)2Sn;1n 4
now derive ( from this recurrence. For
weSn;1Sn;2,
have, since we knowthat is greater than or equal to
h i h i
Sn 2 + )Sn;1 +2)2Sn;1:
( +4) +(2 (
In = 0, one of the terms of recurrence (B.2)
the special case that
drops out, and we have
n; 3
Sn=4Sn;2:
n
231
From this it can be shown by induction that
!
1 2 1 (2
1n1n)!
S2n=
=
2n;n2n!n!
2 1 2n; 1
which with Stirling's formula [see Feller (1970)]
p
1
;
2
n! nn+en
2
yields the asymptotic estimate we used before. For
p
1
;
2
1n)! (2n)2n+e2n1n
1 (2 1 2 22
p
S2n= =:
h i
1
2n;n!n!n+ n
2 1 4np2 ne2 4n
;n
2
Fornrecurrence (B.2) is essentially
large
( 2Sn;2 Sn;1Sn=0nvery:(B.3)
; 4) ; 2 + ( large)
Recurrences such as (B.3) are well known. See, for example, the dis-
cussion of \Recurring series," and \Solution of di erence equations,"
Exercises 15{16, Chapter VIII, pp. 392{393, Hardy (1952). The lim-
itingSn=Sn;1 must satisfy the following equation:
ratio !
( 2 x+x2:
; 4) ; 2 =0
This quadratic equation factors nicely:
(x; +x; ;:
( 2)) ( ( 2)) = 0
Thus are:
the two roots
= ;
2
1
= +2:
2
The 2 agrees with our previous asymptotic estimate for
larger root
Sn=Sn;1.
232 APPENDIX B. S-EXPRESSIONS OF SIZE N
Appendix C
Back Cover
G.J. Chaitin, the inventor of algorithmic information theory,
presents in this book the strongest possible version of G
odel's
incompleteness theorem, using an information theoretic approach
based on the size of computer programs.
An exponential diophantine equation is explicitly constructed
with the property that certain assertions are independent mathe-
matical facts, that is, irreducible mathematical information that
cannot be compressed into any nite set of axioms.
This is the rst book on this subject and will be of interest to
computer scientists, mathematicians, physicists and philosophers
interested in the nature of randomness and in the limitations of
the axiomatic method.
\Gregory::has
Chaitin:proved the ultimate in undecidability
theorems:::, that the logical structure of arithmetic can be
random:::The assumption that the formal structure of arith-
metic is precise and regular turns out to have been a time-bomb,
and Chaitin has just pushed the detonator." Ian Stewart in Na-
ture
\No one, but no one, is exploring to greater depths the amaz-
ing insights and theorems that ow from G work on un-
odel's
decidability than Gregory Chaitin. His exciting discoveries and
speculations invade such areas as logic, induction, simplicity, the
233
234 APPENDIX C. BACK COVER
philosophy of mathematics and science, randomness, proof the-
ory, 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
[ Pobierz całość w formacie PDF ]