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

Докажем, что оба количества способов удовлетворяют одному и тому же рекуррентному соотношению

Для хромого короля рассмотрим первый момент на пути (не считая стартовой клетки), когда он попал на главную диагональ. Если это произошло первым же ходом, то мы получаем способов. Если нет, то первый ход был направо, и далее есть вариантов, в зависимости от того, в каком столбце впервые король попал на главную диагональ. Если он туда попал в по счету слева столбце, то сделал он это ходом вверх, и до этой клетки добраться было способов. С этой клетки до правой-верхней есть способов добраться. Так и получается искомое рекуррентное соотношение.

Для разрезов пронумеруем отмеченные узлы слева направо от до Пусть -й узел это наименьший узел, по которому разрез проходит от края до края исходного квадрата. Не умаляя общности, он проходит по вертикали. Если этот разрез прошел по узлу, то остается способов проделать разрезы дальше. Если по -му, то способов (потому что направление следующего разреза предопределено, а значит, вдвое меньше количества всех возможных способов провести дальнейшие разрезы). Если же по какому-то промежуточному узлу то есть способов провести разрезы слева и способов провести разрезы справа. Не забудем умножить итоговую сумму на поскольку первый разрез можно было провести в любом из двух направлений, и получим следующее соотношение:

что с учетом упрощается до искомого соотношения.