Good upper bound for a certain sum

Question

Given $\gamma \in [0, 1)$, an integer $N \ge 2$, and a decreasing null sequence of positive numbers $e_1,e_2,\ldots,e_t,\ldots$, I'm interested in estimating the sum $S_N := \sum_{t=1}^N\gamma^t e_{N-t}$.

Question

What is a good upper bound for $S_N$ for large $N$ ?

Observations

Empirically, I'm observing (by plotting graphs) that $S_N \sim \dfrac{e_N}{1-\gamma}$, but I'm not able to prove this in general. My experiments have been for $e_t=at^{-b}$ (with $a,b>0$), $e_t = \ln(t)/t$, $e_t=1/\ln(t)$, $e_t=1/\ln(t)^2$, etc.

The case $e_t = at^{-b}$ can be established analytically. Indeed, a tedious computation reveals that $S_N \sim \frac{1}{1-\gamma}N^{-b} \sim \frac{1}{1-\gamma}e_N$.

---

Notes

• In my (abuse of notations), it's fine for $\sim$ to hide global multiplicative constants (e.g $e_1$, etc.).

Answer 1

$\newcommand{\ga}{\gamma} $ Of course, without further assumptions on the $e_t$'s, no good bound can be given. However, looking at your examples, it appears that you are primarily interested in situations where the $e_t$'s satisfy the following conditions: For some real constant $c\ge1$ and some positive log-convex real sequence $(f_t)$ we have the following: (i) $f_t\le e_t\le c f_t$ for all natural $t$ and (ii) $f_{t+1}/f_t\to1$ as $t\to\infty$, so that $\rho_N:=(f_N/f_1)^{1/(N-1)}\to1$ as $N\to\infty$. In fact, in all your examples except for $e_t=(\ln t)/t$, we can use $c=1$ and $f_t=e_t$ for all $t$.

So, for all $N$ large enough for the inequality $\ga<\rho_N$ to hold, we have \begin{equation} \sum_{t=1}^N\ga^t e_{N-t}\le c\sum_{t=1}^N\ga^t f_{N-t}\le c\sum_{t=1}^N \ga^t f_N^{1-t/(N-1)}f_1^{t/(N-1)} =cf_N\sum_{t=1}^N(\ga/\rho_N)^t\le cf_N\sum_{t=0}^\infty(\ga/\rho_N)^t =\frac{cf_N}{1-\ga/\rho_N}\lesssim\frac{ce_N}{1-\ga}, \end{equation} as you observed empirically.

---

One can do similarly assuming (instead of the above conditions involving the $f_t$'s) that the sequence $(e_t)_{t=t_0}^\infty$ is log convex for some natural $t_0$ and $e_{t+1}/e_t\to1$ as $t\to\infty$. In all your examples we can take $t_0=1$ -- except for $e_t=(\ln t)/t$, where we can take $t_0=5$.

Answer 2

Looks like we don't really need the log-convexity assumption in the accepted answer.

Indeed, define $\rho_N := e_{N} / e_{N-1}$ (with $\rho_1 := 1$), and suppose

Assumption. $\liminf_N\rho_N \ge \rho$ (i.e $\exists N_0 > 0 \mid \rho_N \ge \rho\;\forall N \ge N_0$) for some $\rho > \gamma$.

Note that with the above assumption, for sufficiently large $t \le N$, we have $\rho_t \ge \rho$, and so $e_t = e_{N-1}(e_t/e_{t+1})(e_{t+1}/e_{t+2})\ldots(e_{N-2}/e_{N-1}) = e_{N-1}(\rho_t\rho_{t+1}\ldots\rho_{N-1})^{-1} \le e_{N-1}\rho^{-(N-t)}$. Thus, for $N \ge 2$, one computes \begin{eqnarray*} \begin{split} S_N &:= \sum_{t=1}^{N-1}\gamma^t e_{N-t}=\sum_{t=1}^{N-1}\gamma^{N-t}e_t \lesssim e_{N-1}\sum_{t=1}^{N-1}\gamma^{N-t}\rho^{-(N-t)} =e_{N-1}\sum_{t=1}^{N-1}(\gamma/\rho)^t\\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \sim e_{N-1}\sum_{t=1}^{N-1}(\gamma/\rho)^t \le e_{N-1}\sum_{t=1}^\infty(\gamma/\rho)^t = \frac{\gamma}{\rho}\frac{e_{N-1}}{(1-\gamma/\rho)}. \end{split} \end{eqnarray*} Thus $S_N \lesssim \dfrac{\gamma}{\rho}\dfrac{e_{N-1}}{(1-\gamma/\rho)}$. In particular, if $\rho=1$ as in the accepted answer, then $S_N \lesssim \dfrac{\gamma e_{N-1}}{1-\gamma}$.