# Find asymptotics of Sum[2^i*Binomial[n-i-1,2*n/3-1],{i,0,n/3}]

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?

-
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

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

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


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}]


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

-
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


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"}]


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


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"}]


-
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