11
$\begingroup$

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?

$\endgroup$
13
$\begingroup$

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 n}<\int_m^{n+1}\frac{dx}{\sqrt{x-1}},$$ or

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

Then for the complete sum

$$\sum_{k=1}^{m-1}\frac1{\sqrt n}+2(\sqrt{n+1}-\sqrt m)\le\sum_{k=1}^n\frac1{\sqrt n}<\sum_{k=1}^{m-1}\frac1{\sqrt n}+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.

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

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 !

$\endgroup$
7
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.