Пусть утверждение для n верно:
Тогда надо доказать утверждение для n
+ 1:
Начнём доказательство:
Извлечём из первой суммы слагаемое при k = 0
Извлечём из второй суммы слагаемое при k = n
Теперь сложим преобразованные суммы:
Что и требовалось доказать