Re: [math-fun] limit question
Thanks! I came across it while trying to calculate an upper bound on Chaitin's Omega number for Chris Barker's language Iota. Programs in Iota are completely binary trees (that is, 0 or two children). Internal nodes (1's) apply the left branch to the right, and leaf nodes (0's) are a universal combinator. Omega is inf ___ \
(number of n-bit self-delimiting programs that halt) / 2^n /__ n=1
In Iota, programs are self-delimiting--as soon as there are more leaf nodes than internal nodes, you know you're done. The number of ways to do that for a bit string of length 2n+1 is C(n). The probability that a string starts with a prefix containing more zeros than ones approaches certainty. So I guess the limit is another way of saying, "You can't make a syntax error in Iota!" ----- Original Message Follows -----
about :
inf ___ \ C(n)
---- = 2. /__ 4^n n=0
The limit is 2.
C(n) is slightly lower than 4^n, while the principal term is 4^n, eventually the sum converge to 2, I am not a combinatorist or a wilf-zeilbergerologist but I can say that there is probably a variety of ways to show that.
As a number theorist I would suggest, the series slowly increases so it means you can apply lots of tests for series on it validating the convergence of the sum.
simon plouffe
-- Mike Stay staym@clear.net.nz http://www.cs.auckland.ac.nz/~msta039
Simon> C(n) is slightly lower than 4^n, while the principal term
is 4^n, eventually the sum converge to 2, I am not a combinatorist or a wilf-zeilbergerologist but I can say that there is probably a variety of ways to show that.
My HYPERSIMP Macsyma function can sum Catalan(n)/4^n (without WZ): (c29) (sum(binomial(2*n,n)/(n+1)/4^n,n,0,inf),%% = hypersimp(%%)) inf ==== \ binomial(2 n, n) (d29) > ---------------- = 2 / n ==== 4 (n + 1) n = 0 --rwg
-----Original Message----- On Behalf Of R. William Gosper Sent: Friday, January 30, 2004 3:10 AM To: math-fun@mailman.xmission.com; staym@clear.net.nz Subject: Re: [math-fun] limit question
Simon> C(n) is slightly lower than 4^n, while the principal term
is 4^n, eventually the sum converge to 2, I am not a combinatorist or a wilf-zeilbergerologist but I can say that there is probably a variety of ways to show that.
My HYPERSIMP Macsyma function can sum Catalan(n)/4^n (without WZ): (c29) (sum(binomial(2*n,n)/(n+1)/4^n,n,0,inf),%% = hypersimp(%%))
inf ==== \ binomial(2 n, n) (d29) > ---------------- = 2 / n ==== 4 (n + 1) n = 0
Maple can do that sum, too, sum(binomial(2*n,n)/4^n/(n+1),n=0..infinity); 2 This is a simple thing. The generating function for Catalan numbers is infinity 1/2 ----- 1 - (1 - 4 x) \ n ---------------- = ) C(n) x 2 x / ----- n = 0 For x=1/4, it equals 2. The series is convergent because C(n) ~ 4^n/(pi^(1/2)*n^(3/2)). Alec Mihailovs http://webpages.shepherd.edu/amihailo/
-----Original Message----- From: Emeric Deutsch [mailto:deutsch@duke.poly.edu] Sent: Friday, January 30, 2004 7:18 AM To: alec@mihailovs.com; math-fun Subject: RE: [math-fun] limit question
Maple gives
S:=n->sum(binomial(2*k,k)/(k+1)/4^k,k=0..n): simplify(S(n));
(-n) - 1/2 binomial(2 n + 2, n + 1) 4 + 2
S(infinity);
2
I repeat, just in case, S(n)=2 - binomial(2n+2,n+1)/2^(2n+1).
That's interesting. The formula for S(n) can be also obtained using generating functions. Let S(n,x)=C(0)+C(1)x+...+C(n)x^n. The generating function for S(n,x) is infinity 1/2 ----- 1 - (1 - 4 x t) \ n ------------------ = ) S(n, x) t 2 x t (1 - t) / ----- n = 0 For x=1/4, we have infinity 1/2 ----- 2 (1 - (1 - t) ) \ n ------------------ = ) S(n) t t (1 - t) / ----- n = 0 2/t(1-t) gives 2 in the formula for S(n), and the coefficient at t^n in 2(1-t)^(1/2)/(t(1-t)) = 2/t*(1-t)^(-1/2) gives the second term. Alec Mihailovs http://webpages.shepherd.edu/amihailo/
participants (4)
-
Alec Mihailovs -
Emeric Deutsch -
Mike Stay -
R. William Gosper