6

Some time ago, I was given a homework, which, among other things, asked to demonstrate the following equality: $$\left\lfloor \sum_{k=1}^{10000} {1 \over \sqrt k}\right\rfloor = 198$$ I've tried a few things but nothing got me too far; I haven't found anything on the Internet about this, either (at least not satisfactory enough).

I've also wondered if/how it'd be possible to find the result for any positive integer $n$, i.e. to find $q$ such that $$\left\lfloor \sum_{k=1}^n {1 \over \sqrt k}\right\rfloor = q$$

EDIT: Thanks a lot for all your responses. This problem (at least in my case) is for 9th grade, so no integration allowed (or calculus in general), although I'm not sure a proof of that level is possible; your responses are good enough for me, anyways.

Eckchart
  • 63
  • Please give some background, so we know what techniques are appropriate. Was this for a calculus course? Do you know about integration? – saulspatz Jun 30 '19 at 22:46
  • 6
    I've tried a few things but nothing got me too far Could you elaborate on what those few things are? – Lee David Chung Lin Jun 30 '19 at 22:47
  • @LeeDavidChungLin Well, actually, it was mostly nothing: stuff like trying to sum only the square roots of the perfect squares or find some upper bound for the sum, thinking I could get somewhere, when in fact I was just stumped and had no idea what I should do or where I should even begin. – Eckchart Jul 01 '19 at 11:21

3 Answers3

3

In Apostol's Number Theory textbook it is shown using Euler's summation formula that for all $0<s<1$, $$ \sum_{k=1}^n\frac{1}{k^s}=\frac{n^{1-s}-1}{1-s}+1-s\int_1^n\frac{t-\lfloor t\rfloor}{t^{s+1}}\ dt\qquad (1). $$ Observe that for all $n>1$, $$ 0< \int_1^n\frac{t-\lfloor t\rfloor}{t^{s+1}}\ dt\leq \int_1^{\infty}\frac{1}{t^{s+1}}\ dt=\frac{1}{s}. $$ Using these bounds in $(1)$ implies that $$ 0\leq\sum_{k=1}^n\frac{1}{k^s}-\frac{n^{1-s}-1}{1-s}<1. $$ Consequently, it follows that $$ \left\lfloor\sum_{k=1}^n\frac{1}{k^s}\right\rfloor=\frac{n^{1-s}-1}{1-s} $$ whenever the right side is an integer. In particular, when $n=10^4$ and $s=\tfrac12$ the right side evaluates to the integer $198$, and this answers your question.

To answer your more general question, observe that our integer condition when $s=\tfrac12$ requires that $2(\sqrt{n}-1)$ be an integer, or equivalently, that $n$ is a perfect square. Thus, $$ q=2(\sqrt{n}-1), $$ whenever $n$ is a perfect square. For non-square $n$, our bounds imply that rounding $2(\sqrt{n}-1)$ will get you to within $1$ of the correct answer.

pre-kidney
  • 30,223
3

$\frac 1 {\sqrt {k+1}}<\int_k^{k+1} \frac 1 {\sqrt x} dx < \frac 1 {\sqrt k}$. Sum over $k$ and use the fact that $2\sqrt x$ is an anti-derivative for $\frac 1 {\sqrt x}$ to derive the following inequality: $198-\frac 1 {100} <[\sum_{k=1}^{10000} \frac 1 {\sqrt k}]<199$. Hence the result.

Proof of $\frac 1 {\sqrt {k+1}}<\int_k^{k+1} \frac 1 {\sqrt x} dx < \frac 1 {\sqrt k}$: $\int_k^{k+1} \frac 1 {\sqrt x} dx <\int_k^{k+1} \frac 1 {\sqrt k} dx$ because $1 {\sqrt x} <1 {\sqrt k}$ when $k<x<k+1$. Hence $\int_k^{k+1} \frac 1 {\sqrt x} dx < \frac 1 {\sqrt k}$. Similarly you get the other inequality by noting that $\frac 1 {\sqrt x} > \frac 1 {\sqrt{ k+1}}$ when $k<x<k+1$].

Kavi Rama Murthy
  • 311,013
3

If you draw the stair-step graph of the sum (that is, the graph is $1$ between $x=1$ and $x=2$ and it's $1/\sqrt{2}$ between $2$ and $3$, etc.) and also draw the graph of $y=1/\sqrt{x}$, then you'll see that the sum is greater than

$$\int_1^{10001} \frac{1}{\sqrt{x}} \; dx = 198.01.$$

Then if you imagine pushing the stair-step function to the left one unit, you see that the sum is less than

$$1+\int_1^{10000} \frac{1}{\sqrt{x}} \; dx = 199.$$

B. Goddard
  • 1