函數的算法和泛化

Question

我承認我在數學中的功能有點差。
但我真的迫切希望得到這個謎語。
如何表示x(n)=x(n-1)+x(n-2)+1其中n>1和x(0)=0和x(1)=1。
根據函數y(n)=y(n-1)+n其中n>1和y(0)=0和y(1)=1。
我找到答案爲x(n)=y(n+2)-1在關於AVL樹的最小數量的節點nmin（n）的高度爲n的AVL樹的一些pdf。

請解釋。

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。

這些數字被稱爲Fibonacci Numbers。有幾個關於這些數字的公式和結果。例如

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]之間沒有明顯的關係。