Fibonacci

Berekeningsmethoden (deel 3)

We zoeken uitdrukkingen voor sommen van machten van Fibonaccigetallen, dus voor
g_1,n = F₁ + F₂ + F₃ + ... + F_n
g_2,n = F₁² + F₂² + F₃² + ... + F_n²
g_3,n = F₁³ + F₂³ + F₃³ + ... + F_n³
enz.

We hebben in deel 1 en deel 2 al enkele methoden besproken waarmee korte uitdrukkingen voor g_1,n en g_2,n kunnen worden gevonden.
Een formule vinden voor g_3,n wordt een stuk lastiger. We zullen het bepalen van g_k,n voor k=3,4,5,... wat systematischer aan moeten pakken.
Definieer voor k>=0:   f_k,n(x) = (F₀)^k + (F₁)^kx + (F₂)^kx² + (F₃)^k x³ + ... + (F_n)^k xⁿ.
Dan is voor k>0:    g_k,n = f_k,n(1).
Een extra voordeel van het vinden van een uitdrukking voor f_k,n(x) is, dat we nog wat meer formules hieruit kunnen afleiden, die anders zeer lastiger te vinden of te bewijzen zijn. Zo is bijvoorbeeld
F₁ + 2F₂ + 3F₃ + ... + nF_n = f'_k,n(1).

We weten dat:
(r - s)F_m = r^m - s^m, waarbij r = (1 + 5)/2 en s = (1 - 5)/2.
Dus geldt voor 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ⁿ
= {{Vervang (r - s)F₀ door r⁰ - s⁰, (r - s)F₁ door r¹ - s¹, enz.}}
(r⁰-s⁰)(F₀)^k-1 + (r¹-s¹)(F₁)^k-1x + (r²-s²)(F₂)^k-1x² + ... + (rⁿ-sⁿ)(F_n)^k-1xⁿ =
{{splits naar machten van r en 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 hebben nu de relatie (r-s)f_k+1,n(x) = f_k,n(rx) - f_k,n(sx).
Als we een uitdrukking kunnen vinden voor f_0,n(x), dan kunnen we met deze relatie een uitdrukking vinden voor f_k,n(x), voor elke k>0, en dus voor g_k,n.

Nu is f_0,n(x) = 1 + x + x² + x³ + ... + xⁿ en
(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ⁿ⁺¹
en dus als x ongelijk aan 1 is geldt f_0,n(x) =
(1 - xⁿ⁺¹)/(1 - x).

We willen g_3,n bepalen.
5g_3,n =
(r-s)g_3,n =
(r-s)f_3,n(1) =
f_2,n(r) - f_2,n(s).

Dan is 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²).

Dan is 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², dus 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).
Dus g_3,n = (5 + F_3n+2 - 6(-1)ⁿF_n-1)/10.