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?
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
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 $$
Hypergeometric2F1 having a singularity. I deleted my comment because that is just part of the story.
$\endgroup$
Pochhammer instead of Gamma in the definition of g simplifies the derivation.
$\endgroup$
Commented
Jun 15, 2015 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"}]
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
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"}]
Hypergeometric2F1[1, -n/3, 1 - n, 2] is equal to 3 for big n. See the second part of my answer.
$\endgroup$
Commented
Sep 24, 2013 at 18:09
// Normal // FullSimplify instead of // FullSimplify // Normal to achieve the desired simplification.
$\endgroup$
Commented
Jun 15, 2015 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 π] *)
