13
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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]. $\endgroup$
    – Eckhard
    Sep 24, 2013 at 13:51

3 Answers 3

9
$\begingroup$

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 $$

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Hector
    Sep 24, 2013 at 18:21
  • $\begingroup$ Thank you! Why are the two asymptotic results slightly different out of interest? $\endgroup$
    – Simd
    Sep 24, 2013 at 19:00
  • $\begingroup$ @felix The first approach is simple but rough and didn't give the correct coefficient. $\endgroup$
    – ybeltukov
    Sep 24, 2013 at 19:18
  • $\begingroup$ Using Pochhammer instead of Gamma in the definition of g simplifies the derivation. $\endgroup$
    – bbgodfrey
    Jun 15, 2015 at 14:44
5
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thank you. There was a typo I just fixed in the question. $\endgroup$
    – Simd
    Sep 24, 2013 at 12:31
  • $\begingroup$ Hypergeometric2F1[1, -n/3, 1 - n, 2] is equal to 3 for big n. See the second part of my answer. $\endgroup$
    – ybeltukov
    Sep 24, 2013 at 18:09
  • $\begingroup$ Use // Normal // FullSimplify instead of // FullSimplify // Normal to achieve the desired simplification. $\endgroup$
    – bbgodfrey
    Jun 15, 2015 at 14:46
2
$\begingroup$

In the process of addressing question 85900, I noticed that the question above can be solved compactly as follows. The solution draws upon insights from the answers by Hector and ybeltukov.

Series[2^n/Sum[2^i*Binomial[n - i - 1, 2*n/3 - 1], {i, 0, n/3}], {n, ∞, 0}] 
    // Normal // FullSimplify[#, n > 0] &
(* 2^(5 n/3) 3^-n Sqrt[n π]/Hypergeometric2F1[1, -(n/3), 1 - n, 2] *)

Series[Pochhammer[1, k] Pochhammer[-n/3, k]/Pochhammer[1 - n, k] /. 
    n -> 3 m, {m, ∞, 1}] // Normal // FullSimplify[#, k ∈ Integers] &
(* 3^-k Pochhammer[1, k] *)

%% /. Hypergeometric2F1[1, -(n/3), 1 - n, 2] -> Sum[% 2^k/k!, {k, 0, ∞}]
(* 2^(5 n/3) 3^(-1 - n) Sqrt[n π] *)
$\endgroup$
1
  • $\begingroup$ That's very nice! $\endgroup$
    – Simd
    Jul 2, 2015 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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