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čí. )
Další hint: Důkaz z předešlého hintu nám dokazuje, že h(fn) ≥ n − 2, takže je potřeba ještě
ukázat h(fn) ≤ n − 2. Toho lze určitě dosáhnout vícero způsoby. Já bych rovnou dokázal, že pro
všechna a, b ∈ N taková, že fn ≥ a > b, má Euclidův algoritmus pro NSD(a, b) nanejvýš n − 2
kroků. (Využije se silná indukce.)
Poznámka. Pro ilustraci problému ukážeme průběh Euklidova algoritmu pro NSD(f6, f5).
1. krok 8 = 1 · 5 + 3 (f6 = f5 + f4)
2. krok 5 = 1 · 3 + 2 (f5 = f4 + f3)
3. krok 3 = 1 · 2 + 1 (f4 = f3 + f2)
4. krok 2 = 2 · 1 + 0 (f3 = 2 · f2) → Konec algoritmu
Řešení. Nejprve dokážeme h(fn) ≥ n − 2, k tomu nám stačí ukázat, že Euklidův algoritmus
pro NSD(fn, fn−1) má n − 2 kroků. To nám totiž říká, že existuje nějaké b ∈ N, b < fn takové,
že Euclidův algoritmus pro NSD(fn, b) má n − 2 kroků.
• Pro n = 3 počítáme NSD(2, 1) a Euclidův algoritmus (EA) má tento průběh:
1. krok 2 = 2 · 1 + 0 → Konec algoritmu
• Předpokládejme, že máme tvrzení dokázané pro nějaké k ∈ N, k > 3 (tzv. indukční
předpoklad). Ukážeme, že z toho plyne platnost tvrzení i pro k + 1. Protože fk+1 − fk =
fk−1 < fk, pro dělení se zbytkem
fk+1 = q · fk + r
očividně máme q = 1 a r = fk−1. To je 1. krok EA pro NSD(fk+1, fk).
Do dalšího kroku EA tedy máme jako vstupní hodnoty fk a fk−1, tedy následující kroky
jsou stejné, jako při výpočtu NSD(fk, fk−1). Z indukčního předpokladu víme, že pro k
tvrzení platí, tedy NSD(fk, fk−1) spočítáme v k − 2 krocích.
Dohromady tedy NSD(fk+1, fk) spočítáme v 1 + (k − 2) = (k + 1) − 2 krocích. Tvrzení
tedy platí i pro k + 1. Protože k ∈ N bylo libovolné, dokázali jsme tvrzení pro všechna
k ∈ N.
1
Nyní dokážeme, že pro všechna 2 ≤ a ≤ fn je h(a) ≤ n − 2. Tím dostaneme jako speciální
případ h(fn) ≤ n−2. Pro jednoduchost označme pk (a, b) počet kroků EA pro NSD(a, b). Podle
definice platí h(a) = max2≤b<a(pk (a, b)).
• Pro n = 3 je jediné a = f3 = 2 a h(2) = 1.
• Pro1
n = 4 máme možnosti a = 2 a a = 3. Pro oboje se snadno ukáže h(a) ≤ 2.
• Předpokládejme, že máme tvrzení dokázané pro všechna k menší než nějaké n ∈ N.
Ukážeme, že z toho plyne tvrzení i pro n. Vezměme libovolné a, b ∈ N splňující 2 ≤ a ≤ fn,
b < a. Chceme tedy ukázat, že pk (a, b) ≤ n − 2. Mohou nastat dvě možnosti:
1. b ≤ fn−1 : Označme r zbytek po dělení a číslem b, tedy pk (a, b) = 1 + pk (b, r).
Protože r < b < fn−1 (z def. dělení se zbytkem), dostáváme z indukční předpokladu
pk (a, b) = 1 + pk (b, r) ≤ 1 + (n − 3) = n − 2.
2. fn−1 < b : Označme dělení se zbytkem a = q · b + r. Protože
a − b ≤ fn − b < fn − fn−1 = fn−2,
máme q = 1 a r = a − b < fn−2. Nyní označme r zbytek po dělení b číslem r.
S využitím indukčního předpokladu dohromady dostáváme
pk (a, b) = 1 + pk (b, r) = 2 + pk (r, r ) ≤ 2 + (n − 4) = n − 2.
1
Tento případ potřebujeme dokázat zvlášť kvůli druhé možnosti indukční části důkazu.
2