Another proof of Fibonacci sequence in classic probability puzzle

Recently Scientific American reported that Fibonacci sequence appears as an answer 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 i-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.

Step 1 Step 2 Step 3 Step 4 Sort stick lengths l₁ ≤ l₂ ≤ ... ≤ lₙ Express as linear combination of basis Express lₙ in terms of basis Apply condition lₙ ≤ 1 → simplex l = (l₁,l₂,...,lₙ) l = Σ cᵢbᵢ ln = Σ dibni Σ dibni ≤ 1

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:

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:

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 .

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 lie form a volume . This is the volume of the simplex formed by origin and vectors for from 1 to n.

ii) : this is the standard simplex and has a volume of . The exact area 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 Jacobian of this map is . Thus the volume . This gives us the probability to be: