Решение рекуррентного отношения

Question

Я не уверен, что это правильное место для публикации, но проблема на самом деле связана с заданием на программирование.Эта рекурсия - кое-что, что я, вероятно, должен знать, как решить, но у меня есть небольшая проблема с этим.

Решить рекурсию:

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

Решение:

T(n) = 2(n+1)

Может кто-нибудь показать мне, как они получили это решение?

Пожалуйста, обратите внимание, что это не основная часть задания для решения этой конкретной проблемы.

Answer 1

Вы должны выяснить, что является решением, а затем вы можете использовать индукцию, чтобы доказать это.

На рисунке решение простое.

Значение - предыдущее значение + 2.

2, 2+2, 2+2+2, 2+2+2+2, 2+2+2+2+2, ...

Используйте индукцию, чтобы доказать:

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

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

Proof:
T(n) = T(n-1) + 2 => 2((n-1)+1) + 2 = 2(n+1)

Check for n=0
2(0+1)=2

End of proof

Answer 2

Это арифметическая прогрессия с отношением общая разница 2.

Первый член - T[0] = 2, а отношение общая разницаr = 2, поэтому n + 1-й член (n + 1-й, потому что в 0, 1, 2, ..., n чисел n + 1) равен T[0] + r*(n + 1 - 1) = 2 + 2*n = 2*(n + 1).

Не нужно угадывать, просто распознайте его как арифметическую прогрессию.

Answer 3

Взять T(5):

T(5)
  |
  +-> T(4) + 2
        |
        +-> T(3) + 2
              |
              +-> T(2) + 2 
                    |
                    +-> T(1) + 2
                          |
                          +-> T(0) + 2
                                |
                                +-> 2

Теперь посчитайте количество 2, которые складываются вместе для T(5).

Затем попытайтесь выяснить, сколько 2 будет добавлено для T(n).

Answer 4

Попробуйте выписать первые несколько значений - это должно быть очевидно.

Answer 5

Каждый раз, когда n уменьшается на единицу, добавляется 2. Это дает переменный член 2n. Поскольку T (0) зафиксировано на 2, это дает постоянный член 2. Их сложение дает 2n + 2 или 2(n + 1).

Answer 6

Это довольно просто решить вручную, как указывают другие ответы, но в случае его полезности Mathematica довольно хорошо решает повторяющиеся отношения , например,

Оценка

RSolve[{T[0] == 2, T[n] == T[n-1] + 2}, T[n], n]

возвращает

{{T[n] -> 2 (1 + n)}}

Например, он может также найти замкнутую форму n-го числа Фибоначчи:

RSolve[{F[1] == 1, F[2] == 1, F[n] == F[n-1] + F[n-2]}, F[n], n] //FunctionExpand

возвращает

{{F[n] -> (((1 + Sqrt[5])/2)^n - (2/(1 + Sqrt[5]))^n*Cos[n*Pi])/Sqrt[5]}}

Answer 7

Я бы решил это следующим образом:

Assume that T(n) = a*n + b for some a and b.
T(0) = 2. So a * 0 + b = 2, thus b = 2.

T(n) = T(n-1) + 2, so 
a * n + b = (a * (n-1) + b) + 2 consequently
a * n + b = a * n - a + b + 2 and
0 = - a + 2, thus a = 2.

So we have T(n) = 2 * n + 2 = 2 (n+1).