Matematyka dyskretna 1/Wykład 2: Rekurencja

Definicje rekurencyjne

Definicja rekurencyjna (indukcyjna):

• nieformalnie - taka definicja, która odwołuje się do samej siebie - ale trzeba tu uważać, by odwołanie było do instancji o mniejszej komplikacji,

• zwykle chodzi o ciąg $⟨a_0,a_1,a_2,a_3,\dots ⟩$, - dla którego przepis na element $a_n$ wykorzystuje jaki(e)ś poprzedni(e) element(y): $a_{n-1},a_{n-2},\dots$ itp.,

• początkowy element (lub kilka początkowych) muszą być zadane konkretnie -

żeby było od czego zacząć,

• zwykle definicja rekurencyjna odwołuje się do jednego lub kilku poprzednich elementów, ale może też odwoływać się do wszystkich poprzednich.

Przykład

Silnia liczby $n$ (zapisywana jako $n!$) to iloczyn kolejnych liczb naturalnych od $1$ do $n$, czyli

$n!=n(n-1)\cdot \dots \cdot 2\cdot 1.$

Przyjmuje się że $0!=1$. Oto wartości silni dla kilku początkowych liczb naturalnych

$\begin{array}{ccccccccccc}n& 0& 1& 2& 3& 4& 5& 6& 7& 8& \cdots \\ n!& 1& 1& 2& 6& 24& 120& 720& 5040& 40320& \cdots \end{array}$

Ciąg $0!,1!,2!,3!,4!,\dots$ aby mógł być precyzyjnie rozumiany np. przez komputer, powinien być zadany rekurencyjnie jako:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned s_0 &=& 1 \\ s_{n} &=& n \cdot s_{n-1} \mbox{\ \ \ dla \ } n\geq 1. \endaligned}

Ponieważ pierwszy wyraz jest zadany, to możemy kolejno obliczać:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned s_0 &=& 1 \\ s_1 &=& 1 \cdot s_{0} = 1 \cdot 1 = 1 \\ s_2 &=& 2 \cdot s_{1} = 2 \cdot 1 = 2 \\ s_3 &=& 3 \cdot s_{2} = 3 \cdot 2 = 6 \\ s_4 &=& 4 \cdot s_{3} = 4 \cdot 6 = 24 \\ \ldots \endaligned}

Przykład

Jaki ciąg jest zdefiniowany poprzez małą modyfikację w definicji silni?

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned s_0 &=& 0 \\ s_{n} &=& n \cdot s_{n-1} \mbox{\ \ \ dla \ } n\geq 1 \endaligned}

A co definiują następujące określenia:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned s_0 &=& \frac{1}{2} \\ s_{n} &=& n \cdot s_{n-1} \mbox{\ \ \ dla \ } n\geq 1 \endaligned}

oraz

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned s_0 &=& 1 \\ s_{n} &=& n \cdot s_{n-2} \mbox{\ \ \ dla \ } n\geq 2. \endaligned}

W ostatnim przypadku widać, że ponieważ odwołanie jest Parser nie mógł rozpoznać (nieznana funkcja „\mathsl”): {\displaystyle \mathsl{dwa wyrazy wstecz}} , to już wyliczenie pierwszego wyrazu $s_1$ staje się niemożliwe.

Ciąg arytmetyczny

Przykład

W ciągu zadanym poprzez równania:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned s_0 &=& 0 \\ s_{n} &=& s_{n-1}+2 \mbox{\ \ \ dla \ } n\geq 1 \endaligned}

łatwo rozpoznać kolejne liczby parzyste:

$s_n=2n.$

Ogólnie ciąg zadany poprzez ustalenie $a_0$ oraz

$a_n=a_{n-1}+r$

to tzw. Parser nie mógł rozpoznać (nieznana funkcja „\mathsl”): {\displaystyle \mathsl ciąg arytmetyczny} .
Jego $n$-ty wyraz dany jest wzorem:

