解决递归关系

Question

我不确定这是否是发布此问题的正确位置，但实际上这个问题属于一个编程作业。这个递归问题我可能应该知道如何解决，但我遇到了一些麻烦。

解决递归：

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

解决方案：

T(n) = 2(n+1)

请问有人能向我展示他们是如何得出那个解决方案的吗？

请注意，解决这个特定问题并不是任务的主要部分。

- Marthin

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

- Luka Rahne

---

问题是“你如何得出这个解决方案”，而不是“我如何证明这个解决方案是正确的”。 - A. Levy

哦，我应该更加关注如何找出2、2+2、2+2+2等之间的联系和乘法。 - Luka Rahne

证明本身就是获得解决方案的方法。 - President James K. Polk

我很惊讶归纳法不是被接受的答案：http://en.wikipedia.org/wiki/Mathematical_induction - job

Answer 2

拿出 T(5)：

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

现在，计算加起来得到 T(5) 的 2 的数量。

然后尝试计算加起来得到 T(n) 的 2 的数量。

- Bart Kiers

Answer 3

尝试写出前几个值 - 然后很明显。

- Paul R

---

“看它，显而易见！”这句话在正式的论文中很少是一个合适的证明。 - Ignacio Vazquez-Abrams

@Ignacio：没错，但是一旦你面对着实际数字的序列，就会变得更容易构思出证明（至少在我看来是这样）。 - Paul R

我同意Paul R的观点，发帖者并没有要求证明，而是要求获取生成函数的方法。可以通过数学归纳等方式进行证明。 - sebastiangeiger

Answer 4

这是一个公差为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)。

无需猜测，只需将其识别为等差数列即可。

- IVlad

---

将比率更改为公差，因为比率用于几何级数，而不是等差级数。 - Aryabhatta

我很惊讶你是唯一一个为这个进展命名的人...如果它从T(6)开始，似乎会有很多人不知所措。 - Matthieu M.

Answer 5

每当n减少1时，就会增加2。这给出了一个变量项2n。由于T(0)被固定为2，因此这给出了一个常数项2。将它们相加得到2n + 2，或2(n + 1)。

- Ignacio Vazquez-Abrams

---

它在递归中减少。 - Ignacio Vazquez-Abrams

Answer 6

我会按照以下方式解决它：

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).

- Evgeny

Answer 7

这个问题很容易像其他答案所指出的那样手动解决，但是如果有用的话，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]}}

- dreeves