1. domácí úloha z MIN401, jaro 2023
Zadáno: 28. 2. 2023 Odevzdejte do: 28. 3. 2023
Definice. Výškou Euclidova algoritmu h(a) čísla a ∈ N, a ≥ 2 označme největší potřebný počet
kroků Euclidova algoritmu pro výpočet NSD(a, b) ze všech čísel b ∈ N, b < a.
Poznámka. Např. h(4) = h(3) = 2. Pouze pro a = 2 platí h(a) = 1.
Definice. Fibonacciho posloupnosti {fk}∞
k=0 = {0, 1, 1, 2, 3, 5, 8, 13, 21, . . . } je posloupnost zadaná
rekurentně:
f0 := 0, f1 := 1, fn := fn−1 + fn−2 pro n ≥ 2.
Zadání. Dokažte, že pro libovolné číslo fn, n ≥ 3 z Fibonacciho posloupnosti platí:
h(fn) = n − 2.
Hint: Začněte důkazem, že Euclidův algoritmus pro NSD(fn, fn−1) má n − 2 kroků. (A taky si
uvědomte, že tento samotný fakt ještě nestačí. )
1