3
$\begingroup$

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.

enter image description here 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.).
$\endgroup$
13
  • 1
    $\begingroup$ 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$. $\endgroup$ Jun 4 '19 at 20:00
  • $\begingroup$ Well the coefficient of $e_1$ is $\gamma^N$, which is pretty tiny. No ? $\endgroup$
    – dohmatob
    Jun 4 '19 at 20:01
  • $\begingroup$ $\gamma^{N-1}$ you mean. Maybe this is tiny, but $e_N$ could be much tinier. $\endgroup$ Jun 4 '19 at 20:03
  • $\begingroup$ (Yes, I meant $\gamma^{N-1}$, but this doesn't change much in the arguments :) ) $\endgroup$
    – dohmatob
    Jun 4 '19 at 20:07
  • $\begingroup$ I've added to support the empirical claims. $\endgroup$
    – dohmatob
    Jun 4 '19 at 20:10
6
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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! $\endgroup$
    – dohmatob
    Jun 5 '19 at 6:39
  • $\begingroup$ BTW, someone has voted for the question to be closed. Is the question that "bad" ? $\endgroup$
    – dohmatob
    Jun 5 '19 at 6:40
  • $\begingroup$ 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. $\endgroup$ Jun 5 '19 at 17:24
  • $\begingroup$ 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? $\endgroup$
    – dohmatob
    Jun 7 '19 at 7:43
3
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ 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$. $\endgroup$ Jun 5 '19 at 17:53
  • $\begingroup$ Yes, I just added that remark before seeing your comment entered at the same time :) $\endgroup$
    – dohmatob
    Jun 5 '19 at 17:54
  • 1
    $\begingroup$ Also, finitely many exceptions don't matter, hence just $\liminf e_{n+1}/e_n>\gamma$ is enough. $\endgroup$ Jun 5 '19 at 18:21
  • 1
    $\begingroup$ Good point. Thanks! $\endgroup$
    – dohmatob
    Jun 5 '19 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.