$a_n=a_0+n\cdot r.$

Aby to uzasadnić, pokazujemy indukcyjnie, że:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle a_0 + 0\cdot r = a_0 \mbox{\ \ jest rzeczywiście zerowym wyrazem ciągu} }

oraz

$a_0+n\cdot r=(a_0+(n-1)r)+r=a_{n-1}+r=a_n$

Ciąg geometryczny

Przykład

W ciągu zadanym poprzez równania:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned s_0 &=& 1 \\ s_{n} &=& 2\cdot s_{n-1} \mbox{\ \ \ dla \ } n\geq 1 \endaligned}

łatwo rozpoznać kolejne potęgi liczby $2$:

$s_n=2^n.$

Ogólnie ciąg zadany poprzez ustalenie $a_0$ oraz zadanie

$a_n=q\cdot a_{n-1}$

to tzw. Parser nie mógł rozpoznać (nieznana funkcja „\mathsl”): {\displaystyle \mathsl ciąg geometryczny} .
Jego $n$-ty wyraz dany jest wzorem:

$a_n=a_0\cdot q^n.$

Aby to uzasadnić, pokazujemy indukcyjnie, że:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle a_0 \cdot q^0 = a_0 \cdot 1 = a_0 \mbox{\ \ jest rzeczywiście zerowym wyrazem ciągu} }

oraz

$a_0\cdot q^n=(a_0\cdot q^{n-1})\cdot q=a_{n-1}\cdot q=a_n.$

Wieże Hanoi

Przykład (E.Lucas, 1883)

U zarania czasu Bóg umieścił 64 złote krążki na jednej z trzech diamentowych iglic tak, że krążki wyżej umieszczone miały mniejsze promienie.

{}{0.9pt}

(400,125)

(49,15)(150,0){3}{(2,100)[cc]{

(50,10){(0,0)[tc]{A}} (200,10){(0,0)[tc]{B}} (350,10){(0,0)[tc]{C}} (0,15){(1,0){100}} (2,19){(1,0){96}} (4,23){(1,0){92}} (6,27){(1,0){88}} (8,31){(1,0){84}} (10,35){(1,0){80}} (12,39){(1,0){76}} (14,43){(1,0){72}} (16,47){(1,0){68}} (18,51){(1,0){64}} (20,55){(1,0){60}} (22,59){(1,0){56}}

(42,78){(0,0)[cc]{$⋮$}} (58,78){(0,0)[cc]{$⋮$}}

(40,97){(1,0){20}} (42,101){(1,0){16}} (44,105){(1,0){12}} (46,109){(1,0){8}}

Następnie Bóg polecił grupie mnichów przełożenie tych krążków na trzecią iglicę $(C)$, ale tak by:

• w jednym ruchu przenosić tylko jeden krążek,

• krążek większy nigdy nie może leżeć na krążku mniejszym,

• można posługiwać się iglicą $B$.

Mnisi pracują od zarania dziejów dzień i noc ... .Ile czasu im to zajmie? }}

Wieże Hanoi - analiza

By obliczyć ilość potrzebnych do wykonania ruchów, przeanalizujmy najpierw małe przypadki:
Łatwo zauważyć, że dla 1 krążka potrzebny jest jeden ruch: $A\to C$
Podobnie dla dwu krążków możemy postąpić: $A\to B,A\to C,B\to C$
Przy 3 krążkach postępujemy tak:

• najpierw przenosimy dwa górne krążki na iglicę $B$ posługując się iglicą $C$:

$A\to C,A\to B,C\to B$

• przenosimy największy krążek z $A$ na $C$:

$A\to C$

• przenosimy krążki z $B$ na $C$ posługując się iglicą $A$:

$B\to A,B\to C,A\to C$

co pokazuje, że potrzeba tu 7 ruchów.
Czy już wiesz jak rozwiązać to zadanie w ogólności (dla $n$ krążków)?
Oznaczmy przez $H_n$ liczbę ruchów potrzebnych do przeniesienia $n$ krążków z jednej iglicy na drugą. Wiemy już, że:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned H_1 &=& 1 \\ H_2 &=& 3 \\ H_3 &=& 7 \endaligned}

