комбинаторика - Сумма биномиальных коэффициентов

Можно дать доказательство, опирающееся на комбинаторный смысл биномиальных коэффициентов, а также чисел Фибоначчи.

С биномиальными коэффициентами всё ясно: $%C_n^k$% выражает число способов выбрать $%k$% элементов из $%n$%. Для чисел Фибоначчи надо взять любую задачу, в которой возникает такой ответ. Например, пусть нас интересует число строк из нулей и единиц длиной $%n$%, где никакие две единицы не идут подряд. При $%n=0$% такая строка одна (пустая), при $%n=1$% их две. Далее при $%n\ge2$% строка оканчивается либо на 0, либо на 01. Поэтому число таких строк будет равно сумме двух предыдущих чисел последовательности -- для длин $%n-1$% и $%n-2$% соответственно. Это и есть рекуррентная зависимость для чисел Фибоначчи.

Если мы положим $%F_1=F_2=1$% и далее $%F_n=F_{n-1}+F_{n-2}$% при $%n\ge3$%, то окажется, что число $%F_{n+2}$% описывает количество строк длиной $%n$% с указанным выше свойством. Допишем 0 у строки слева. Тогда получатся строки длиной $%n+1$%, начинающиеся с нуля, у которых 11 не встречается в качестве подстроки. Мы показали, что их количество равно $%F_{n+2}$%, а теперь сосчитаем его же другим способом.

Легко видеть, что все такие строки составляются из 0 и 01 в произвольном количестве. Пусть $%k\ge0$% -- число единиц в строке. Тогда 01 встречается столько же раз, и общее число позиций для 0 и 01 равно $%n+1-k$%. На этих местах 01 можно расставить $%C_{n+1-k}^k$% способами, где $%2k\le n+1$%. Если эти числа просуммировать по всем допустимым значениям $%k$%, то получится сумма $$C_{n+1}^0+C_n^1+C_{n-1}^2+\cdots+C_{n+1-k}^k+\cdots$$ из левой части равенства. Она равна $%F_{n+2}$%, что и требовалось.

Хотя чисто комбинаторные доказательства обычно оказываются более предпочтительными, в данном случае прямая вычислительная проверка рекуррентной формулы выглядит даже несколько проще с учётом правила формирования элементов треугольника Паскаля.