# Growth rate of a sum

Consider a positive sequence $x_n >0$ that satisfy the condition that there exists a constant $0<\alpha<1$ such that $x_{n+1} \geq \alpha (x_1+\ldots{} +x_{n})$.

What can be said about the set of all such sequences? Can one solve for them in terms of a formula for $x_n$?

-
If you define $y_n$ by $y_1=x_1$ and putting equality in your recursion, you'll get $y_{n+1} \geq (1+\alpha) y_n$ for all $n\geq 2$, and $x_n\geq y_n$ for all $n\geq 1$ by induction. In particular $x_n \geq y_n = \alpha x_1 (1+\alpha)^{n-2}$ for all $n\geq 2$ (assuming I haven't made an indexing error -- at any rate you get exponential growth in $n$). So that's basically a discrete Gronwall-type bound -- I'm not sure how much more one can say beyond that in any generality. –  Vaughn Climenhaga Sep 30 '12 at 22:57
I don't know what a "solution" could mean in this setting, since there are infinitely many such sequences. Given $x_1$, the smallest such sequence is obtained by recursively setting each $x_{n+1}$ equal to its lower bound $\alpha\sum_{i=1}^n x_i$, which makes $x_n = \alpha(1+\alpha)^{n-2} x_1$ for $n>1$; in particular $x_n \rightarrow \infty$ as $n \rightarrow \infty$. In general if $d_n = x_n - \alpha\sum_{i=1}^{n-1} x_i \geq 0$ then $$x_n = \alpha(1+\alpha)^{n-2} x_1 + d_n + \sum_{i=2}^{n-1} \alpha(1+\alpha)^{n-1-i} d_i,$$ which may be as much of a "solution" as one can hope for. –  Noam D. Elkies Sep 30 '12 at 22:58
Thanks for the responses. I am particularly interested in knowing whether or not all sequences that grow at least exponentially fast in $n$ or faster must necessarily satisfy the inequality stated in the question. –  Euplio M. Oct 1 '12 at 0:37
You might get some insight by considering the whole set or subsets as convex sets. The analysis is hardly mysterious, so geometry could help. –  Charles Matthews Oct 1 '12 at 10:10
@Euplio: if the your last question means, if a sequence satisfying $x_n\ge C\theta^n$ necessarily satisfies the initial inequality for some $0 < \alpha < 1$ then the answer is no. Take e.g. $x_n:=2^n$ for odd $n$ and $x_n:=n2^n$ for even $n$. –  Pietro Majer Oct 1 '12 at 15:08

Not very much can be said about all such sequences. In essence all that can be said is that they grow at least exponentially. As previous comments have noted, for all $n$, we have $x_n \geq y_n$, where $y_1 := x_1$ and for all $n>1$, $$y_n := \alpha \sum_{i=1} ^{n-1} y_{i} = \alpha \sum_{i=1} ^{n-2} y_{i} + \alpha y_{n-1} = (1+\alpha) y_{n-1}.$$ Therefore, $y_n = \alpha (1+\alpha)^{n-2} x_1$, which is valid for all $n\geq 2$. Thus if $x_n$ satisfies the desired property in the original post, then for all $n\geq 2$, we have $x_n \geq \alpha (1+\alpha)^{n-2} x_1$, and this lower bound is of course obtained by the sequence $y_n$.

To strengthen this bound somewhat, for all $n > m \geq 1$, we must have $$x_{n} \geq \alpha (1+\alpha)^{n-m-1}\left(\sum_{i=1} ^{m} x_{i} \right) \geq x_m \alpha (1+\alpha)^{n-m-1}.$$ Therefore, if $x_m \neq 0$ and $t\geq 1$, we have $$\frac{x_{m+t}}{x_m} \geq \alpha (1+\alpha)^{t-1},$$ which implies that for all sufficiently large $t$ (which depends only on $\alpha$), $x_{m+t} > x_m$ and that $x_n$ goes to infinity.

However, trying to say something much more precise is difficult. Sequences that have the desired property you described certainly grow fast ($x_n \geq \alpha x_1 (1+\alpha)^{n-2}$), but it is not the case that all sequences that grow at least this fast must have your desired property. Consider for example the sequence $a_n = (2^1, 4^2, 2^3, 4^4, 2^5, 4^6, ...).$ Then $a_n \geq a_1 2^{n-1}$, but there is no alpha for which your desired property holds.

This problem arose because some of the $a_i$ grew more slowly than the others (but honestly, this difference in growth rate wasn't even that bad)! If you know that $\gamma _n$ satisfies $$c_1 R^n \leq \gamma_n \leq c_2 R^n,$$ then you can in fact conclude that $\gamma_n$ satisfies a bound such as you desired.

Hoping to find a closed formula is of course as hopeless as ever even assuming a sequence has your desired property. This is because you can start with any sequence $A(n)$ that is perhaps as complicated and difficult as possible. Then if $B(n)$ is a function that grows sufficiently quickly (e.g., iterating $n^{n}$ a few times), then $A(n) + B(n)$ will have your desired property, but finding a closed formula for it will be at least as hard as finding a closed formula for $A(n)$ [which could be arbitrarily difficult].

In short, knowing more about your particular sequence may help a lot, but in general, your condition says very very little about the sequence (other than the fact that it grows fast).

-