Aby przenieść $n$ krążków z $A$ na $C$ możemy postąpić podobnie jak w przypadku 3 krążków, redukując zadanie do:

• przenosimy $n-1$ górnych krążków na iglicę $B$ posługując się iglicą $C$ - potrzeba na to $H_{n-1}$ ruchów

• przenosimy największy krążek z $A$ na $C$ - to tylko jeden ruch

• przenosimy $n-1$ krążków z $B$ na $C$ posługując się iglicą $A$ - znów potrzeba na to $H_{n-1}$ ruchów

A zatem

$H_n=H_{n-1}+1+H_{n-1}=2\cdot H_{n-1}+1$

Ile wobec tego wynosi $H_{64}$?

Mamy więc równanie rekurencyjne

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned H_1 &=& 1 \\ H_{n} &=& 2\cdot H_{n-1}+1 \mbox{\ \ \ dla \ } n\geq 2 \endaligned}

bardzo podobne do ciągu geometrycznego.
Możemy policzyć kilka jego wyrazów:

$1,3,7,15,31,63,127,\dots$

i rozpoznać w nim ciąg potęg dwójki zmniejszonych o 1.

Ale czy rzeczywiście $H_n=2^n-1$?

I znów, aby się upewnić, że nasze { odgadnięcie} było poprawne, sprawdzamy indukcyjnie, że

$2\cdot H_{n-1}+1=2\cdot (2^{n-1}-1)+1=2\cdot 2^{n-1}-2+1=2^n-1=H_n$

co oznacza, że rzeczywiście ciąg $2^n-1$ spełnia równanie rekurencyjne, którym zadany jest ciąg $H_n$.
A wiec $H_{64}=2^{64}-1\approx 100000000000000000000$, co przy przenoszeniu jednego krążka na sekundę zajmie ponad $3000000000000$ lat, a przenosząc te krążki "komputerem" 3GHz potrzeba będzie... i tak ponad tysiąc lat!

Przykład

{{{3}}}

Przykład

Jaka jest największa możliwa liczba $l_n$ obszarów wyznaczonych przez $n$ prostych na płaszczyźnie?

Sprawdźmy najpierw kilka pierwszych wartości.

• Gdy nie ma żadnej prostej obszar jest jeden.

• Jedna prosta tworzy zawsze dwa różne obszary.

• Kładąc drugą prostą (byle nie równoległą do pierwszej) otrzymujemy $4$ obszary.

W tym momencie możemy pokusić się o zgadywanie i przypuścić, że $l_n=2^n$. Jednakże

• Dla trzech prostych jest to $7$.

Zauważmy, że nowa prosta zwiększa ilość obszarów o $k$ jeśli przecina dokładnie $k-1$ z poprzednich prostych i to w nowych punktach przecięć. Z drugiej strony dwie proste mogą się przeciąć w co najwyżej jednym punkcie i przecinają się o ile nie są równolegle. Widzimy zatem, że najwięcej obszarów dostaniemy kładąc kolejne proste w ten sposób aby żadne dwie nie były równoległe i żadne trzy nie przecinały się w jednym punkcie. Otrzymujemy następujące równanie rekurencyjne:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned l_0&=&1,\\ l_{n+1}&=&l_n+n. \endaligned}

Ponownie rozwiążemy równanie rozwijając je:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned l_n&=&l_{n-1}+n=l_{n-2}+(n-1)+n=l_{n-3}+(n-2)+(n-1)+n=\ldots\\ &=&l_0+1+2+\ldots+n=1+\frac{n(n+1)}{2}, \endaligned}

gdzie ostatnia równość wynika z - już udowodnionego - wzoru na sumę kolejnych liczb naturalnych.

Liczby Fibonacciego

foto, notka