1
$\begingroup$

This question is a follow up of the question asked in: Sum of a sequence which is neither arithmetic nor geometric

I have the following sum which doesn't seem to have a closed-form expression: $$S_n = \sum_{i=1}^n 0.9^{\frac{1}{2}(n-i+1)(i+n)}$$

However, a pattern can be observed in the sequence. Let $r = 0.9$, then the few first terms are:

\begin{align} S_0&=0\\ S_1&=r\\ S_2&=r^3+r^2\\ S_3&=r^6+r^5+r^3\\ S_4&=r^{10}+r^9+r^7+r^4\\ S_5&=r^{15}+r^{14}+r^{12}+r^9+r^5\\ \end{align} Notice that it can be written recursively as: $S_n=r^n(S_{n-1}+1)$

I am looking for a way to prove that $\forall n'>n>5$, we have $S_{n'} \leq S_n$. Experimentally (see the figure below), $S_n$ seem to decrease exponentially with $n$, but I don't see how to proceed to prove that.

See Figure: $S_n$ with respect to $n$

$\endgroup$
2
  • $\begingroup$ what is the value of your $r$? $\endgroup$
    – pisco
    Commented Sep 19, 2017 at 15:32
  • $\begingroup$ @pisco125 $r = 0.9$, I have edited the post now. $\endgroup$ Commented Sep 19, 2017 at 16:44

1 Answer 1

0
$\begingroup$

The recurrence $S_n = r^n (S_{n-1} + 1)$ doesn't guarantee that $S_n \le S_{n-1}$: if, for example, $S_{n-1} = 0$, then $S_n = r^n$ and the sum has increased. To deal with this problem, we need a lower bound on $S_n$.

Which lower bound do we need? We can rearrange the recurrence to get $$r^n(S_{n-1} + 1) \le S_{n-1} \iff r^n \le (1 - r^n) S_{n-1} \iff S_{n-1} \ge \frac{r^n}{1-r^n}.$$

It's not obvious that this is initially true, but it's easy to show that $S_{n-1} \ge r^{n-1}$: we can see this from the initial values, and we can prove it by induction from $$S_{n-1} \ge r^{n-1} \implies S_n \ge r^n(r^{n-1} + 1) \implies S_n \ge r^n + r^{2n-1} \ge r^n.$$ This will imply our desired lower bound for sufficiently large $n$: we get $r^{n-1} \ge \frac{r^n}{1-r^n}$ when $1 - r^n \ge r$.

This eventually happens for any $r \in [0,1)$, since $1 - r^n \to 1$ as $n \to \infty$. For $r = 0.9$ this is true once we hit $n=22$: we have $1 - 0.9^{22} \approx 0.9015$. So we've shown that $S_n \le S_{n-1}$ holds for $n$ at least $22$.

This isn't quite what we want, and the reason is that our initial lower bound of $r^{n-1}$ isn't sharp, but it still works for sufficiently large $n$, and you can verify values of $n$ between $5$ and $22$ directly with just some computation.


Alternatively, we can check that the inequality $$S_{n-1} \ge \frac{r^n}{1 - r^n}$$ holds for one specific value of $n$: for example, when $r=0.9$ it holds for $n=5$. Once it does, it holds for all higher values of $n$ by induction: \begin{align*} S_n &= r^n(S_{n-1}+1) \ge r^n \left(\frac{r^n}{1-r^n} + \frac{1-r^n}{1-r^n}\right) \\ &= \frac{r^n}{1 - r^n} = \frac{r^{n+1}}{r - r^{n+1}} \ge \frac{r^{n+1}}{1 - r^{n+1}}. \end{align*} As we saw earlier, this upper bound implies $S_n \le S_{n-1}$, so the sequence is decreasing for $n \ge 5$.

$\endgroup$
2
  • $\begingroup$ We can also inductively show that $S_n$ is the sum of $n$ powers of $r$ between $r^n$ and $r^{n(n+1)/2}$, which means that $S_n \le n \cdot r^n$. This doesn't guarantee that $S_n$ is decreasing, but does guarantee exponential decay. $\endgroup$ Commented Sep 19, 2017 at 17:06
  • $\begingroup$ @ForumsDZForumsDZ The short argument in my comment shows that $S_n$ is bounded above by a decaying exponential, but leaves open the possibility that it keeps oscillating below that upper bound, and never becomes monotone. If you want specifically monotonicity, then you need the more complicated argument in my answer. $\endgroup$ Commented Sep 19, 2017 at 18:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .