Ciąg Fibonacciego

[Kocurka]

Wykaż, że każda liczba naturalna może być przedstawiona jako skończona suma elementów ciągu Fibonacciego, w której każdy element występuje nie więcej niż jeden raz.

Będę bardzo wdzięczna za pomoc.

[Sylwek]

Było już.

Indukcją, sprawdź coś małego w ramach założenia, w kroku robimy coś takiego: niech \(\displaystyle{ F_i}\) będzie takim wyrazem ciągu Fibonacciego, że: \(\displaystyle{ F_i \le n+1 < F_{i+1}}\), wówczas: \(\displaystyle{ n+1-F_i}\) z założenia da się przedstawić we wskazany sposób. Musisz tylko pokazać, że ta liczba jest mniejsza od \(\displaystyle{ F_i}\), zatem \(\displaystyle{ n+1}\) jest sumą \(\displaystyle{ F_i}\) oraz grupy różnych wyrazów ciągu Fibonacciego mniejszych od \(\displaystyle{ F_i}\), czyli może być przedstawiona jako skończona suma elementów ciągu Fibonacciego, w której każdy element występuje co najwyżej raz.

[Kocurka]

Mógłbyś mi to jakoś rozpisać, jak to ma dokładniej wyglądać? bo ja jakoś dalej tego nie widzę, a bardzo mi na tym zależy. Z góry dziękuję.

[Sylwek]

1. Dla każdej liczby nie większej niż n działa (to założenie indukcyjne, sprawdzić wystarczy dla n=1).

2. Niech \(\displaystyle{ F_i}\) będzie takim wyrazem ciągu Fibonacciego, że: \(\displaystyle{ 1 \le F_i \le n+1 < F_{i+1}}\) (ponieważ \(\displaystyle{ n \ge 2}\), to \(\displaystyle{ F_i \ge 2}\), to pociąga za sobą: \(\displaystyle{ F_{i-1}<F_i}\) - przyda się później), oczywiście istnieje dokładnie jeden taki wyraz \(\displaystyle{ F_i}\).

3. Wówczas: \(\displaystyle{ k=n+1-F_i \le n+1-1=n}\) - zatem \(\displaystyle{ k \le n}\), czyli jest liczbą nie większą niż n. Zatem z założenia da się przedstawić we wskazany sposób.

Pokażmy, że: \(\displaystyle{ k < F_i}\). Z założeń przyjętych w podpunkcie 2. mamy: \(\displaystyle{ k=(n+1)-F_i < F_{i+1}-F_i = F_{i-1} < F_i}\). Zatem k jest:
* z założenia sumą różnych wyrazów ciągu Fibonacciego
* mniejsza od \(\displaystyle{ F_i}\)

4. Podsumowując k jest sumą różnych wyrazów ciągu Fibonacciego mniejszych od \(\displaystyle{ F_i}\).

5. \(\displaystyle{ k=n+1-F_i \iff (n+1)=k + F_i}\) - z wcześniejszych wniosków po prawej stronie mamy sumę dwóch wyrażeń:
* sumy różnych wyrazów ciągu Fibonacciego mniejszych od \(\displaystyle{ F_i}\)
* \(\displaystyle{ F_i}\)

6. Zatem prawa strona również jest sumą różnych wyrazów ciągu Fibonacciego, co kończy dowód indukcyjny.

Jaśniej nie umiem.

[Kocurka]

Bardzo dziękuję za pomoc, ale mam jeszcze pytanie może ktoś zna dowód tego samego twierdzenia z wykorzystaniem tożsamości: \(\displaystyle{ f_{1}+f_{3}+...+f_{2n-1}=f_{2n}}\)
\(\displaystyle{ f_{2}+f_{4}+...+f_{2n}=f_{2n+1}-1}\)
i znowu jest to bardzo ważne, więc będę wdzięczna za pomoc.