Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I have an expression

2^n / Sum[ 2^i Binomial[ n - i - 1, 2n/3 - 1], { i, 0, n/3}]
2^n / ( Binomial[ -1 + n, -1 + (2 n)/3] Hypergeometric2F1[ 1, -(n/3), 1 - n, 2])

I would like to find if there is an exact asymptotic expression for this for large $n$.
I suspect it is something like $\;\sqrt{n}\;\;1.06^{\;n}\quad$ from numerical experiments.
Is it possible to work out it out exactly using Mathematica?

share|improve this question
    
Try plotting DiscretePlot[1/n Log[1/Sqrt[n]2^n/Sum[2^i*Binomial[n-i-1,2*n/3-1],{i,0,n/3}],{n,1,100,3}] and see if it converges to Log[1.06]. –  Eckhard Sep 24 '13 at 13:51

2 Answers 2

up vote 5 down vote accepted

There is a way without hypergeometric functions.

Binomial asymptotics is

bin = Normal@Series[Binomial[n - i - 1, 2*n/3 - 1], {n, ∞, 0}, {i, ∞, 0}] // FullSimplify

$\displaystyle\frac{2^{-2 n/3} \sqrt{\frac{1}{n}} 3^{n-i}}{\sqrt{\pi }}$

Approximately sum is integral

sum = Integrate[bin, {i, 0, n/3}]

$\displaystyle\frac{\left(\frac{3}{2}\right)^{2 n/3} \left(3^{n/3}-1\right) \sqrt{\frac{1}{n}}}{\sqrt{\pi } \ln 3}$

Its asymptotics is $\;\frac{3^n\;2^{-\frac{2n}{3}}}{\sqrt{n}}$.

As a result we have

$$ \frac{2^n \sqrt{n}}{3^n2^{-\frac{2n}{3}}} = \sqrt{n}\left(\frac{2^{5/3}}{3}\right)^n \approx \sqrt{n}\;1.06^{\;n} $$


Analysis of hypergeometric functions

From Hector answer:

Series[2^n/Sum[2^i*Binomial[n - i - 1, 2*n/3 - 1], {i, 0, 
      n/3}], {n, ∞, 1}] // FullSimplify // Normal

enter image description here

At the first glance Hypergeometric2F1[1, -(n/3), 1 - n, 2] is a nightmare. However, let us analyze its asyptotics. By definition Hypergeometric2F1[a, b, c, z] is

Sum[(Gamma[a + k] Gamma[b + k] Gamma[c])/(Gamma[a] Gamma[b] Gamma[c + k]) z^k/k!, {k, 0, ∞}]
Hypergeometric2F1[a, b, c, z]

In our case

a = 1;
b = -n/3;
c = 1 - n;
z = 2;

Let us consider one term of the sum above. We are interested in the case when $\ n\!\!\mod 3 = 0$. Gamma is undefined for negative integers but we can take a limit

g = FullSimplify[
  Limit[(Gamma[a + k] Gamma[b + k] Gamma[c])/(
    Gamma[a] Gamma[b] Gamma[c + k]) z^k/k!, n -> 3 m, 
   Assumptions -> {m \[Element] Integers, k \[Element] Integers, 
     m > k > 0}], Assumptions -> {k \[Element] Integers}]

enter image description here

Now we can consider the series about $m = \infty$

s = Normal@Series[g, {m, ∞, 0}]
(3/2)^-k

It doesn't depend on m!

Therefore, Hypergeometric2F1[1, -(n/3), 1 - n, 2] is equal to 3 for big $n$!

Sum[s, {k, 0, ∞}]

3

Numerical verification:

Needs["NumericalCalculus`"]
NLimit[Hypergeometric2F1[1, -Round[n, 3]/3, 1 - Round[n, 3], 2], n -> ∞]

2.99998

As a result the asymptotics is

$$ \frac{\sqrt{\pi n}}{3} \left(\frac{2^{5/3}}{3}\right)^n $$

share|improve this answer
    
I made a comment (and then erased it) about Hypergeometric2F1 having a singularity. I deleted my comment because that is just part of the story. –  Hector Sep 24 '13 at 18:21
    
Thank you! Why are the two asymptotic results slightly different out of interest? –  felix Sep 24 '13 at 19:00
    
@felix The first approach is simple but rough and didn't give the correct coefficient. –  ybeltukov Sep 24 '13 at 19:18

I find it very interesting that Mathematica does not simplify the numerator:

Series[2^n/Sum[2^i*Binomial[n - i - 1, 2*n/3 - 1], {i, 0, n/3}], {n, ∞, 1}]
     // FullSimplify // Normal

enter image description here

Using the obvious simplification, we get:

behavior = (2^(5 n/3) 3^-n Sqrt[n] Sqrt[π]) / Hypergeometric2F1[1, -(n/3), 1 - n, 2]
exact = Table[ Log@N@(2^n/Sum[2^i*Binomial[n - i - 1, 2*n/3 - 1], {i, 0, n/3}]), {n, 300, 1000, 3}];
approx = Table[Log@N@behavior, {n, 300, 1000, 3}];
estim = Table[Log@N@(Sqrt[n] 1.06^n), {n, 300, 1000, 3}];
ListPlot[{exact, approx, estim}, PlotLegends -> {"exact", "approx", "estim"}]

enter image description here


Original answer

I would use Series[blah,{n,∞,1}]:

behavior = Series[Sum[2^i*Binomial[n-i-1, 2*n/3-1], {i, 0, n/3}], {n, ∞, 1}]
     //FullSimplify//Normal

enter image description here

Your estimation however seems to be off:

exact = Table[Log@N@Sum[2^i*Binomial[n - i - 1, 2*n/3 - 1], {i, 0, n/3}], {n,300, 1000, 3}];
approx = Table[Log@N@behavior, {n, 300, 1000, 3}];
estim = Table[Log@N@(Sqrt[n] 1.06^n), {n, 300, 1000, 3}];
ListPlot[{exact, approx, estim}, PlotLegends -> {"exact", "approx", "estim"}]

enter image description here

share|improve this answer
    
Thank you. There was a typo I just fixed in the question. –  felix Sep 24 '13 at 12:31
    
Hypergeometric2F1[1, -n/3, 1 - n, 2] is equal to 3 for big n. See the second part of my answer. –  ybeltukov Sep 24 '13 at 18:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.