# Find asymptotics of $\sum\limits_{i=0}^{n/3} 2^i \binom{n-i-1}{\frac{2n}{3}-1}$

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
Using Pochhammer instead of Gamma in the definition of g simplifies the derivation. – bbgodfrey Jun 15 at 14:44

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
Use // Normal // FullSimplify instead of // FullSimplify // Normal to achieve the desired simplification. – bbgodfrey Jun 15 at 14:46

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 π] *)
`
-
That's very nice! – felipa Jul 2 at 7:16