Glossary / Harmonic series
Put a book on the edge of a table and slide it out until it is about to fall: it sticks out by exactly half. Now pile books on top of one another, each a bit further out than the one below. It seems you can't get far this way: the stack will topple as soon as the top book is a length or two past the edge. In fact, with enough books, the top one can hang out over the floor as far as you like. It is all down to the harmonic series: the sum 1 + ½ + ⅓ + ¼ + …, which grows without end, if unbelievably slowly.
“In plain words” is hidden on all puzzles.
Add books. Each new one goes underneath, and the whole stack above it is pushed out as far as it can go without falling. The scale stays fixed: the dashed lines are book lengths past the table edge. How many books does it take for the top one to be completely past the edge?
How many books it takes for the top one to overhang by:
The picture holds up to 300 books; the rest we calculated.
The first book sticks out by half a length, the second adds a quarter, the third a sixth, the fourth an eighth. Each next one gives less, and it feels as if such crumbs must stop somewhere. But they don't. With four books the top one is already entirely over the floor, with 31 it is two lengths out. The price grows terribly: five lengths take 12,367 books. At 3 cm each, that is a stack 371 m tall, higher than the Eiffel Tower. And yet there is no limit: any distance can be exceeded.
“Rigorous” is hidden on all puzzles.
The harmonic series is the sum of the reciprocals of the whole numbers: 1 + ½ + ⅓ + ¼ + … The sum of the first n terms is called the n-th harmonic number and written Hn. The series diverges: Hn grows without bound, even though the terms shrink to zero.
H4 = 1 + 1/2 + 1/3 + 1/4 = 25/12 ≈ 2.08 · H10 ≈ 2.93 · H100 ≈ 5.19 · H1000 ≈ 7.49
The book stack is the same series, just halved: n books overhang by ½ · Hn book lengths. With 4 books that is ½ · 25/12 = 25/24, a little over one length.
Compare it with 1 + ½ + ¼ + ⅛ + …, where each term is half the one before. Its terms also shrink to zero, even faster. But it never gets past 2: each step covers only half of the distance still left to two. The harmonic series barely trails it at first, then climbs slowly but relentlessly. Switch the scale.
How many terms does it take for the sum to pass a given number? Add one term a second and see how long it would take.
“Deeper” is hidden on all puzzles.
Around 1350 the French philosopher Nicole Oresme spotted a simple trick. Group the terms: the second group has two terms, the third four, the fourth eight. In each group every term is at least as big as the last one, so the whole group is at least a half.
1 + ½ + (⅓ + ¼) + (1/5 + 1/6 + 1/7 + 1/8) + … ≥ 1 + ½ + (¼ + ¼) + (⅛ + ⅛ + ⅛ + ⅛) + … = 1 + ½ + ½ + ½ + …
H2k ≥ 1 + k / 2
There are infinitely many halves, so the sum will exceed any number. See how the bound holds from below.
The bound is crude: the real sum grows faster than ½ per group. But that is enough for a proof.
The sum 1/1 + 1/2 + … + 1/n is almost the area under the curve 1/x from 1 to n, and that area is the natural logarithm ln n. The gap between them doesn't grow but settles on a constant γ ≈ 0.5772, named after Leonhard Euler. It is still unknown whether γ can even be written as an ordinary fraction.
Hn = ln n + γ + 1/(2n) − …
This gives the numbers from the section above: for Hn to pass t you need n ≈ et − γ. For 10 that is about 12,367; for 100, about 1.5 · 1043 terms. That is exactly how many books it takes for a stack to overhang by 50 lengths.
A stack stands as long as the common centre of mass of every top part lies over the book beneath it. So the furthest you can go is to place the centre of mass of the top k books exactly over the edge of book k + 1. Suppose that is so, and measure from that edge. The centre of the k books is at the edge, at zero, and the centre of book k + 1 is half a length further in. The common centre of the k + 1 books is the weighted average:
(k · 0 + 1 · ½) / (k + 1) = 1 / (2(k + 1))
That is exactly where the edge of the next book must be, so book k + 1 sticks out past it by 1/(2(k + 1)). Adding the shifts 1/2, 1/4, 1/6, …, 1/(2n) gives ½ · Hn. The last shift is over the table: the centre of mass of the whole stack sits exactly on the table edge.
That is the record for a stack with one book on each level. If several books may lie side by side and act as counterweights, the overhang grows much faster: Mike Paterson and Uri Zwick showed this in 2006.
One more paradox. Remove from the harmonic series every term 1/n whose n contains the digit 9: 1/9, 1/19, 1/90, 1/199… It seems we threw out a trifle, as nines are rare among small numbers. But the sum becomes finite, below 80. There are 8 · 9d − 1 d-digit numbers without a nine, and each of their reciprocals is at most 1/10d − 1. So the whole sum is at most
8 · (1 + 9/10 + (9/10)2 + …) = 8 · 10 = 80
The point is that among very long numbers almost all contain a nine. We are not throwing out a trifle but nearly the whole series. This series was studied by Aubrey Kempner in 1914.
The middle value: line everyone up in order, and half are below it, half above.
A millionaire walks into a bar: the average income shoots up, the median barely moves.
The sum of all values divided by how many there are: what everyone would get if it were shared equally.
Almost everyone has more legs than average: the average is a little under two.
The average result you can expect if you repeat the same thing very many times.
A die's expected value is 3.5, yet no face shows 3.5.
A number from −1 to +1 showing how closely two quantities move together.
In summer both ice cream sales and drownings go up. Ice cream isn't to blame: the heat drives both.
A measure of spread: how far values typically stray from the mean. The standard deviation is its square root, in the same units.
Two towns with the same average temperature: one stays near +15 all year, the other swings from −20 to +50.
A bell-shaped distribution: most values sit near the mean, and the further away, the rarer.
Every ball on a Galton board falls at random, yet thousands of balls always build the same bell.
The more repetitions, the closer the share of an outcome gets to its true probability.
The share of heads creeps towards 50%, while the gap between heads and tails in coins usually grows.
The chance of an event given that something else is already known.
Almost all NBA players are tall, but almost all tall people are not NBA players.
Events are independent if knowing about one doesn't change the chances of the other.
After five heads in a row tails is no more likely: the coin remembers nothing.
How many times you multiply the base by itself to get a number: log₂ 8 = 3, because 2 · 2 · 2 = 8.
A sheet of paper folded in half 42 times would be thicker than the distance to the Moon.
A sample some people get into more easily than others, so it describes everyone badly.
In 1936 a magazine polled millions of Americans and still picked the wrong election winner.
How often chance alone would produce a gap at least as big as yours if there were really no difference.
When there is no effect at all, p below 0.05 turns up as often as p between 0.50 and 0.55.
A range around a measured number, built by a method that covers the true value in a chosen share of samples, such as 95%.
Of twenty honest 95% intervals, on average one misses the truth, and none of them knows whether it is the one.
The probability that a test notices a real effect of a given size. A power of 80% means the test misses one working effect in five.
A weak A/B test that does find an effect almost always exaggerates it: a real +10% shows up on the dashboard as +24%.
How far an average or a rate computed from a sample usually misses the truth: σ divided by the square root of the sample size.
Halving the error takes four times as much data.
Counting how many ways things can be ordered or chosen: permutations n!, combinations C(n, k).
A well-shuffled deck is almost certainly in an order nobody has ever seen.
The rule for updating confidence when new evidence arrives: prior odds × strength of the evidence.
Two weak pieces of evidence together can be strong, while one striking piece means little if the claim was unlikely.
Growth where a quantity is multiplied by the same factor each time, so it doubles at equal intervals.
One grain on the first square of a chessboard, doubling on each next one: the last square holds as much rice as the world grows in over 300 years.
A path where each next step is taken at random: forward or back, left or right.
A drunk man will always find his way home, but a drunk bird may never return.
A stream of independent random events at a constant average rate: calls, Geiger clicks, raindrops.
In 1944 Londoners thought German flying bombs were aimed at certain districts; it was ordinary random clumping.