Date: Fri, 20 Oct 95 15:31:32 CDT From: rusin (Dave Rusin) To: rusin@washington.math.niu.edu Subject: Re: help with recurrence formulas Newsgroups: sci.math Hi, self! In article <468quk$6sn@muir.math.niu.edu> you write: >I'm pretty sure you can push this further and conclude that g(n)/phi^n >is not only bounded above and below but in fact converges to some limit >L; I'm not inclined to puruse the details, but this leaves you with >the estimate g(n) ~ L * phi^n, and thus f(n) ~ exp(L*phi^n). Right. The recurrence f(n)=f(n-1)*(1+f(n-2)) leads to g(n)=g(n-1)+g(n-2)+log(1+exp(-g(n-2))), and so letting k(n)=g(n)/phi^n, we have k(n)=k(n-1)/phi + k(n-2)/phi^2 + log(1+exp(-phi^(n-2)*k(n-2)))/phi^n. We wish to show k converges knowing it is bounded. Let l(n)=k(n)-k(n-1). l(n) = k(n-1)(1/phi-1)+k(n-2)/phi^2+log(1+exp(-phi^(n-2)*k(n-2)))/phi^n which simplifies as follows: phi^2=phi+1, so 1/phi-1=(phi-1)-1=phi-2 and 1/phi^2=phi^2-2phi+1=2-phi; thus l(n)=(phi-2) * l(n-1) + log(etc) So we add to get l(n) = log(1+1/f(n-2))/phi^n + (phi-2)*log(1+1/f(n-3)))/phi^(n-1) + ...; since phi*(phi-2) =1-phi, this is =1/phi^n{ Sum( (1-phi)^i * log(1+1/f(n-2-i)) , i = 0, ..., n-3 ) }. Considering the dominant term, it is easy to see that this alternating series has a sum which is a (negative) exponential in n. Thus the seqence k(n) = sum l(n-k) converges. The limiting value is lim_n k(n) = lim_n Sum_(22; 0<=i0} 1/phi^(2+i+j) * (1-phi)^i * log(1+1/f(j)) = 1/phi^2 * Sum_{i>=0,j>0} 1/phi^(i+j) (1-phi)^i * log(1 + 1/f(j)) =1/phi^2*Sum_(i>=0) (1/phi-1)^i * Sum_(j>0) ( log(1+1/f(j))/phi^j ) The first factor is phi/(2phi-1) = phi/sqrt(5). The second converges quite rapidly; the jth term is roughly 1/(f(j)*phi^j). The sum seems to be 1.0943625... Thus we get the limiting value of k to be 1/(phi*sqrt(5)) * Sum log(1+1/f(j))/phi^j. Etc. Can't seem to get the final numbers to work out. Too tired. It's Friday. I just observe g(n) = phi^n * 0.22929687... dave (=self) ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: help with recurrence formulas Date: 20 Oct 1995 18:48:52 GMT In article , Johan Ovlinger wrote: >I have some recurrence formulas which specify the runtime of >a particularly nasty function. I'd appreciate any help in >deriving a general formula for f, given: >f(0) =0 >f(1) =1 >f(n) =f(n-1)+f(n-1)f(n-2) Given your application I will take the liberty of _estimating_ f(n). On the one hand, f(n) > f(n-1)f(n-2) so g(n)=log(f(n)) satisfies g(n) > g(n-1) + g(n-2). Thus if h(n)=g(n) for n=2 and n=3 and h(n) = h(n-1) + h(n-2) thereafter, we conclude by induction that g(n) > h(n) for all n>3. Since h(2)=0 and h(3)=log(2), we see that h(n) is a multiple of the Fibonnaci sequence: h(n) = log(2) * F_(n-2). Since F_n is the nearest integer to phi^n / sqrt(5) (where phi=(-1+sqrt(5))/2 is the golden ratio), we see that g(n) grows faster than an exponential function A*phi^n. On the other hand, 1+f(n) = 1 + f(n-1)*(1+f(n-2)) < (1+f(n-1))*(1+f(n-2)), so the numbers g'(n) = log( 1 + f(n) ) satisfy g'(n) < g'(n-1) + g'(n-2). As above we find g'(n) < log(2) * F_n, so that g'(n) grows slower than an exponential function B*phi^n. Actually, g'(n) = g(n) + log(1 + 1/f(n)), so that asymptotically g(n) and g'(n) behave the same. Therefore we may also state that g(n) grows more slowly than an exponential function B'*phi^n. I'm pretty sure you can push this further and conclude that g(n)/phi^n is not only bounded above and below but in fact converges to some limit L; I'm not inclined to puruse the details, but this leaves you with the estimate g(n) ~ L * phi^n, and thus f(n) ~ exp(L*phi^n). (You may interpret the " ~ " symbol as you wish.) dave ============================================================================== Date: Tue, 24 Oct 95 11:57:39 CDT From: rusin (Dave Rusin) To: rusin Subject: further thoughts (Not posted) Estimating integers determined by quadratic recurrence relation (sketch). We consider the asymptotic evaluation of sequences of positive integers satisfying recurrence relations of the form f(n)=f(n-1)*f(n-2) + v(n) where v(n) is a positive integer whose aymptotic behaviour we shall specify later. The original example is v(n)=f(n-1), with f(0)=0, f(1)=1. Let g(n)=log(f(n)); then the g(n) satisfy g(n)=g(n-1)+g(n-2) + u(n), where u(n)=log(1+v(n)/(f(n-1)*f(n-2))). In particular, v(n) >=1 => g(n) >= g(n-1)+g(n-2). Thus if g'(n)=g(n) for n=1, 2 and thereafter g'(n) = g'(n-1)+g'(n-2), then the g' satisfy a Fibonnaci relation, and so have the form g'(n)=A*phi^n + B*phibar^n for some A and B, where phi and phibar are the roots of x^2-x-1=0. It follows that g(n) >= g'(n) >= A*phi^n - B for all n, so that g grows exponentially and then f even faster. Let k(n)=g(n)/phi^n. Then the k(n) satisfy k(n) = k(n-1)/phi + k(n-2)/phi^2 + u(n)/phi^n. Setting l(n)=k(n)-k(n-1), we compute l(n)=(phi-2)*l(n-1) + u(n)/phi^n. Dividing these equations by (phi-2)^n and adding from, say, n=3 to n=N gives, after adding and cancellation, l(N)/(phi-2)^N = l(2)/(phi-2)^2 + Sum u(n)*(-phi)^n since 1/(phi*(phi-2))=-phi. If we assume that each u(n) < u(n-1)/phi, then the sum is a decreasing alternating sum, and hence convergent. In the original problem, the sum is about -0.32012 62948 64561. Let the sum be S1. Then we have k(m) = k(2)+Sum_{3 <= N <= m} l(N) =k(2)+Sum_N (phi-2)^N-2 l(2) + Sum_{N,n} (phi-2)^N(-phi)^n u(n) Summing first over N=n...m we get k(m) = k(2) + l(2)*((phi-2)^(m-1)-(phi-2))/(phi-3) + Sum_n u(n)*(-phi)^n*((phi-2)^(m+1)-(phi-2)^n)/(phi-3) which we write as [k(2)-l(2)*(phi-2)/(phi-3)] + [l(2)/(phi-3)](phi-2)^(m-1) + -1/(phi-3) * Sum_{n=3...m} (phi-1)^n * u(n) + (phi-2)^(m+1)/(phi-3) * Sum (-phi)^n * u(n) The first sum here is convergent by comparison to the geomertric series Sum (phi-1)^n/phi^n; call the sum S3. In the original sequence, this value is about 0.31688 04859 17134. Since |phi-2|<1, these terms drop as m->oo, and so the limit of the k(m) exists. Indeed the limit is S4=k(2)-l(2)*(phi-2)/(phi-3) - S3/(phi-3); in the original sequence this is about 0.22929 68736 83955. Setting S5=l(2)/((phi-2)^2(phi-3)) + S1/(phi-3) we may write k(m) = S4 + S5*(phi-2)^m + 1/(phi-3)* Sum_{n=m+1...oo} u(n)*(phi-1)^n*[1-1/(phi-2)^(n-m-1)] Note that the summand corresponding to n=m+1 drops out, so the dominant terms are u(m+2)*(phi-1)^(m+2)*((phi+2)/(phi-3)) + + u(m+2)*(phi-1)^(m+3)*((-3phi-1)/(phi-3)) + ... Since phi*(phi-1)=1 and phi*(phi-2)=1-phi=phibar, we now have g(m) = S4 phi^m + S5 phibar^m + u(m+2)*(phi-1)^2*((phi+2)/(phi+3)) + ... (The remaining terms include a factor dropping by phi-1 each time.) We may exponentiate to get f(m) = exp( S4 phi^m + S5 phibar^m ) * (1 + v(m+2)/f(m+1)f(m) )^((7-4phi)/5) * ... Now we need only assume that v(n) = o(f(n-1)). For then v(m+2)/f(m+1)f(m) will be o(1/f(m)), and hence quite small; the last factor above is then roughly 1+(7-4phi)/5*v(m+2)/f(m+1)f(m). Since the first factor is asymptotically f(m), we get simply f(m) = exp( ... ) + (7-4phi)/5 * v(m+2)/f(m+1) + smaller terms. In the original problem, v(n)=f(n-1), so u(n)=log(1+1/f(n-2)). This is now bounded by exp(-S4 phi^m+epsilon), and so is rapidly convergent.The terms not expanded above are bounded in sum by, say, (phi-1)^(m+1)*(phi+2)/f(m+1), and soupon exponentiating, this fator increases the estimate by at most a multiple off(m)/f(m+1), which is less than 1!. Thus we concludef(n) is the integer nearest to exp( S4 phi^n + S5 phibar^n) Likewise in general it can "only" be that these smaller terms total less than 1, so since f(m) is integral, we conclude: f(n) is the integer nearest to exp( S4 phi^n + S5 phibar^n ) + S6* v(n+2)/f(n+1). It would be of interest to determine a closed form expression for S4 and S5; perhaps they or the exponentials are algebraic? =================================================================== We remark that this analysis applies to other recurrences too. For example, if f(n)=f(n-1)^2+c, then we see log g(n) = S*2^n + small, so that f(n) = nearest integer to exp(S*2^n)+fraction... ============================================================================== Date: Tue, 24 Oct 95 11:57:59 CDT From: rusin (Dave Rusin) To: rusin Subject: program used (not posted) 10 point 50 20 Phi=(1+sqrt(5))/2 30 S1=-0.320126294865460977506006485928450934069064999033349215583702256429109749656717123740999038194005137287532997335515293179273950523076787418625952788770155922475497155484059027024975614408174899378165547005210626630874511907139714433799690722 40 S2=0.229296873683954724645037289668857177904917996751304573144104960805394413456042455502320520906551469185009344219192215441734674666936286391132898363151880777046105825879309050223473600523309990140406708793636344580844451517100126723618522689 50 Uuu=S1*(Phi-2)/(Phi-3) 60 S1=(-Phi)^3*log(2)+(-Phi)^4*log(2) 70 Gamma=(Phi-1)^3*log(2)+(Phi-1)^4*log(2) 90 N=2 100 Ko=0 110 G=0 120 Go=0 130 N=N+1 140 if Go>1000 then =+Go:goto 200 150 =G+Go+log(1+exp(-Go)) 160 if >1000-N/2 then 200 170 S1=S1+(-Phi)^(N+2)*log(1+exp(-)) 180 Gamma=Gamma+(Phi-1)^(N+2)*log(1+exp(-)) 200 Go=G 210 G= 220 Ko=K 230 K=G/Phi^N 240 L=K-Ko 250 if abs(S1)>4 then print N:Halt 260 print (G-S2*Phi^N-Uuu/(-Phi)^N),N 280 if N<130 then 130 290 print "S1=";S1 300 print "S2=";Gamma/(3-phi) 320 end