1

To complete a longer a proof I could need a result of the following type:

Assume that $m \in \mathbb{N}_{\geq 2}$ is fixed and that we have a sequence $a_k$ with the property $a_k = o(2^{k/m})$ for $k \to \infty$, i.e. $\lim_{k \to \infty} \frac{a_k}{2^{k/m}} = 0$. Is there a chance to show, that

$\sum_{k=1}^{\lfloor\log_2(n)\rfloor} a_k = o(n^{1/m})$ for $n \to \infty$

holds true?

Probably the result is either false or trivial to prove, but I'm neither able proving it nor finding a counterexample.

Any help, hints or suggestions would be great.

Thanks in advance.

Student1369321
  • 145
  • Presumably you mean that $m$ is fixed and $n\to\infty$. We're given that for every $\varepsilon$, there exists $k_0$ such that $a_k < \varepsilon 2^{k/m}$ for $k\ge k_0$. What does that upper bound for $a_k$ imply as an upper bound for the sum? – Greg Martin Mar 31 '22 at 16:54
  • Thanks for the hint regarding the assumptions, I edited my question. – Student1369321 Mar 31 '22 at 17:50
  • 1
    @GregMartin If we choose $\varepsilon > 0$ arbitrary, then we find $k_0$ such that $a_k < \varepsilon 2^{k/m}$ for any $k \geq k_0$. If I did my computations right we get $\sum_{k=1}^{\log_2(n)} a_k < c_1 + \varepsilon c_2 n^{1/m}$. So we find $C > 0$ such that $\sum_{k=1}^{\log_2(n)} a_k < \varepsilon C n^{1/m}$ for sufficiently large $n$. And since $\varepsilon$ is chosen arbitrary this already completes the proof. Was that your idea? – Student1369321 Mar 31 '22 at 17:52
  • Your sum is bounded by a geometric series with ratio $2^{1/m}$; try and evaluate that geometric series explicitly and see what it is in terms of $n$. – Steven Stadnicki Mar 31 '22 at 17:53
  • Yes, that's the idea, well done! – Greg Martin Mar 31 '22 at 22:37
  • @PaulSinclair The title is wrong. Initially I planned to ask the question for big O, I'll fix this. – Student1369321 Apr 01 '22 at 20:56

0 Answers0