解决递归关系

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