Suppose we have a sequence $x_1,x_2,\ldots \in [0,1]$ that satisfies $x_{n+1} \le \left(\sum_{i=1}^n x_i \right)^{-c}$ for each $n$ and some $c \in (0,1)$. The relation comes from deciding stepsizes for a recursive algorithm. I suspect it forces the sum to grow slowly but am unsure how to prove it.
I can show for example that we cannot have $x_n \ge \Omega(n^{-a})$ for some $a \le 1-\frac{1}{c+1}$. For if this happens then $\sum_{i=1}^n x_i \ge \Omega(n^{1-a })$ and so $x_{n+1} \le O(n^{(a-1)c})$. Thus we must have $-a \le (a-1)c$ which simplifies to $a \ge 1-\frac{1}{c+1}$.
This leads me to guess $x_n \le O(n^{\frac{1}{c+1}-1})$ and the sum is $O(n^{1/(c+1)})$.
Is there a way to prove this directly? Ideally without resort to clumsy asymptotic notation?
The claim for the sum holds true: if $s_n=\sum_{k=1}^n x_k$ then $n\mapsto s_n^{c+1}/n$ is bounded.
Here's a fact that helps: for any sequence $n\mapsto a_n$ of real numbers, we have $$\limsup_{n\to\infty}(a_n/n)\leqslant\limsup_{n\to\infty}(a_{n+1}-a_n)$$ (this is a corollary of the Stolz–Cesàro theorem, but is also easy to prove directly).
From the premises, $s_n\leqslant s_{n+1}\leqslant s_n+s_n^{-c}$; with $a_n=s_n^{c+1}$, this can be rewritten as $$0\leqslant a_{n+1}-a_n\leqslant\psi(1/a_n),\qquad\psi(t):=\frac{(1+t)^{c+1}-1}{t}.$$ Observe that $\lim_{t\to 0^+}\psi(t)=c+1$ is finite, thus $\psi$ is bounded on $(0,a)$ for any $a>0$.
Hence, $n\mapsto a_{n+1}-a_n$ is bounded, and by the above, $n\mapsto a_n/n$ is bounded as well.
The claim regarding $x_n$ may fail to hold. We can violate it on a subsequence like $x_{2^n}$. Specifically, take any "slowly convergent" $\sum_{k=0}^\infty a_k=1$, say with $a_k=1/[(k+1)(k+2)]$, and let $x_n=a_k$ if $n=2^k$ and $x_n=0$ otherwise (for $x_n\neq 0$, take $x_n=a_k$ if $n=2^k$ and $k>0$, and $x_n=2^{-n}a_0$ otherwise).