3

Let $\alpha <1, k\le n$. Consider the sequence $$a_0 = 1, a_{i+1} = \alpha^{n-i} a_i.$$

I'm trying to upper bound the sum $$S(\alpha, n, k) := \sum_{i = 0}^k a_i.$$ Note that the sequence $\{a_i\}$ is dominated by a geometric sequence with the ratio $\alpha^{n-k}$, but the upper bound that results from this is too weak for the problem I want to apply this to. I also tried splitting the sum into blocks and separately bounding each block by a geometric series, but this quickly turned intimidatingly messy. Is there a trick I can use to exploit the stronger initial decay? Alternately, is there a neat way to deal with the multiple geometric series approximation?

In case helpful, it may be assumed that $k\gg 1$, and that $\alpha \ll 1$.

stochasticboy321
  • 9,003
  • 1
    Can you make it more specific? Are $n$ and $k$ large? Is $k$ assymptotically close to $1$ or to $n$? What upper bound would be sufficient? I understand you're looking for some trick, but this explanation might help. – Michał Miśkiewicz Aug 11 '17 at 21:16
  • 1
    @MichałMiśkiewicz As such, there's no assumptions on $k$ or $n$. That said, I would be fairly happy with a result for $k\gg 1.$ Adding to the Q. now. – stochasticboy321 Aug 11 '17 at 21:42

1 Answers1

2

First, we can get an explicit formula for $a_i$ with $i \in N$ using the recursive definition. $$a_i=\prod_{m=0}^{i-1}{\alpha^{n-m}}=\alpha^{\sum_{m=0}^{i-1}{(n-m)}}=\alpha^{\sum_{m=0}^{i-1}{(n)}-\sum_{m=0}^{i-1}{(m)}}$$ $$a_i=\alpha^{ni-\frac{i(i-1)}{2}}=\alpha^{ni+\frac{i}{2}-\frac{i^2}{2}}=\alpha^{\frac{ni+i}{2}+\frac{ni-i^2}{2}}$$ $$\sum_{i=0}^{k}{a_i}=\sum_{i=0}^{k}{\alpha^{\frac{ni+i}{2}+\frac{ni-i^2}{2}}}$$ In the summation $n \geq k \geq i$, which implies that $ni \geq i^2$ and $\frac{ni-i^2}{2} \geq 0$. $$\frac{ni+i}{2} \leq \frac{ni+i}{2}+\frac{ni-i^2}{2}$$ I suggest to add a lower bound on $\alpha$ such that $0 < \alpha < 1$ $$\alpha^{\frac{ni+i}{2}} \geq \alpha^{\frac{ni+i}{2}+\frac{ni-i^2}{2}}$$ $$\sum_{i=0}^{k}{\alpha^{\frac{ni+i}{2}}} \geq \sum_{i=0}^{k}{a_i}$$ $$\sum_{i=0}^{k}{\alpha^{\frac{ni+i}{2}}}=\sum_{i=0}^{k}{\left(\alpha^{\frac{n+1}{2}}\right)^i}=\sum_{i=0}^{k}{\left(\sqrt{\alpha}^{(n+1)}\right)^i}$$ This is in the form of a partial geometric sum: $$\frac{1-\sqrt{\alpha}^{(n+1)(k+1)}}{1-\sqrt{\alpha}^{(n+1)}}$$ Conclusion: $$S(\alpha, n, k) \leq \frac{1-\sqrt{\alpha}^{(n+1)(k+1)}}{1-\sqrt{\alpha}^{(n+1)}}$$ $$0<\alpha<1 \quad\quad 1 \leq k \leq n$$ This approximation tends to work best for large $n$, small $\alpha$, and $n \gg k$.

cvogt8
  • 430
  • Nice answer! Notice that the exponent is $\beta_i=\frac{ni+i}{2}+\frac{ni-i^2}{2}=(\frac{2n+1-i}{2})i$. If you split the sum into parts ending at $i_j$, $j=1,\dots,s$, with $i_s=k$, then for each sum you have $i_{j-1}+1\le i\le i_j$, where $i_{0}=-1$, which gives $\beta_i\ge\gamma_ji$ with $\gamma_j=\frac{2n+1-i_j}{2}$ (and a lower bound follows analogously). This bound gives $s$ partial geometric series which can be computed in closed form each. This way you can further improve to arbitrary precision at the expense of elegance. – Matija Feb 07 '23 at 07:29