我不确定这是否是发布此问题的正确位置,但实际上这个问题属于一个编程作业。这个递归问题我可能应该知道如何解决,但我遇到了一些麻烦。
解决递归:
T(0) = 2;
T(n) = T(n-1) + 2;
解决方案:
T(n) = 2(n+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
拿出 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
的数量。
这是一个公差为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)
。
无需猜测,只需将其识别为等差数列即可。
T(6)
开始,似乎会有很多人不知所措。 - Matthieu M.n
减少1时,就会增加2
。这给出了一个变量项2n
。由于T(0)被固定为2
,因此这给出了一个常数项2
。将它们相加得到2n + 2
,或2(n + 1)
。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).
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]}}