Almost binomial sum limit

Question

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.

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

Answer 1

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.