Thread by @gregeganSF

What these wondrous numbers giveth with one hand, they taketh with the other.

— Leonardo Bigollo Pisano, Liber Abaci (1202)

Consider the sets K_n of coin tosses that end with HH, but contain no other pair of consecutive heads.

We can modify any such sequence of tosses by:

• (blah)HH → (blah)tHH

or

• (blah)HH → (blah)HtHH

This recursively gives us all of them, and shows why:

|K_n| = F_{n-1}

Sometimes everything generalises beautifully: this all extends to the Tribonacci, Tetranacci numbers etc.

Those generalised Fibonacci numbers count the number of coin toss sequences ending with N heads, but containing no other run of N heads — and total probabilities sum to 1:

The predecessor of the Fibonacci numbers, in the sense that the Tribonacci numbers are their successor, are the Mononacci numbers:

M_0 = M_1 = ... = 1

These count the number of coin toss sequences ending with a single H, but containing no other H.

Σ_{i=1}^∞ M_{i-1}/2^i = 1

If we replace coins with (q+1)-sided dice, everything generalises.

The (p,q)-nacci numbers:

R_{0} = ... = R_{p–2} = 0
R_{p–1} = 1
R_n = q (R_{n–1} + R_{n–2} + ... + R_{n–p})

count sequences that end with p 1s but contain no other runs of p 1s.

Below are some examples for q=2.