如何通过展开解决递归关系？

Question

如果我有T（n）= T（n-1）+ T（n-2）+ cn; T（1）= T（2）= d

我如何应用展开来求解T（n）的封闭式？

[当我尝试通过替代展开它时，我的方程式变得很长，很难追踪。

Answer 1

您可以使用Python的符号数学库sympy来写出术语。

sympy

这给：

from sympy.abc import c, d

def T(n):
    if n <= 0:
        return None
    elif n <= 2:
        return d
    else:
        return T(n-1) + T(n-2) + c*n

for i in range(1, 12):
    print(i, T(i))

1 d
2 d
3 3*c + 2*d
4 7*c + 3*d
5 15*c + 5*d
6 28*c + 8*d
7 50*c + 13*d
8 86*c + 21*d
9 145*c + 34*d
10 241*c + 55*d
11 397*c + 89*d

的系数显然是斐波那契数。可以在导致d的c中查找oeis的系数。这给出了一个很长的明确公式，还有A023552。

或者，您可以尝试Fibonacci(n+2) + 2*Fibonacci(n) - (n+3)得到一个明确的公式：

Sympy's rsolve

哪个输出：

rsolve

不幸的是，这似乎是错误的。