Positive linear recurrent sequence

Question

Suppose there is a linearly recurrent sequence $a_k$ satisfies $a_k\geq 0$ and $\sum_{k=1}^{\infty}a_k=1$.

Can we always find a $x$ and $r<1$ such that $a_k\leq x r^k$?

Answer 1

Even more is true: for all linear recurrences either $|a_k| \le xr^k$ for some $x>0, r < 1$ or $\limsup |a_k| > 0$.

Indeed, for any linear recurrence we have $a_k = \sum_{m = 1}^N b_m k^{c_m} d_m^k$ for some $b_m\in \mathbb{C}\backslash \{ 0\}$, $c_m\in \mathbb{N}_0$, $d_m\in \mathbb{C}$ and the pairs $(c_m, d_m)$ are pairwise distinct. If all $|d_m|$ are less than $1$ than we get the desired estimate with $r = \sup |d_m| + \varepsilon$ for an arbitrary $\varepsilon > 0$. So, assume that some $|d_m| \ge 1$. Let us consider only the terms with biggest $|d_m| = d$ and among those with biggest $c_m = c$. If we will show that their sum is infinitely often $\gg k^c d^k$ then we are done, since all the other terms are $o(k^c d^k)$.

Since they all have a term $k^c$, we just have to prove that $s_k = \sum_{n = 1}^M f_n g_n^k$ for $|g_n| = d$ distinct, $f_n\in \mathbb{C}\backslash \{0\}$ is infinitely often $\gg d^k$. Consider $s_k, s_{k+1}, \ldots , s_{k+M-1}$. We have $$(s_k, s_{k+1}, \ldots , s_{k+M-1}) = (f_1g_1^k, f_2g_2^k, \ldots , f_Mg_M^k)V^{T},$$ where $V$ is the Vandermonde matrix corresponding to the numbers $g_n$ (I used transpose and wrote the vectors as horizontal lines only for the typesetting purposes).

Now, since $g_n$ are distinct, the Vandermonde matrix is invertible. Thus, the norm of the vector on the right-hand side is bounded by the norm of the vector on the left-hand side:

$$\sum_{n = k}^{k + M-1} |s_n|^2 \ge c d^{2k} \sum_{n = 1}^M |f_n|^2 \ge c_1 d^{2k}.$$

Thus, at least one of the terms on the left-hand side is at least $\frac{c_1}{M}d^{2k}$, that is at least one of $|s_n|$ is at least $\frac{\sqrt{c_1}}{\sqrt{M}}d^{k}$, which is exactly what we wanted.

I deviced this trick a few years ago when my friend gave me (a finite group version of) this MO question as an excercise.