Another proof of Fibonacci sequence in classic probability puzzle

Recently Scientific American reported that Fibonacci sequence makes an unexpected appearance in the solution to the following problem:

If I have n sticks with random lengths between 0 and 1, what is the probability that no three of those sticks can form a triangle?

The answer to this puzzle is

where is the -th Fibonacci number. This is the arxiv link for the paper which contains a proof of it. Someone posted a novel proof of this puzzle which is more linear algebraic in nature. I made a small modification on top of this proof which is what I present here. Most of the credit to this proof goes to the Reddit user.

---

0. Outline of the proof

Here is the overall idea:

• Sort the lengths from shortest to longest.
• The vector of sorted lengths can be shown to be a linear combination of a certain basis.
• Once we get this basis, we use it express the longest length in terms of it.
• Finally we use the condition that to get a simplex.

These steps are implemented below:

---

1. Steps 1 and 2 - Expressing sorted stick lengths as a matrix-vector product

We do this for two cases - the case where the lengths can not form a triangle and the general case (the lengths may or may not form a triangle).

1.1 Lengths which cannot form a triangle

Given the shortest length is , we have that . Note that has to be bigger than . We can assume that . Using the same argument, the next three lengths can be written down as:

Thus the vector of sorted lengths can be written down as:

Written out for , with one color per Fibonacci number (, , , , ), every entry is visible at once:

The general entry is

1.2 Any arbitrary vector of lengths

This case is much simpler. As before, start with . Then since , we have that and so on. For sake of completion, the remaining lengths look something like:

In this case, the vector of sorted lengths can be written down as:

The general entry is

---

2. Step 3 - largest length in each case

2.1 First case

In this case, the largest length is

for positive coefficients .

2.2 Second case

In this case, the largest length is

for positive coefficients : the same sum with every replaced by .

---

3. Step 4 - obtain simplexes for each case

Since these lengths are sampled from the interval , they have to be less than or equal to one. Applying this condition to each of the largest lengths above we get:

i) : the points that satisfy this condition form a volume . This is the volume of the simplex spanned by the origin and the vectors

for from to .

ii) : this is the standard simplex and has a volume of . The exact volume is not needed for the proof though.

---

4. Final step

The probability is given by . How do we find in terms of ? By defining a map . It is easy to see that the determinant of the Jacobian of this map is

since the map only rescales each axis. Thus the volume , and this gives us the probability to be: