Сумма чисел Фибоначчи

Определим сумму первых n чисел Фибоначчи.

0 = 0,

0+1 = 1,

0+1+1 = 2,

0+1+1+2 = 4,

0+1+1+2+3 = 7,

0+1+1+2+3+5 = 12,

0+1+1+2+3+5+8 = 20,

0+1+1+2+3+5+8+13 = 33.

Легко заметить, что прибавлением к правой части каждого уравнения единицы мы снова получаем число Фибоначчи. Общая формула для определения суммы первых n чисел Фибоначчи имеет вид:

.

Докажем это, используя метод математической индукции. Для этого запишем:

.

Эта сумма должна быть равна .

.

Сократив левую и правую часть уравнения на –1, получим уравнение (6.1).