# Good upper bound for a certain sum

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.).
• It's impossible in general to have an upper bound that just depends on $e_N$, because there are no upper bounds on $e_1$. Jun 4 '19 at 20:00
• Well the coefficient of $e_1$ is $\gamma^N$, which is pretty tiny. No ? Jun 4 '19 at 20:01
• $\gamma^{N-1}$ you mean. Maybe this is tiny, but $e_N$ could be much tinier. Jun 4 '19 at 20:03
• (Yes, I meant $\gamma^{N-1}$, but this doesn't change much in the arguments :) ) Jun 4 '19 at 20:07
• I've added to support the empirical claims. Jun 4 '19 at 20:10

$$\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 $$$$\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},$$$$ 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$$.

• Great, thanks. After the discussions in the comments, I knew there had to be a kind of "correction" which would safe 80% of the conjecture, but couldn't quite work it out. The log-convexity sandwhich nails it indeed. Thanks! Jun 5 '19 at 6:39
• BTW, someone has voted for the question to be closed. Is the question that "bad" ? Jun 5 '19 at 6:40
• For the members who voted to close, yes it is bad. You seem to have a good answer from an interested and helpful member, so I would not worry about it. Gerhard "Closing Is A Subjective Thing" Paseman, 2019.06.05. Jun 5 '19 at 17:24
• Well, there should be some objectivism regarding voting to close a question, as this is a very strong form of (dis)engagement. Otherwise MO wouldn't be any different from random YouTube comments. No? Jun 7 '19 at 7:43

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}$$.

• You don’t need the ratios to be nonincreasing or even convergent for this. You only need that they are bounded away from $\gamma$, that is, there exists $\rho>\gamma$ such that $e_{n+1}/e_n\ge\rho$ for all $n$. Jun 5 '19 at 17:53
• Yes, I just added that remark before seeing your comment entered at the same time :) Jun 5 '19 at 17:54
• Also, finitely many exceptions don't matter, hence just $\liminf e_{n+1}/e_n>\gamma$ is enough. Jun 5 '19 at 18:21
• Good point. Thanks! Jun 5 '19 at 19:55