9. Доказательство формулы (строгое)

Для полноты приведём строгое доказательство методом математической индукции.

База индукции: при n=1 формула даёт S1=b1(q1)q1=b1 — верно.

Индукционный переход: предположим, что формула верна для n=k:
Sk=b1(qk1)q1

Тогда Sk+1=Sk+bk+1=b1(qk1)q1+b1qk

Приведём к общему знаменателю:
Sk+1=b1(qk1)+b1qk(q1)q1=b1(qk1+qk+1qk)q1=b1(qk+11)q1

Что и требовалось доказать.