# Almost binomial sum limit

I got the following sum with which I want to prove one limit fact:

$$f_n(a) = \sum\limits_{t=0}^{n-1} \binom{n-1}{t} (a^t)^{n-t}$$

I want to prove that $f_n(a) \to 1$ while $n \to \infty$ for $a\in [0,1)$ if true. (I plotted and it looks like it were true). As you see this is kind of binomial sum, but instead of multiplying by $a^{n-t}$ we are powering. I wrote the sum without sigma sign and tried to prove using members, however I stuck because the size of the sum still growing.

Any help would be appreciated.

Thank you.

 If it is possible the speed of decreasing is also interesting, in terms of small-o.

• The $t=0$ term dominates all the others. This is too elementary for this board. You should ask at math.stackoverflow. – Brendan McKay Dec 28 '16 at 5:09
• What about the number of the terms, it's getting bigger and biggger – Eugene Dec 28 '16 at 5:26

Splitting your sum as $\sum_{t=0}^{n-1}=1+\sum_{t=1}^{n-1}$, it suffices to show that $\sum_{t=1}^{n-1}\binom{n-1}ta^{t(n-t)}\rightarrow0$ as $n\rightarrow\infty$; provided $0<a<1$.
To illustrate our proposed method, assume $0<a<\frac12$. Since $t(n-t)\leq n-1$, we estimate $$0\leq\sum_{t=1}^{n-1}\binom{n-1}ta^{t(n-t)}\leq a^{n-1}\sum_{t=1}^{n-1}\binom{n-1}t\leq (2a)^{n-1}\rightarrow0, \qquad \text{as n\rightarrow\infty}.$$ The claim holds for $0<a<\frac12$. The general idea is quite similar.
Fix $k\in\mathbb{N}$ and assume $0<a<\sqrt[k]{\frac12}$. For $n\gg k$, "shave off" terms from above and below: $$\sum_{t=1}^{n-1}\binom{n-1}ta^{t(n-t)} =\left(\sum_{t=1}^{k-1}+\sum_{t=k}^{n-k}+\sum_{t=n-k+1}^{n-1}\right) \binom{n-1}ta^{t(n-t)}$$ $$\qquad \qquad =\sum_{t=1}^{k-1}\left[\binom{n-1}t+\binom{n-1}{t-1}\right]a^{t(n-t)}+ \sum_{t=k}^{n-k}\binom{n-1}ta^{t(n-t)}$$ $$=\sum_{t=1}^{k-1}\binom{n}ta^{t(n-t)}+ \sum_{t=k}^{n-k}\binom{n-1}ta^{t(n-t)}$$ $$\leq(k-1)\binom{n}{k-1}a^{n-1}+\sum_{t=k}^{n-k}\binom{n-1}ta^{t(n-t)}$$ $$\leq(k-1)\binom{n}{k-1}a^{n-1}+a^{k(n-k)}\sum_{t=k}^{n-k}\binom{n-1}t$$ $$\leq(k-1)\binom{n}{k-1}a^{n-1}+a^{k(n-k)}2^{n-1}.$$ It remains to observe that (i) $(k-1)\binom{n}{k-1}$ is a polynomial in $n$ while $a^{n-1}$ is a decaying exponentially, so $$(k-1)\binom{n}{k-1}a^{n-1}\rightarrow 0 \qquad \text{as n\rightarrow\infty}.$$ Also that (ii) since $a^k2<1$, we can say $$a^{k(n-k)}2^{n-1}=a^{k(1-k)}\cdot(2a^k)^{n-1}\rightarrow0 \qquad \text{as n\rightarrow\infty}.$$ We've just shown that $\sum_{t=1}^{n-1}\rightarrow0$ for each $0<a<\sqrt[k]{\frac12}$. To complete the proof, increase $k\rightarrow\infty$ freely so that the interval $0<a<1$ is exhausted.
• I independently obtained the proof for $a < 0.5$ using upper bound for binomials. Your trick completed the task I was struggling with. Thanks! – Eugene Dec 28 '16 at 5:44
• Also, is it correct that this sum is $1+O(a^{n-1})$? – Eugene Dec 28 '16 at 5:49
• Also, I'd like to point out that $t(n-t) \geq n-1$. And that's why you using it in the $\leq$ estimate, b/c $a < 1$. – Eugene Dec 28 '16 at 6:20