Линейные рекурренции первого порядка с циклами (суммирование)

Question

У меня есть следующие повторения:

T (n) = Σ _{k = 0} ^n-1 T (k) + n + 3

Мой профессор говорит, что это упрощается до

T (n) = 2T (n - 1) + 1

Как это возможно

Answer 1

Это упрощение не является правильным. Эти повторения возвращают разные значения.

Вы не указали базовый случай для повторения, поэтому давайте предположим, что базовый случай равен T (0). Тогда имеем

• T (0) = T (0)
• T (1) = T (0) + 1 + 3 = T (0) + 4
• T (2) = T (0) + (T (0) + 4) + 2 + 3 = 2T (0) + 9
• T (3) = T (0) + (T (0) + 4) + (2T (0) + 9) + 3 + 3 = 4T (0) + 19
• ...
• T (k) = 2 ^k T (0) + 3k + k (k + 1) / 2

Это не соответствует шаблону, который вы получили бы от T (n) = 2T (n - 1) + 1:

• T (0) = T (0)
• T (1) = 2T (0) + 1
• T (2) = 2 (2T (0) + 1) + 1 = 4T (0) + 3
• T (3) = 2 (4T (0) + 3) + 1 = 8T (0) + 7
• ...
• T (k) = 2 ^k T (0) + 2 ^{k + 1} - 1.

Похоже, что либо где-то было недопонимание, либо предоставленный вам ответ был неправильным.