0
$\begingroup$

Working with asymptotics, I frequently encounter expressions of the following form in my upper bound: $$\sum_{k=1}^{f(n)} g(n)^k$$ Almost always, I have trouble simplifying them. An example of something I had to simplify recently: $$\sum_{k=1}^{\sqrt n} n^{-k/2} = \frac{1 - n^{-\sqrt{n}/2}}{\sqrt n - 1}$$ I only got the RHS by Wolfram Alpha, but I want to know the step that can get me there. Suppose I start with the standard formula for geometric sum, how would I get to this? In general, what techniques are there to simplifying the geometric sum formula?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

The terms of the sum $\sum_{k=1}^{f(n)} g(n)^k$ form a geometric progression. For such sums there is a simple formula, which in this particular case yields $$\sum_{k=1}^{f(n)} g(n)^k=g(n)\frac{1-g(n)^{\lfloor f(n)\rfloor}}{1-g(n)\hphantom{{}^{\lfloor f(n)\rfloor}}}.$$ In your example $g(n)=n^{-1/2}=\tfrac{1}{\sqrt{n}}$ and $f(n)=\sqrt{n}$, so that $$\sum_{k=1}^{\sqrt n} n^{-k/2} =\frac{1}{\sqrt{n}}\frac{1-(\tfrac{1}{\sqrt{n}})^{\lfloor\sqrt{n}\rfloor}}{1-\tfrac{1}{\sqrt{n}}} =\frac{1-\sqrt{n}^{-\lfloor\sqrt{n}\rfloor}}{\sqrt{n}-1}.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .