ciąg fibbonacciego rekurencyjnie

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
ketnasar77
Dopiero zaczynam
Dopiero zaczynam
Posty: 19
Rejestracja: 21 mar 2018, 21:39
Podziękowania: 11 razy
Płeć:

ciąg fibbonacciego rekurencyjnie

Post autor: ketnasar77 » 24 lip 2020, 18:19

Ciąg Fibonacciego zadany jest wzorem rekurencyjnym
\(f_{0}=0, f_{1}=1, f_{n+2}=f_{n+1}+f_{n} \) dla \(n \geq 0\)

Udowodnić, że dla wszystkich \(n \subseteq \mathbb{N}\)
zachodzi wzór
\(\sum_{k=0}^{n} k\cdot f_{k} = n\cdot f_{n+2} - f_{n+3} +2\)

Na razie spróbowałem indukcyjnie i doszedłem do takiego rówanania.
\(
\\
n*f_{n+2}-f_{n+3}+(n+1)*f_{n+1}=(n+1)*f_{n+3}-f_{n+4}
\)

kerajs
Fachowiec
Fachowiec
Posty: 1937
Rejestracja: 14 lis 2016, 15:38
Podziękowania: 12 razy
Otrzymane podziękowania: 832 razy
Płeć:

Re: ciąg fibbonacciego rekurencyjnie

Post autor: kerajs » 25 lip 2020, 02:12

\(\sum_{k=0}^{n+1} k\cdot f_{k} = (n+1)\cdot f_{n+3} - f_{n+4} +2\)
\(
L=\sum_{k=0}^{n+1} k\cdot f_{k}=\sum_{k=0}^{n} k\cdot f_{k}+(n+1)f_{n+1}=n f_{n+2} - f_{n+3} +2+(n+1)f_{n+1}=\\=(n+1)(f_{n+1}+f_{n+2})-f_{n+2}-f_{n+3}+2=(n+1)f_{n+3} - f_{n+4} +2=P\)


Można też bez indukcji, korzystając ze wzoru Bineta.