Телескопічні суми

Awww! MASSAGE is very fun! AWWW!!

In this article we are going to talk about a simple yet powerful tactic, massaging. That is a pretty bad name, doesn't it? (Maybe you think it is a good name, I don't care) But actually, if you massage an expression or an equation or even a term, you are "loosen them up" so that you can solve it easier (that's why I said that this is a great tactic). But you must have no idea on how to massage an expression by only reading the long and trashy text above, right? So, let's look at an example, shall we?

Example. Let $A=\displaystyle\sum^{10,000}_{n=1}\frac{1}{\sqrt n}$. Find $\lfloor A \rfloor$ without using a calculator. (Even you use a calculator, you also have no enough time to press up to 10,000, except you use Wolfram Alpha :P)

Solution. We can use massaging here since we don't need an exact value, luckily. Through massaging, we can make the sum telescope. We have $\frac{1}{\sqrt n}=\frac{2}{2\sqrt n} < \frac{2}{\sqrt n +\sqrt {n-1}} = 2(\sqrt n -\sqrt {n-1})$

(In this step, we rationalised the denominator)

On the other hand,

$\frac{1}{\sqrt n}>\frac{2}{\sqrt {n+1}+\sqrt n}=2(\sqrt{n+1}-\sqrt n)$

Implying

$2(\sqrt{n+1}-\sqrt n)<\frac{1}{\sqrt n}<2(\sqrt n-\sqrt{n-1})$

That looks great, right? We had just bound the deadly term $\frac{1}{\sqrt n}$ above and below by the terms that will telescope greatly when summed. Therefore,

$\displaystyle\sum^{10,000}_{n=1}2(\sqrt{n+1}-\sqrt n)=2\sqrt{10,001}-2$ and $\displaystyle\sum^{10,000}_{n=1}2(\sqrt n-\sqrt{n-1})=2\sqrt{10,000}-\sqrt 0$

Implying

$2\sqrt{10,001}-2<\frac{1}{\sqrt n} < 2\sqrt{10,000}-\sqrt 0 \Longrightarrow \lfloor A \rfloor= 198 \text{ or } 199$

Let me ask you something, which is the correct answer, 198 or 199, in your opinion? You can't decide it right? So, let's refine this estimate! When n=1, we get $2(\sqrt 2 -1)<1<2\sqrt 1$. Lower limit is good, but that's too terrible for upper limit! How about we start the summation at n=2? We have

$A=1+\displaystyle\sum^{10,000}_{n=2}\frac{1}{\sqrt n}$

And we estimate

$2\sqrt{10001}-2\sqrt 2<\displaystyle\sum^{10,000}_{n=2}\frac{1}{\sqrt n}<2\sqrt{10,000}-2\sqrt 1$

The lower limit is about 197, while the upper limit is 198. So, A is somewhere at 198 and 199, implying $\lfloor A \rfloor = 198$.