algorithm - アルゴリズムと関数の一般化

Question

私は数学の機能が少し苦手であることを認めます。
しかし、私はこのなぞなぞを取り除くことを強く望んでいます。どこで、どの
ように表現するか。 関数の観点から、ここで、および。高さnのAVLツリーのノードの最小数nmin（n）に対するAVLツリーに関するいくつかのPDFのように 答えを見つけました。x(n)=x(n-1)+x(n-2)+1n>1x(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]。