Рекурренты в комбинаторике и числа Фибоначчи f(n)

Докажем для любого натурального , что если победитель провёл не меньше боёв, то число участников не меньше , а также, что существует турнир с участниками, победитель которого провёл боёв. Для оба условия очевидны.

Пусть победитель A выиграл последний бой у боксёра B. Оставшиеся поединки фактически распадаются на два турнира: один из них выиграл A, а второй – B. В первом турнире победитель A провёл не меньше боя, значит, число участников не меньше . Во втором турнире победитель B провёл не меньше боёв, значит, число участников не меньше . Но тогда в исходном турнире число участников не меньше .

Пример же будем строить, опираясь на примеры для меньших . Достаточно свести в заключительном поединке победителя турнира с участниками, выигравшего бой, и победителя турнира с участниками, выигравшего боя.

Поскольку , отсюда следует ответ.