5   Rekurze a induktivní definice
Mimo „přímočarých" definic množin a funkcí, jako výčtem prvků či explicitním zadáním, se obzvláště v informatice setkáváme s definicemi nepřímými, které se odvolávají na sebe sama.
Odborně se taková situace nazývá rekurzí a induktivní definicí. □
Stručný přehled lekce
* Posloupnosti a rekurentní vztahy pro ně, jejich řešení a důkazy.
* Rekurze za přítomnosti více parametrů a použití indukce.
* Induktivní definice množin s ukázkami.
Petr Hliněný, Fl MU Brno, 2024
1/20
Fl: IB000: Rekurze a induktivní definice
^5.1   Posloupnosti a rekurentní vztahy
• Uspořádané fc-tice z daného oboru hodnot H jsou nazývány konečnými posloupnostmi délky k (nad H).
• Pojem posloupnosti zobecňuje toto pojetí na „nekonečnou délku" takto:
Definice 5.1. Posloupnost (nekonečná) je zobrazením z přirozených čísel N do oboru hodnot H, neboli
p : N -> H.
Místo „funkčního" zápisu n-tého členu posloupnosti jako p(n) častěji používáme „indexovou" formu jako pn, ve které se celá posloupnost zapíše (pn)neN-c
Oborem hodnot H posloupnosti obvykle bývá nějaká číselná množina, ale může to být i jakákoliv jiná množina. □
Poznámka: Třebaže to není zcela formálně přesné, běžně se setkáme s posloupnostmi
indexovanými od nuly nebo od jedničky, jak se to v aplikacích hodí.
I my se budeme tímto řídit a vždy si určíme počáteční index podle potřeby.
Petr Hliněný, Fl MU Brno, 2024
2/20
Fl: IB000: Rekurze a induktivní definice
^Příklady posloupností
• po — 0, pi = 2,... ,pi = 2i,... je posloupnost sudých nezáporných čísel,c
• (3, 3.1, 3.14, 3.141,...) je posl. postupných dekadických rozvojů 7r,c
• třeba (jablko, hruška, švestka, hruška, hruška,...) je posloupnost nad druhy ovoce coby oborem hodnot.c
• (1, —1, 1, —1,...) je posloupnost určená vztahem pi = (—l)z, i > 0,
• avšak pokud bychom chtěli stejnou posloupnost (1, —1, 1, —1,...) určit indexy od jedné, tj. zadat ji jako g^, i > 1, tak vztah bude qi — (—1)2_1.
Definice: Posloupnost (pn)ne^ Je
* rostoucí pokud pn+i > Pn a nerostoucí pokud pn+i ^ Pn>
* klesající pokud pn+i < Pn a neklesající pokud pn+i > Pn
platí pro všechna n.
Petr Hliněný, Fl MU Brno, 2024
3/20
Fl: IB000: Rekurze a induktivní definice
^Rekurentní zadání posloupnosti
Definice: Říkáme, že posloupnost (pn)n^ je zadána rekurentně, pokud je dán její počáteční člen po (či několik počátečních členů) a dále máme předpis, jak určit hodnotu členu        z hodnot     pro nějaká i < n.
Ukázky rekurentně zadaných posloupností:
• Zadáme-li posloupnost pn počátečním členem po = 1 a rekurentním vztahem        = 2pn pro n > 0, pak platí pn = 2n pro všechna n.
• Funkce „faktoriál" (na přirozených číslech) je dána počáteční hodnotou 0! = 1 a rekurentním vztahem (n + 1)! = (n + 1) • n\ pro n > 0.
• Známá Fibonacciho posloupnost je zadaná počátečními členy f1 = f2 = l a vztahem fn+2 = fn+i + fn pro n > 1. □
Všimněte si v poslední ukázce, že není potřeba doslova dodržovat formu rekurentního vztahu „pn+i z hodnot pi \ ale vždy je třeba hodnotu následujícího členu posloupnosti odvozovat z předchozích (tj. už určených) členů, v tom případě z hodnot /j, i = n, n + 1".
Petr Hliněný, Fl MU Brno, 2024
4/20
Fl: IB000: Rekurze a induktivní definice
T-
Řešení rekurentní posloupnosti
Příklad 5.2. Posloupnost f : N —> 7L je zadaná rekurentní definicí
/(O) =3    a    /(n + l)=2-/(n) + l
pro všechna přirozená n. Určete hodnotu f(n) vzorcem v závislosti na n.
Řešení: V první fázi řešení takového příkladu musíme nějak „uhodnout" hledaný vzorec pro f(n). Jak? Zkusíme vypočítat několik prvních hodnot a uvidíme... [
/(l) = 2./(0) + l = 2.3 + l = 7
f (2) = 2-/(1)+ 1 = 2-7 + 1 = 15
/(3) = 2-/(2)+ 1 = 2-15 + 1 = 31
/(4) = 2 • /(3) + 1 = 2 • 31 + 1 = 63
Nepřipomínají nám tato čísla něco? Co třeba výrazy 8 — 1, 16 — 1, 32 — 1, 64 — 1... ? Bystrým studentům se již asi podařilo uhodnout (a ostatním napovídáme), že jde o mocniny dvou snížené o 1. Přesněji, f (ji) = 2ri+2 — 1.
Ve druhé fázi nesmíme ale zapomenout správnost našeho „věštění" dokázat, nejlépe matematickou indukcí podle n. □
Petr Hliněný, Fl MU Brno, 2024
5/20
Fl: IB000: Rekurze a induktivní definice
/(O) =3    a    /(n + 1) = 2 • /(n) + 1
pro všechna přirozená n. Určete hodnotu f (n) vzorcem v závislosti na n. Rešení: ...
Bystrým studentům se již asi podařilo uhodnout (a ostatním napovídáme), že jde o mocniny dvou snížené o 1. Přesněji, f(n) = 2ri+2 — 1.
Ve druhé fázi nesmíme ale zapomenout správnost našeho „věštění" dokázat, nejlépe matematickou indukcí podle n.
• Báze pro n := 0 říká /(O) = 2°+2 -1=4-1 = 3 = /(O), což platí. □
• Indukční krok využije indukční předpoklad platnosti vztahu f(n) = 2n+2 — 1 pro n := i (tj. f (i) = 22+2 — 1)   a pokračuje úpravou ze zadaného rekurentního vzorce
f (i + 1) = 2 • /(i) + 1 = 2- (2i+2 - 1) + 1 = 2 • 2i+2 - 2 + 1 = 2(i+1)+2 - 1, což po dosazení pro n := i + 1 znamená opět požadovaný vztah /(n) = 2n+2 — lx
Podle principu matematické indukce je nyní dokázáno, že pro zadanou rekurentní posloupnost / platí f(n) = 2n+2 — 1 pro všechna přirozená n. □
Petr Hliněný, Fl MU Brno, 2024
6/20
Fl: IB000: Rekurze a induktivní definice
Příklad 5.3. Posloupnost (<sn)neN je zadaná rekurentní definicí
sq = O    a    sn = sn-i + n2
pro všechna n > 1.   Dokažte, že sn = |n(n + l)(2n + 1) pro všechna přirozená n.
v
Řešení: Opět postupujeme matematickou indukcí podle n.
• Báze n := 0: s0 = ± • 0 • (0 + 1)(2 • 0 + 1) = 0, což platí.
• Indukční krok: za využití sť_i = ±(i -      - 1 + l)(2i - 2 +1) = ±(i - l)i(2i - 1), což je indukční předpoklad pro n := i — 1 a libovolné i > 1, upravujeme
1 1
Si = Si-! + i2 = -(i - l)i(2i - 1) + i2 = -i (2i2 - 3i + 1) + i2
6 6
=     (2i2 - 3i + 1 + 6i) =       + l)(2i + 1), o o
což dokazuje požadovaný vztah sn = |n(n + l)(2n + 1) také pro n := i. □ Poznámka: Výsledek Příkladu 5.3 je ukázkou tzv. sumačního vzorce pro řadu
l2 + 22 + • • • + n2 = -
ra(ra + l)(2n + 1).
Jinou ukázkou je už dříve zmíněný základní vztah 1 + 2 + • • • + n
\n(n + 1).
Petr Hliněný, Fl MU Brno, 2024
7/20
Fl: IB000: Rekurze a induktivní definice
5.2   Rekurze s více parametry a indukce
• Kromě přímočarých ukázek rekurze na funkcích s jediným celočíselným parametrem (tj. na posloupnostech) se lze setkat, především v návrhu algoritmů, s rekurzí za přítomnosti více parametrů.
• I pro takové obecnější případy je základním matematickým přístupem použít indukci, avšak nejprve je nutno vhodně zvolit či vytvořit jeden celočíselný parametr, podle nějž indukci můžeme vést.
• Samozřejmě takový parametr (i nově vytvořený) opět musí být zdola ohraničený a pro každou rekurentně odkazovanou hodnotu musí být nižší než pro aktuálně určovanou hodnotu.
Možné přístupy k věci si uvedeme na několika typických ukázkách.
Petr Hliněný, Fl MU Brno, 2024
8/20
Fl: IB000: Rekurze a induktivní definice
^Přístup fixace parametru
Příklad 5.4. Mějme funkci m : N x N —> N definovanou rekurentně takto: i
• m(0, b) = O pro všechna b G N a
• m(a + 1,6)= m(a, 6) + 6 pro všechna a, 6 G N.
c Co 6ívc/e hodnotou m(a, 6) pro obecné a, 6 G N? □
Bližším pohledem na zadanou definici zjistíme, že hloubka zanoření rekurze pro vyčíslení m(a, 6) je přesně a. Jelikož každé zanoření k výsledku přičte hodnotu 6, odhadneme:
Věta. Pro každá a, 6 G N platí m(a, 6) — a-b (součin daných parametrů).
Jaký je vhodný postup k důkazu tohoto tvrzení indukcí? Je snadno vidět, že rekurentní vyhodnocení na hodnotě parametru b nijak podstatně nezáleží (b lze fixovat) a důležité je sledovat měnící se hodnotu a. Tato úvaha nás dovede k následujícímu přístupu:
Petr Hliněný, Fl MU Brno, 2024
9/20
Fl: IB000: Rekurze a induktivní definice
T
Mějme m : N x N -> N:
* m(0, 6) = O pro všechna 6 G N a
* m(a + 1,6)= m(a, 6) + 6 pro všechna a, 6 G N.
Věta. Pro každá a, 6 G N platí m(a, 6) — a-b (součin daných parametrů).
Důkaz: Budiž b G N libovolné ale pro další úvahy pevné.
Dokazujeme tady, že pro každou hodnotu a \— i G N platí m(i, b) — i - b.
• V bázi i = 0 je explicitně zadáno m(0, 6) = 0 = 0 • b pro jakékoliv b G N. □
• Indukční krok. Nechť je tvrzení známo pro a — i G N a uvažme hodnotu parametru a \— i + 1. Podle zadání pak platí m[i + 1,6)= m(i, 6) + 6. Podle indukčního předpokladu již víme, že m(i,6) — i • b.   Zbývá jen uvedené poznatky správně zřetězit
m(a, 6) — m(i + 1,6)= m(i, 6) + 6 = i- 6 + 6=   (z + 1) • 6 = a • 6.
Důkaz matematickou indukcí je tímto zdárně ukončen.
Petr Hliněný, Fl MU Brno, 2024
10/20
Fl: IB000: Rekurze a induktivní definice
Indukce k součtu parametrů
Příklad 5.5. Mějme funkci k : N x N —> N definovanou rekurentně takto: i
• fc(c, 0) = fc(0, c) = 1 pro všechna c G N a
• fc(m, n) = fc(m, n — 1) + fc(m — 1, n) pro všechna m, n G N, m, n > 0. :Co        hodnotou fc(m, n) pro obecné m, n G N? t
Studenti znalí takzvaného Pascalova trojúhelníka už mohou tušit, že výsledek souvisí s počtem podmnožin a tedy kombinačními čísly. □
My si zde správnou odpověď nejen ukážeme, ale i přesně dokážeme:
Věta. Pro každé m,n G N je hodnota k{m,n) rovna počtu všech m-prvkových podmnožin (m + n)-prvkové množiny, tedy jinými slovy roven
známému kombinačnímu číslu fc(m, n)
Petr Hliněný, Fl MU Brno, 2024
11/20
Fl: IB000: Rekurze a induktivní definice
* k(c, 0) = k(0, c) = 1 pro všechna c G N a
* fc(ra, n) = fc(ra, n — 1) + k(m — 1, n) pro všechna ra, n G N, ra, n > 0. Věta. Pro každé ra, n G N je hodnota fc(ra, n) rovna počtu všech ra-
Důkaz indukcí vzhledem k součtu parametrů i = m + n:
• Báze i = ra + n = 0 pro ra, n G N znamená, že ra = n = 0. Zde však s výhodou využijeme tzv. „rozšíření báze" na všechny hraniční případy ra = 0 nebo n = 0 naší rekurze.
V obou rozšířených případech je přímo zadáno fc(ra, 0) = fc(0, n) = 1. Je toto platná odpověď? □
* Kolik je prázdných podmnožin (ra = 0) jakékoliv množiny? Jedna, 0.
* Kolik je ra-prvkových podmnožin ra-prvkové (n = 0) množiny? Zase jedna, ta množina samotná.
Tím je důkaz rozšířené báze indukce dokončen.
□
Petr Hliněný, Fl MU Brno, 2024
12/20
Fl: IB000: Rekurze a induktivní definice
* k(c, 0) = k(0, c) = 1 pro všechna c G N a
* fc(ra, n) = fc(ra, n — 1) + fc(ra — 1, n) pro všechna m, n G N, m, n > 0.
• Indukční krok přechází na součet i + 1 = m + n. nNavíc díky předchozímu rozšírení báze se rovnou můžeme omezit na případy m, n > 0.
Platí tedy podle zadání fc(ra, n) — k{m,n — 1) + k(m — Přitom oba rekurentní odkazy fc(m, n — 1) i k(m — 1, n) se vztahují na případy se součtem obou parametrů rovným m — 1 + n — m + n — 1 — i.
Podle indukčního předpokladu tudíž platí, že k{m,n — 1) je počtem m-prvkových podmnožin i-prvkové množiny a k{m — l,n) je počtem (m —1)-prvkových podmnožin i-prvkové množiny, třeba množiny M — {1, 2,... , á}.
Kolik je m-prvkových podmn. (i +l)-prvkové množiny M7 = M U {i + 1}? Pokud ze všech těchto podmnožin odebereme prvek       dostaneme právěc
* m-prvkové podmnožiny (z těch neobsahujících prvek i + 1) plus
* (m — l)-prvkové podmnožiny (z těch původně obsahujících i + 1).
A to je v součtu rovno právě k(m — 1, n) + fc(m, n — 1) = fc(m, n). rn
Petr Hliněný, Fl MU Brno, 2024
13/20
Fl: IB000: Rekurze a induktivní definice
^Přístup se zesílením dokazovaného tvrzení
Příklad 5.6. Zjistěte, jakou hodnotu v závislosti na celočíselném parametru a nabývá funkce t (a, 1), která je rekurentně definována takto: i
• t(0, b) = 0 pro všechna b £ N a
• t(a, b) = t(a — 1, 26) + b pro všechna a, b £ N, a > 0.
Zkusíme-li si ručně vypočítat několik prvních požadovaných hodnot t(a, 1) pro a = 0,1, 2, 3,4... , postupně získáme výsledky rovné 0,1, 3, 7,15 ... (všimněte si také, jak se v rekurzivním rozvoji postupně sčítají mocniny dvou). nNa základě toho již není obtížné uhodnout, že návratová hodnota patrně bude obecně určena vztahem 2a — 1.
Toto je však třeba také dokázat. □
Jak záhy zjistíme, matematická indukce na naše tvrzení přímo „nezabírá", ale mnohem lépe se nám povede s následujícím přirozeným zesílením dokazovaného tvrzení, které zobecňuje výsledek na proměnné hodnoty parametru b v návaznosti na zadaný rekurentní vztah.
Petr Hliněný, Fl MU Brno, 2024
14/20
Fl: IB000: Rekurze a induktivní definice
* t(0, b) = O pro všechna b G N a
* t(a, b) = t (a — 1, 26) + b pro všechna a, 6 G N, a > 0.
Věta. Pro každé a, 6 G N platí í(a, 6) = (2a - 1) • 6. Důkaz: Postupujeme indukcí podle a := i G N.
* V bázi pro a = i = 0 je určena hodnota t(a, 6) = 0 = (2° — 1) • b.n
* Indukční krok. Nechť je tvrzení známo pro a = i G N a uvažujme další hodnotu a := i + 1 > 0. □V tom případě je rekurentní podmínkou dáno t(a, b) = t(a — 1, 26) + b, přičemž hodnota t(a — 1, 26) = 26) vyplývá z dosazeného a = i + 1 a indukčního předpokladu. Celkově tedy i
r(a, 6) = í(i, 26) + 6 = (2* - 1) • 26 + 6  = 2i+16 - 26 + 6 = (2i+1 - 1) • 6.
Poslední výraz je roven požadovanému (2a — 1) • 6.
□
Petr Hliněný, Fl MU Brno, 2024
15/20
Fl: IB000: Rekurze a induktivní definice
^5.3   Induktivní definice množin
Širokým zobecněním rekurentních definic posloupností je následující koncept. Definice 5.7. Induktivní definice množiny.
Jedná se obecně o popis (nějaké) množiny M v následujícím tvaru:
• Je dáno několik pevných {bázických) prvků ai, a2,..., a& G M.
• Je dán soubor induktivních pravidel typu
Jsou-li (libovolné prvky) xi,... ,xt G M, pak také y G M. V tomto případě je y typicky funkcí y = fi(xi,... , x$) (v pravidle číslo i).
Pak naše induktivně definovaná množina M je určena jako nejmenší (inkluzí) množina vyhovující všem těmto pravidlům.
Petr Hliněný, Fl MU Brno, 2024
16/20
Fl: IB000: Rekurze a induktivní definice
T
Několik jednoduchých ukázek. ..
• Pro nejbližší příklad induktivní definice se obrátíme na množinu všech přirozených čísel, která je formálně zavedena následovně.
- 0 G N
- Je-li i G N, pak také succ(i) G N (kde následník succ(i) odpovídá
Pro každé y G N můžeme definovat jinou množinu My C N induktivně:
- y e My
- Jestliže x G My a x + 1 je liché, pak x + 2 G My. □ Pak například M3 = {3}, nebo M4 = {4 + 2i | i G N}. □
Dalším příkladem induktivní definice je už známé zavedení výrokových formulí z Oddílu 1.4. Uměli byste teď přesněji říci, co tam byly bázické prvky a jaká byla induktivní pravidla? A jaká byla v definici formulí role závorek?
Petr Hliněný, Fl MU Brno, 2024
17/20
Fl: IB000: Rekurze a induktivní definice
^Pokročilý ilustrační příklad
. .. zase na induktivní definici.
Příklad 5.8. V Růžovém království majízvláštní peníze - používají mince pouze dvou hodnot, tríkoruny a třináctikoruny.
a) Určete induktivní definici množiny P všech celých kladných čísel, které lze jak peněžní částku složit z mincí v Růžovém království (Uvažujte, že království má k dispozici neomezené množství mincí) i
b) Dokažte, že z mincí v Růžovém království lze složit jakoukoliv celou částku od 24 korun výše.
c) Chytrý Honza přijel do Růžového království a potřebuje si tam koupit jeden knoflík za korunu. Jak to může udělat a neprodělat?
Petr Hliněný, Fl MU Brno, 2024
18/20
Fl: IB000: Rekurze a induktivní definice
a) Určete induktivní definici množiny P všech celých kladných čísel, které lze jak peněžní částku složit z mincí v Růžovém království (Uvažujte, že království má k dispozici neomezené množství mincí) i
Například takto: Bazickými prvky jsou 3 G P a 13 G P.
K tomu přináleží dvě induktivní pravidla;
je-li a G P, pak a + 3 G P a také a + 13 G P. □
b) Dokažte, že z mincí v Růžovém království lze složit jakoukoliv celou částku od 24 korun výše.
V řešení úkolu postačí dokázat toto tvrzení matematickou indukcí:
Věta. Platí-li pro nějaké n > 24, že 24, 25,... , n, n + 1, n + 2 G P, pak také n + 3 G P. □
Důkaz: V bázi indukce snadno vidíme, že částky 24 = 3 • 8, 25 = 13 + 3 • 4 a 26 = 13 • 2 náleží do P, a proto tvrzení platí pro n = 24.
V indukčním kroku z předpokladu n G P přímo odvodíme n + 3 G P (přidáme jednu tříkorunu) a jsme hotovi.
Petr Hliněný, Fl MU Brno, 2024
19/20
Fl: IB000: Rekurze a induktivní definice
j"" c) Chytrý Honza přijel do Ružového království a potřebuje si tam koupit jeden knoflík za korunu. Jak to může udělat a neprodělat?
□
Honza zaplatí 1 třinácti korun u a nechá si vrátit 4 tříkoruny (12). □
□
A na závěr jeden bonusový pro samostatné přemýšlení
Příklad 5.9. Jak byste dokázali jasně a srozumitelně (explicitně) popsat množinu D zadanou následující induktivní definici? t
• Bázickými prvky jsou 21 G D a 35 G D.
• Máme dvě induktivní pravidla:
* Jsou-li a, b G D (je možné a — h), pak také a + b G D.
* Jsou-li a, b G D a platia > b, pak také a — b G D. □
Pokud už máte odpověď, pak přemýšlejte, co se stane, když bázickými prvky bude jiná dvojice přirozených čísel.
A co když v bázi zadáme trojici nebo čtveřici čísel? □
Petr Hliněný, FI MU Brno, 2024 20/20 Fl: IB000: Rekurze a induktivní definice