本定理来自一道算法竞赛题：

给定任意多条边，每条边都是不超过1,000,000,000的正整数。请给出一个算法，判断其中是否存在3条边可以构成三角形。

应用该定理可以有效地解决此问题。

定理

给定n个边长，如果其中最大的边长与最小的边长的比值小于第n个斐波那契数，那么其中必存在3个边长可以构成三角形。

应用

由题中条件可知，最大的边长和最短的边长的比值不超过\(1,000,000,000 < F_{45}\)。所以，只要边的个数达到45，根据上述定理，就必然存在3条边可以构成三角形。如果边的个数少于45个，也很好办，穷举解决即可（\({45 \choose 3} = 14190\)，穷举量很小）。

证明

使用反证法，承认条件但否定结论，即假设给定的n个边长中的任意3个都不能构成三角形。将n条边以由小到大的顺序记作\(s_1, s_2, \dots, s_n\)。我们将用归纳法证明\(s_n / s_1 \geq F_n\)，其中\(F_n\)表示第n个斐波那契数。

当\(k=1,2\)时，\(s_1 / s_1 = 1 \geq F_1, s_2 / s_1 \geq 1 \geq F_2\)显然成立。假设\(s_k / s_1 \geq F_k, s_{k+1} / s_1 \geq F_{k+1}\)成立，那么因为\(s_k, s_{k+1}, s_{k+2}\)三者不能构成三角形，所以最长的边不会小于另外两边之和。所以有\(s_{k+2}/s_1 \geq (s_k + s_{k+1}) / s_1 \geq F_k + F_{k+1} = F_{k+2}\)。接下来使用归纳法即可。

我们所得到的结论和条件相矛盾：\(s_n / s_1 \geq F_n\)。这说明假设不成立，所以，定理是成立的。