I've been doing some questions to study for my analysis final next week. and I came across the following:
Let $$a_n = \sum_{k=0}^{n}(-1)^k \sqrt{k} $$
Prove that $a_n = O(\sqrt{n})$.
I've done plenty of big-oh questions when the sum is not alternating, they mainly come down to using the triangle inequality, but of course if we do that here, the best we can get is $a_n = O(n^{3/2})$. I've also used a Riemann sum type argument, but similarly I can't find a way to make that work here.
Any techniques you can recommend for how to tackle alternating sum problems like this? Is my only option induction? Do I need to split into n is even or odd cases?
Any helps or pointers in the right direction would be much appreciated, Thanks!
EDIT:
I also thought there may be a way to make use of the inequality: $$\sqrt{n+1} - \sqrt{n} < \frac{1}{2\sqrt{n}}$$
But the best I came up with using that method was $O(n)$.
Summation by parts is the key. If we consider $b_k = (-1)^k$ and $c_k= \sqrt{k}$, we have that $B_k=b_0+\ldots+b_k$ equals $1$ if $k$ is even and zero if $k$ is odd. It follows that
$$ a_n = \sum_{k=0}^{n}b_k c_k = B_n \sqrt{n} - \sum_{k=0}^{n-1}\frac{B_k}{\sqrt{k}+\sqrt{k+1}} $$ has an absolute value which is bounded by $$ \sqrt{n}+\sum_{k\leq\frac{n-1}{2}}\frac{1}{\sqrt{2k}+\sqrt{2k+1}}\leq \left(1+\frac{1}{\sqrt{2}}\right)\sqrt{n} $$ and we are done.