29
$\begingroup$

We all know the story related to Gauss that Gauss' class was asked to find the sum of the numbers from $1$ to $100$ as a "busy work" problem and and he came up with $5050$ in less than a minute. He used a simple trick $50\times 101=5050$ there.

Now what if in some parallel universe, his teacher knew Gauss would figure that out quickly and asked the class to calculate $$1+\frac12+\frac13+\frac14+ \dots +\frac1{100}$$ instead, and assures himself a nice nap.

Is there any way Gauss could still impress the world in that universe by calculating it precisely up to, say, two decimal points using some trick (assuming he knows advanced mathematics too, although still in junior class). I do not see any quicker way to find this sum and had to use wolfram alpha which gives $$\frac{14466636279520351160221518043104131447711}{2788815009188499086581352357412492142272} \approx 5.1873.$$

What is the best method/trick to reach around $5.1$ or even $5$ quickly than any other student in your class, and impress the world?

We can make G.P's like $(1+\frac12+\frac14+\frac18+\frac1{16}+\frac1{32}+\frac1{64})+(\frac13+\frac19+\frac1{27}+\frac1{81})$ but we still leave way too many terms out of the G.P.'s and will have to find them separately by dividing.

$\endgroup$
  • 3
    $\begingroup$ This is called the 100th harmonic number, written $H_{100}$. We have approximations for $H_n$ but no nice, exact formulae. $\endgroup$ – Akiva Weinberger Aug 19 '15 at 3:51
  • 5
    $\begingroup$ $H_n\approx\ln(n)+\gamma$ where $\ln$ is the logarithm to the base $e=2.718\dots$ and $\gamma$ is the constant $0.577\dots$. $\ln100+\gamma\approx5.18239$. $\endgroup$ – Akiva Weinberger Aug 19 '15 at 4:00
  • 3
    $\begingroup$ Here's something interesting for you to try to prove: $H_n$ always has an odd numerator and even denominator, except for $H_1=1$. This means that it is never an integer again. $\endgroup$ – Akiva Weinberger Aug 19 '15 at 4:03
  • 1
    $\begingroup$ (Cont'd) In fact, no sum $\frac1n+\frac1{n+1}+\dotsb+\frac1m$ is an integer, except, again, for $n=m=1$. $\endgroup$ – Akiva Weinberger Aug 19 '15 at 4:06
  • 1
    $\begingroup$ This is somewhat similar to this recent question. (But this question is much better motivated.) $\endgroup$ – Martin Sleziak Aug 19 '15 at 6:27
23
$\begingroup$

Euler's identity would be easiest: $$H_n \approx \ln n + \gamma$$ Then (assuming no calculators) you would remember that $\ln 10 \approx 2.3$, so that $\ln 100 \approx 4.6$, getting that: $$H_{100} \approx 4.6+ 0.577 \approx 5.18$$

Now, one may argue that this is a bit of a cheat, since, $\gamma$ is sort of defined by the difference between $H_n$ and $\ln n$. What one could do however, is calculate $\gamma$ knowing that most of the contribution comes from the first few members of the series, since the difference between the sum and the integral becomes smaller as the derivative becomes smaller. This is something an older Gauss could have potentially worked out without Euler's work.

Let's take $n=10$ for example: $$\gamma \approx H_{10} - \ln 10$$ So that we get: $$H_{100} \approx \ln 10 + H_{10}\approx 2.3 + 2.9 = 5.2$$ Which is pretty close, considering all you had to do was sum up the first $10$ numbers, which only involves a single long division!

$\endgroup$
  • 1
    $\begingroup$ That should work fine, assuming in that parallel universe, junior Gauss was a fan of Euler's work. Thanks a lot. $\endgroup$ – Bhaskar Vashishth Aug 19 '15 at 7:01
  • $\begingroup$ @BhaskarVashishth - see the update, this should be more convincing. $\endgroup$ – nbubis Aug 19 '15 at 7:09
11
$\begingroup$

Well, I think he would be smart enough to realize that since it is difficult to calculate all that 100 times without an error, maybe he would decide to estimate the regions around $\frac{1}{2^k}$ in this manner

$1$ and $\frac{1}{2}$ both region size $0$ so we take $1+\frac{1}{2}$

Around $\frac{1}{4}$ we take symmetrically $\frac{1}{3}+\mathbf{\frac{1}{4}}+\frac{1}{5} \approx \frac{3}{4}$, we take all three to be equal to $\frac{1}{4}$

Around $\frac{1}{8}$ we take again symmetrically from where we left off $\frac{1}{6}+\frac{1}{7}+\mathbf{\frac{1}{8}}+\frac{1}{9}+\frac{1}{10} \approx \frac{5}{8}$

Around $\frac{1}{16}$ we take $\frac{1}{11}+\frac{1}{12}+\frac{1}{13}+\frac{1}{14}+\frac{1}{15}+\mathbf{\frac{1}{16}}+\frac{1}{17}+\frac{1}{18}+\frac{1}{19}+\frac{1}{20}+\frac{1}{21} \approx \frac{11}{16}$

...

If we continue in this symmetrical manner, it is not difficult to actually count how many approximations we would have, or to realize it is $2k \pm 1$ formula except for the last one

$$1+\frac{1}{2}+\frac{3}{4}+\frac{5}{8}+\frac{11}{16}+\frac{21}{32}+\frac{43}{64}+\frac{15}{128}$$

There is not much to calculate just gather.

$$1+\left (\frac{1}{2}+\frac{3}{4} \right )+\left (\frac{5}{8}+\frac{11}{16} \right )+\left (\frac{21}{32}+\frac{43}{64} \right )+\frac{15}{128}=$$ $$1+\frac{5}{4}+\frac{21}{16}+\frac{85}{64}+\frac{15}{128}=$$ $$1+1+1+1+\frac{1}{4}+\frac{5}{16}+\frac{21}{64}+\frac{15}{128}=$$ $$4+\frac{1}{4}+\frac{4}{16}+\frac{1}{16}+\frac{21}{64}+\frac{15}{128}=$$ $$4+\frac{1}{2}+\frac{1}{16}+\frac{21}{64}+\frac{7}{64}+\frac{1}{128}=$$ $$4+\frac{1}{2}+\frac{1}{16}+\frac{28}{64}+\frac{1}{128}=$$ $$4+\frac{1}{2}+\frac{1}{16}+\frac{7}{16}+\frac{1}{128}=$$ $$4+\frac{1}{2}+\frac{1}{2}+\frac{1}{128}=5+\frac{1}{128}$$

Back to the future: 200 years later

This method is completely acceptable since the estimated error for each group is around $0.03$ and it is steady. We just need to add $\sim 0.03$ each time we create a group. In very young Gauss' case that would be 6 groups created, so the error estimate would be $0.18$. He might be able to guess this as well just by calculating first few groups and noticing that the error remains steady. It reduces the calculation from $n$ to $\log(n)$ additions with smaller numbers.

The error at infinity is analytically exactly $\log(2)-\frac{2}{3} \approx 0.02648$ which is kind of "Euler $\gamma$" for the above method. (The difference is that you need to add a value close to this one for each group.)

A real-life reason he might have guessed this method is that as long as we are close to $2^k$, $2^k-m$ and $2^k+m$ together form a pair whose value is close to $2 \cdot 2^k$. For example, for the group around $\frac{1}{8}$, last two are $\frac{1}{6}$ and $\frac{1}{10}$, and $10 \cdot 6 $ is not far from $64$.

$\endgroup$
4
$\begingroup$

Even on an off day, young Gauss would have seen at a glance that

$$\begin{align} 1+{1\over2}+\cdots+{1\over10}&=\left(1+{1\over2}+{1\over3}+{1\over6}\right)+\left({1\over4}+{1\over5}+{1\over8}+{1\over10} \right)+\left({1\over7}+{1\over9} \right)\\ &=2+(.25+.2+.125+.1)+(.142857...+.111111...)\\ &=2.675+.253968...\\ &=2.928968... \end{align}$$

A suitably precocious Gauss would have sensed that

$${1\over11}+\cdots+{1\over100}\approx\int_{10.5}^{100.5}{dx\over x}=\ln\left(201\over21 \right)=\ln\left(67\over7 \right)=\ln10+\ln\left(1-{3\over70} \right)$$

and he would have known that $\ln10=2.302585...$ and $\ln(1-{3\over70})\approx-{3\over70}=-.042857...$

Finally, young Gauss would have figured that a decent two-digit approximation would be

$$2.93+2.30-.04=5.19$$

What unclear (to me, at least) is how he would have handled the error estimates to know how close he'd come.

$\endgroup$
2
$\begingroup$

The approximation $$H_n\approx\log(2n+1)$$ https://math.stackexchange.com/a/1602945/134791

could be used twice

$$H_{100}\approx \log(201)=\log(3)+\log(67)\approx H_1+H_{33}=\frac{66803685795949}{13127595717600}=5.088...$$

to get an approximation within 2% computing about one third of the sums.

$$\frac{H_{100}}{H_1+H_{33}}=1.019...$$

A slightly worse approximation with about one fifth of the sums is given by: $$H_{100}=H_{101}-\frac{1}{101}\approx \log(203)-\frac{1}{101}=\log(7)+\log(29)-\frac{1}{101}\approx H_3+H_{14}-\frac{1}{101}=\frac{184711333}{36396360}\approx5.075$$

$\endgroup$
0
$\begingroup$

Euler invented some convergence acceleration methods. Probably as an adult, though.

https://en.wikipedia.org/wiki/Series_acceleration

$\endgroup$
0
$\begingroup$

Maybe Gauss would have reached $$H_{100}\approx 1+6\log(2)$$

from $$\lim_{n \to \infty}\left(\log\left(e^\gamma n+1\right)-H_n\right)=0$$ and $$e^\gamma\approx\frac{7}{4}$$ so $$H_n\approx\log\left(\frac{7}{4}n+1\right)$$

For $n=100$, this is $$H_{100}\approx\log\left(\frac{7}{4}100+1\right)=\log\left(176\right)= 4\log\left(2\right)+\log\left(11\right)$$

but $\log(11)$ is related to $\log(2)$ through the first harmonic number by the same approximation

$$\log(11)=\log(7+4)=\log(7/4+1)+\log(4)\approx H_1-2\log(2)=1+2\log(2)$$ so $$H_{100}\approx 1+6\log\left(2\right)=5.15888...$$

Now using $\log(2)\approx\frac{2}{3}$ would yield $$H_{100}\approx 5$$ while $\log(2)\approx\frac{7}{10}$ would lead to $$H_{100}\approx 5.2$$

$\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.