algorithm - 算法和函数的泛化

Question

我承认我的数学函数有点差。
但我真的很想解开这个谜。
如何表达x(n)=x(n-1)+x(n-2)+1wheren>1和. 就函数而言where和和。 我在一些关于 AVL 树的 pdf 中找到了答案，对于高度为 n 的 AVL 树的最小节点数 nmin(n)。 x(0)=0x(1)=1
y(n)=y(n-1)+nn>1y(0)=0y(1)=1
x(n)=y(n+2)-1

请解释。

Answer 1

请更清楚您真正想要什么以及为什么（如果相关）。

你的第一个方程不是齐次的。为了使其同质化，你可以这样写：

x[n]+1 = (x[n-1]+1)+(x[n-2]+1)

并代替u[n] = x[n] + 1得到

u[n] = u[n-1]+u[n-2]与u[0] = 1, u[1]=2.

这些数字被称为斐波那契数字。关于这些数字有几个公式和结果。例如

u[n-2] = (phi^n - (-phi)^(-n)) / sqrt5和phi = (1 + sqrt 5) / 2 = 1.618...

x[n]它在你的原始方程中给出了一个公式：

(phi^(n+2) - (-phi)^(-n-2)) / sqrt5 - 1

另一方面，您的其他等式y[n] = y[n-1] + n可以重申为

y[n] = y[n-1] + n = y[n-2] + (n-1) + n = ... = 1 + 2 + ... + n

众所周知，这笔款项是y[n] = n(n+1)/2

我认为你提供的x[n]和之间没有明显的关系。y[n]