Fibonacci

Einige Berechnungsmethoden (3. Teil)

Wir suchen Ausdrücke für Summen von Potenzen von Fibonaccizahlen, also für
g_1,n = F₁ + F₂ + F₃ + ... + F_n
g_2,n = F₁² + F₂² + F₃² + ... + F_n²
g_3,n = F₁³ + F₂³ + F₃³ + ... + F_n³
usw.

Wir haben im ersten und zweiten Teil schon einige Methoden besprochen wobei kurze Ausdrücke für g_1,n und g_2,n gefunden werden können.
Eine Formel für g_3,n finden wird schwieger sein. Wir werden eine systematische Methode besprechen um Ausdrücke für g_k,n zu finden (k=3,4,5,...).
Definiere für k>=0:   f_k,n(x) = (F₀)^k + (F₁)^kx + (F₂)^kx² + (F₃)^k x³ + ... + (F_n)^k xⁿ.
Dann ist für k>0:    g_k,n = f_k,n(1).
Wenn wir einen Ausdruck für f_k,n(x) gefunden haben, dann können wir hiermit zahlreiche Formeln ableiten, die sonst sehr schwierig zu finden oder zu beweisen sind. So ist z.B.
F₁ + 2F₂ + 3F₃ + ... + nF_n = f'_k,n(1).

Wir wissen dass:
(r - s)F_m = r^m - s^m, waarbei r = (1 + 5)/2 und s = (1 - 5)/2.
Also gilt für k>0:
(r-s)f_k,n(x) = (r-s)F₀(F₀)^k-1 + (r-s)F₁(F₁)^k-1x + (r-s)F₂(F₂)^k-1x² + (r-s)F₃(F₃)^k-1x³ + ... + (r-s)F_n(F_n)^k-1 xⁿ
= {{Ersetze (r - s)F₀ durch r⁰ - s⁰, (r - s)F₁ durch r¹ - s¹, usw.}}
(r⁰-s⁰)(F₀)^k-1 + (r¹-s¹)(F₁)^k-1x + (r²-s²)(F₂)^k-1x² + ... + (rⁿ-sⁿ)(F_n)^k-1xⁿ =
{{trenne die Potenzen von r und s}}
=(F₀)^k-1r⁰ + (F₁)^k-1r¹x + (F₂)^k-1r²x² + ... + (F_n)^k-1rⁿxⁿ
- ((F₀)^k-1s⁰ + (F₁)^k-1s¹x + (F₂)^k-1s²x² + ... + (F_n)^k-1sⁿxⁿ) =
(F₀)^k-1 + (F₁)^k-1(rx) + (F₂)^k-1(rx)² + ... + (F_n)^k-1(rx)ⁿ
- ((F₀)^k-1 + (F₁)^k-1(sx) + (F₂)^k-1(sx)² + ... + (F_n)^k-1(sx)ⁿ) =
f_k-1,n(rx) - f_k-1,n(sx).

We haben nun die Formel (r-s)f_k+1,n(x) = f_k,n(rx) - f_k,n(sx).
Wenn wir einen Ausdruck für f_0,n(x) finden können, dann können wir mit dieser Formel einen Ausdruck für f_k,n(x) finden, für jedes k>0, und deshalb für g_k,n.

Nun ist f_0,n(x) = 1 + x + x² + x³ + ... + xⁿ und
(1 - x)f_0,n(x) = f_0,n(x) - xf_0,n(x) =
(1 + x + x² + x³ + ... + xⁿ) - x - x² - x³ - ... - xⁿ - xⁿ⁺¹ =
1 - xⁿ⁺¹
also, wenn x nicht gleich 1 ist gilt f_0,n(x) =
(1 - xⁿ⁺¹)/(1 - x).

Wir wollen g_3,n bestimmen.
5g_3,n =
(r-s)g_3,n =
(r-s)f_3,n(1) =
f_2,n(r) - f_2,n(s).

Dann ist 5g_3,n =
(r-s)f_2,n(r) - (r-s)f_2,n(s) =
(f_1,n(r.r) - f_1,n(s.r)) - (f_1,n(r.s) - f_1,n(s.s)) = {{rs = -1}} =
f_1,n(r²) - 2f_1,n(-1) + f_1,n(s²).

Dann ist 55g_3,n =
(r-s)f_1,n(r²) - 2(r-s)f_1,n(-1) + (r-s)f_1,n(s²) =
(f_0,n(r.r²) - f_0,n(s.r²)) - 2(f_0,n(-r) - f_0,n(-s)) + (f_0,n(r.s²) - f_0,n(s.s²)) = {{rs = -1}} =
(f_0,n(r³) - f_0,n(s³)) - 3(f_0,n(-r) - f_0,n(-s)) =
(1 - r³ⁿ⁺³)/(1 - r³) - (1 - s³ⁿ⁺³)/(1 - s³) - 3 (1 - (-r)ⁿ⁺¹)/(1 + r) + 3(1 - (-s)ⁿ⁺¹)/(1 + s) =
{{1 + s = s², also 1 - s³ = 1-s-s² = -2s}} =
(1 - r³ⁿ⁺³)/(-2r) - (1 - s³ⁿ⁺³)/(-2s) - 3 (1 - (-r)ⁿ⁺¹)/(r²) + 3(1 - (-s)ⁿ⁺¹)/(s²) =
(1/s-1/r)/2 +3(1/s²-1/r²) + (r³ⁿ⁺² - s³ⁿ⁺²)/2 + 3(-1)ⁿ⁺¹(r^n-1 - s^n-1) =
(r-s)(-1/2 + 3 + F_3n+2/2 + 3(-1)ⁿ⁺¹F_n-1).
Also g_3,n = (5 + F_3n+2 - 6(-1)ⁿF_n-1)/10.