# Finding summation of inverse of square roots.

Problem: Find the integer part of $$\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} +...+\frac{1}{\sqrt{1000000}}$$

How should I go about approaching this question? I have never seen such a question before, where you cannot multiply any conjugate or whatsoever. What is the method to go about approaching such problems?

• Experiments with WolframAlpha has let me to believe that the integer part of your sum, in general from $\frac1{\sqrt1}$ to $\frac1{\sqrt{a^{2n}}}$, is $2\cdot a^n - 2$ (integers $a, n$). I have no idea how to prove it, though. The integral $\int_1^{2n+1}\frac1{\sqrt{x}}dx$ gives an approximation, but going from there to the exact integer part... Jan 11, 2018 at 10:32
• You can try the Euler-Maclaurin summation formula.
– user65203
Jan 11, 2018 at 10:50
• Several similar posts:math.stackexchange.com/questions/1854810/…, Jan 11, 2018 at 10:50
• Jan 11, 2018 at 10:51

For an precalculus (telescoping) approach. Notice that $$\frac{1}{\sqrt n}>\frac{2}{\sqrt{n}+\sqrt{n+1}}=2(\sqrt{n+1}-\sqrt{n})$$ From this $$\frac{1}{\sqrt{1}}+\frac1{\sqrt2}+\cdots+\frac1{\sqrt{1000^2}}\geq 2(\sqrt 2-1+\sqrt 3-\sqrt 2+\cdots+\sqrt{1000^2+1}-\sqrt{1000^2})\geq 2\sqrt{1000^2+1}-2>2000-2=1998$$ And also $$\frac{1}{\sqrt n}\leq\frac{2}{\sqrt n+\sqrt{n-1}}=2(\sqrt n-\sqrt{n-1})$$ Leaving the $n=1$ case alone we get $$\frac{1}{\sqrt{1}}+\frac1{\sqrt2}+\cdots+\frac1{\sqrt{1000^2}}<1+2(\sqrt 2-1+\sqrt 3-\sqrt 2+\cdots \sqrt{1000^2}-\sqrt{1000^2-1})=1+2\sqrt{1000^2}-2=1999$$

And it follows that the integer part is $1998$

By integration of

$$\frac1{\sqrt x}\le\frac1{\sqrt{\lfloor x\rfloor}}<\frac1{\sqrt{x-1}}$$

we establish a formula for the tail of the summation,

$$\int_m^{n+1}\frac{dx}{\sqrt x}\le\sum_{k=m}^n\frac1{\sqrt k}<\int_m^{n+1}\frac{dx}{\sqrt{x-1}},$$ or

$$2(\sqrt{n+1}-\sqrt m)\le\sum_{k=m}^n\frac1{\sqrt k}<2(\sqrt n-\sqrt{m-1}).$$

Then for the complete sum

$$\sum_{k=1}^{m-1}\frac1{\sqrt k}+2(\sqrt{n+1}-\sqrt m)\le\sum_{k=1}^n\frac1{\sqrt k}<\sum_{k=1}^{m-1}\frac1{\sqrt k}+2(\sqrt n-\sqrt{m-1}).$$

We can compute the bracketing for increasing $$m$$, and it turns out that $$m=2$$ suffices to establish

$$1998.17257288\le S<1999.0$$

Hence, $$\color{green}{1998}.$$

For safety, with $$m=3$$,

$$1998.24400517\le S<1998.87867966$$

Rationale of the method:

An integral approximates a sum inasmuch as the function value remains sufficiently constant in unit intervals. In the case of the inverse square root, the error per interval is

$$\frac1{\sqrt{n+1}}-\frac1{\sqrt n}=O(n^{-3/2}),$$ which decreases relatively quickly. So there is some hope that by combining a direct summation of the first terms and a bracketing of the tail, we can end up with the two bounds in the same unit interval so that we know the integer part. (The last terms won't be a problem as they correspond to a tiny error.)

We are pretty lucky here as the unit interval is found with very few terms.

Given that the width of the bracketing is

$$2(\sqrt n-\sqrt{n+1}+\sqrt m-\sqrt{m-1}),$$ we can conclude as soon as the partial sum differs from an integer by more than this amount. And the firt parial sums are approximately

$$1,1.71,2.28,2.78,3.23\cdots$$

which leave a good margin.

• Simple and nice (as usual). Cheers. Jan 11, 2018 at 11:36
• @ClaudeLeibovici: greetings, Claude. My secret (maybe I already said it): I am unable to do complicated things ;-)
– user65203
Jan 11, 2018 at 11:38
• For instance if it were to change to + then -, would the approach be the same? Jan 11, 2018 at 11:54
• @XcoderX: then you would take the terms two by two to get rid of the alternation (and get a yet faster convergence).
– user65203
Jan 11, 2018 at 11:55
• @WillJagy. Thanks for the link. It is very interesting (question and answers). Jan 12, 2018 at 4:37

If you know about generalized harmonic numbers $$S_n=\sum_{k=1}^n \frac 1 {\sqrt k}=H_n^{\left(\frac{1}{2}\right)}$$ Now, using the asymptotics $$S_n=2 \sqrt{n}+\zeta \left(\frac{1}{2}\right)+\frac1 {2\sqrt{{n}}}+O\left(\frac{1}{n^{3/2}}\right)$$ where $$\zeta \left(\frac{1}{2}\right)\approx -1.46035$$.

SO, if $$n=10^6$$, the approximation gives for your summation $$\approx \zeta \left(\frac{1}{2}\right)+\frac{4000001}{2000}\approx 1998.54$$ while the rigorous calculation would give ... the same value !

Edit (five years later)

To answer a question asked in private, considering the more general case of $$S_n=\sum_{k=1}^n \frac 1 {\sqrt[a] k}=H_n^{\left(\frac{1}{a}\right)}$$ using asymptotics $$\color{blue}{n^{\frac{1}{a}} \left(S_n-\zeta \left(\frac{1}{a}\right)\right)=}$$ $$\color{blue}{\frac{a n}{a-1}+\frac{1}{2}-\frac{1}{12 a n}+\frac 1{720}\sum_{k=1}^\infty (-1)^{k+1}\, \frac{\prod_{m=1}^{2k} (a m+1) } {\alpha_k\,(an)^{2k+1} }}$$

where the $$\alpha_k$$ form the sequence $$\{1,42,1680,66528,1816214400,103783680,14820309504000,\cdots\}$$

Multiplied by $$720$$, you will find them in sequence $$A060055$$ in $$OEIS$$.