У меня есть эта программа, которая при запуске печатает по этому шаблону:
a (0) = 0
a (1) = 1
a ( 2) = 2 + a (1) = 3
a (3) = 3 + a (2) + a (1) = 3 + 3 + 1 = 7
a (4) ) = 4 + 3 + 3 + 1 = 15
В этот момент я наблюдаю, что существует закономерность его превращения в O (2 ^ n - 1). Однако я не уверен, является ли это действительным доказательством по индукции. У меня была идея:
a (n) = n + a (n-1) + a (n-2) + ... + 1 = 2 ^ n - 1
Но отсюда схема для терминов мне не очень понятна. Я знаю, что первое слагаемое равно n (в нашем коде это из-за a для l oop, который печатает инструкцию n раз), и из-за рекурсии я знаю, что буду суммировать предыдущие значения, но я не знаю, что а (n-1), а (n-2) и др. c. с точки зрения п.