Fibonacciho rozvoj

Úloha číslo: 3296

Dokažte, že každé přirozené číslo \(n\) lze jednoznačně napsat jako součet různých Fibonacciho čísel takových, že v součtu nejsou žádná dvě po sobě jdoucí Fibonacciho čísla.

Formálně: \(n\) lze jednoznačně napsat ve tvaru \(\displaystyle n=\sum_{j=1}^{k}F_{i_j},\) kde \(i_1\ge 2\) a pro každé \(j \in \{1, 2, …, k-1\}\) je \(i_{j+1}\ge i_j + 2\).

  • Řešení

    Dokazujeme indukcí podle \(n\). Pro \(n=1\) máme \(1=F_2\).

    Indukční krok \(n \to n+1\): Podle indukčního předpokladu pro \(n\) existují \(i_1,…,i_k\) taková, že \(\displaystyle n=\sum_{j=1}^{k}F_{i_j},\). Potom \(\displaystyle n+1=1+\sum_{j=1}^{k}F_{i_j}\).

    • pokud \(i_1\ge 4\), zapíšeme 1 jako \(F_2=F_{i_0}\), a pak už jen posuneme číslování indexů
    • pokud \(i_1=3\), zapíšeme 1 jako \(F_2=F_{i_0}\), a pak ještě řadu upravíme, jak popíšeme níže
    • pokud \(i_1=2\), zapíšeme 1 jako \(F_1=F_{i_0}\), a řadu také upravíme

    Na začátku úprav řada obdahuje jen jednu dvojici po sobě jdoucích Fibonacciho čísel. Je-li tato dvojice ve tvaru \(F_{i_j}\), \(F_{i_{j+1}}\), kde \(i_{j+1}=i_j+1\), zaměníme tyto dva sčítance za \(F_{i_j+2}\). Tím jednu dvojici po sobě jdoucích Fibonacciho čísel eliminujeme a nejvýše jedna vznikne, to pokud \(i_{j+2}=i_j+3\).

    Protože je řada konečná a po sobě jdoucí dvojice jsou tvořeny stále většími Fibonacciho čísly, tento proces úprav po konečně mnoha krocích skončí.

Obtížnost: Středně těžká úloha
Úloha vyžadující neobvyklý trik nebo nápad
En translation
	Zaslat komentář k úloze