Matematyka dyskretna 1/Ćwiczenia 2: Rekurencja

Rekurencja

Ćwiczenie 1

Znajdź postać zwartą ciągu zadanego równaniem rekurencyjnym:

$\{\begin{array}{rl}{a}_0& =2,\\ a_1& =5,\\ a_n& =5a_{n-1}-6a_{n-2}\text{dla}n\ge 2.\end{array}$

Wskazówka

Wypisz kilka początkowych wyrazów ciągu. Zaobserwuj, że $a_n=2^n+3^n,$ a następnie udowodnij to indukcyjnie ze względu na $n$ .

Rozwiązanie

Przeprowadźmy dowód, że $a_n=2^n+3^n$ , indukcyjnie ze względu na $n$ . Dla wartości początkowych $n=0,1$ dostajemy odpowiednio, że

$\begin{array}{rl}{a}_0& =2=2^0+3^0,\\ a_1& =5=2^1+3^1.\end{array}$

Przejdźmy więc do przypadku $n\ge 2$ . Na mocy zależności rekurencyjnej otrzymujemy, że

$\begin{array}{rl}{a}_n& =5a_{n-1}-6a_{n-2}\\ & =5(2^{n-1}+3^{n-1})-6(2^{n-2}+3^{n-2})\\ & =4\cdot 2^{n-2}+9\cdot 3^{n-2}\\ & =2^n+3^n,\end{array}$

co kończy dowód.

Ćwiczenie 2

Znajdź postać zwartą ciągu zadanego równaniem rekurencyjnym:

$\{\begin{array}{rl}{a}_0& =1,\\ a_1& =2,\\ a_n& =\frac{a_{n-1}^2}{a_{n-2}}\text{dla}n\ge 2.\end{array}$

Wskazówka

Wypisz kilka początkowych wyrazów ciągu. Zaobserwuj, że $a_n=2^n,$ a następnie udowodnij to indukcyjnie ze względu na $n$ .

Rozwiązanie

Przeprowadźmy dowód, że $a_n=2^n$ , indukcyjnie ze względu na $n$ . Dla wartości początkowych $n=0,1$ dostajemy odpowiednio, że

$\begin{array}{rl}{a}_0& =1=2^0,\\ a_1& =2=2^1.\end{array}$

Przejdźmy więc do przypadku $n\ge 2$ . Na mocy zależności rekurencyjnej otrzymujemy, że

$a_n=\frac{a_{n-1}^2}{a_{n-2}}=\frac{{\left(2^{n-1}\right)}^2}{2^{n-2}}=2^{2(n-1)-(n-2)}=2^n,$

co kończy dowód.

Ćwiczenie 3

Ciąg liczb Lucasa jest definiowany następującą zależnością rekurencyjną:

$\{\begin{array}{rl}{l}_0& =1,\\ l_1& =3,\\ l_n& =l_{n-1}+l_{n-2}\text{dla}n\ge 2.\end{array}$

Udowodnij, że $l_n=f_{n+1}+f_{n-1},$ gdzie $f_n$ jest $n$ -tą liczbą Fibonacci'ego. (Dla precyzji obliczeń przyjmij, że $f_{-1}=0$ .)

Wskazówka

Zastosuj indukcję względem $n$ .

Rozwiązanie

Dowód przeprowadzimy, indukcyjnie ze względu na $n$ . Dla wartości początkowych $n=0,1$ dostajemy odpowiednio, że

$\begin{array}{rl}{f}_1+f_{-1}& =1+0=1=l_0,\\ f_2+f_0& =2+1=3=l_1.\end{array}$

Przejdźmy więc do przypadku $n\ge 2$ . Na mocy zależności rekurencyjnej otrzymujemy, że

$\begin{array}{rl}{l}_n& =l_{n-1}+l_{n-2}\\ & =(f_n+f_{n-2})+(f_{n-1}+f_{n-3})\\ & =(f_n+f_{n-1})+(f_{n-2}+f_{n-3})\\ & =f_{n+1}+f_{n-1},\end{array}$

co kończy dowód.

Ćwiczenie 4

Adam i Marek zabawiali się w następującą grę. Adam wymyślał liczbę z zakresu od $0$ do $n-1$ . Zadaniem Marka było odgadnąć tę liczbę zadając Adamowi pytania, na które mógł odpowiadać jedynie TAK lub NIE. Znajdź najmniejszą liczbę pytań, po której Marek zawsze odnajdzie szukaną liczbę.

Wskazówka

Załóżmy, że Marek ma pewność, że szukana liczba $x$ znajduje się w przedziale $[a,b]$ . Po uzyskaniu odpowiedzi na pytanie, czy $x$ jest większa niż $\lfloor (a+b+1)/2\rfloor$ , Marek zawęzi zbiór poszukiwań o połowę, szukając później liczby $x$ w przedziale $[a,\lfloor (a+b-1)/2\rfloor ]$ albo w przedziale $[\lfloor (a+b+1)/2\rfloor ,b]$ . Dla uproszczenia obliczeń załóż, że Marek szuka liczby z zakresu $[0,2^{\lceil \lg n\rceil }-1]$ .

Rozwiązanie

Strategię Marka można przedstawić w następujący rekurencyjny sposób:

• Jeśli szukana liczba $x$ jest z zakresu $[a,b]$, gdzie $a=b$, to Marek wie, że szukana liczba to $a$ .
• Jeśli szukana $x$ liczba jest z zakresu $[a,b]$, gdzie $a<b$, to Marek zadaje pytanie, czy $x\ge \lfloor (a+b+1)/2\rfloor$. Gdy Adam odpowie:
  • NIE, to $x\in [a,\lfloor (a+b-1)/2\rfloor ]$ ,
  • TAK, to $x\in [\lfloor (a+b+1)/2\rfloor ,b]$ .

Za każdym razem, zbiór możliwych wartości $x$ zmniejsza się o połowę. Tak pomniejszony zbiór przeszukujemy wykorzystując rekurencyjnie opisywaną strategię.

Dla uproszczenia obliczeń załóżmy, że Marek na początku powiększa przedział poszukiwań do $[0,2^{\lceil \lg n\rceil }-1]$. Może oczywiście tak zrobić, bo $n\le 2^{\lceil \lg n\rceil }.$ Równanie rekurencyjne opisujące liczbę zapytań $T\left(n\right)$ jest więc postaci

$\{\begin{array}{rl}T\left(1\right)& =0,\\ T\left(n\right)& =T\left(\lceil \frac{n}{2}\rceil \right)+1\text{dla}n\ge 2.\end{array}$

Dla liczb postaci $2^k$ , gdzie $k=0,1,\dots$ otrzymujemy prostszą postać:

$\{\begin{array}{rl}T\left(1\right)& =0,\\ T\left(2^k\right)& =T\left(2^{k-1}\right)+1\text{dla}k\ge 1.\end{array}$

Pokażmy indukcyjnie, że

$T\left(2^k\right)=k.$

Dla $n=1$ otrzymujemy, że

$T\left(1\right)=\lg 1=0.$

Przejdźmy więc do przypadku, gdy $k>0$ . Korzystając z założenia indukcyjnego, że $T\left(2^{k-1}\right)=k-1$ , otrzymujemy:

$T\left(2^k\right)=T\left(2^{k-1}\right)+1=(k-1)+1=k.$

W konsekwencji wiemy, że liczba pytań po których Marek dowie się o jaką liczbę chodzi jest równa

$T\left(2^{\lceil \lg n\rceil }\right)=\lceil \lg n\rceil .$

Ćwiczenie 5

Talia składa się z $2^n$ kart. Sortujemy te karty poprzez rekurencyjne rozkładanie ich na dwie równe kupki w następujący sposób:

• Jeśli kupka składa się z jednej karty, to kupka ta jest posortowana.
• Kupkę zawierającą $2^k$ kart, gdzie $k>0$ ,

dzielimy na dwie kupki zawierające po $2^{k-1}$ kart. Każdą z tych mniejszych kupek sortujemy oddzielnie (powtarzając rekurencyjnie całą procedurę sortowania). Następnie kolejno zbieramy karty ze szczytów obu kupek, zawsze zabierając większą z dwu szczytowych kart.

Oblicz ile ruchów potrzebnych było do posortowania wszystkich $2^n$ kart, jeżeli rozdzielenie $2^k$ kart na dwie kupki wymaga $2^{k-1}$ ruchów, a złożenie dwu posortowanych kupek, o $2^{k-1}$ kartach, w jedną całość wymaga $2^k$ ruchów.

Wskazówka

Udowodnij indukcyjnie, ze względu na $n$ , że liczba ruchów potrzebna do posortowania $2^n$ kart wymaga $\frac{3}{2}n{2}^n$ ruchów.

Rozwiązanie

Z definicji rekurencyjnej sortowania kart wynika, że dla $n>0$ liczba $T\left(2^n\right)$ potrzebnych przełożeń $2^n$ kart jest równa sumie

• $2^{n-1}$ ruchów na rozdzielenie kupek,
• $2T\left(2^{n-1}\right)$ posortowanie obu rozdzielonych kupek,
• $2^n$ ruchów na scalenie dwu posortowanych części.

Otrzymujemy więc następujące równanie rekurencyjne:

$\{\begin{array}{rl}T\left(1\right)& =0,\\ T\left(2^n\right)& =2T\left(2^{n-1}\right)+\frac{3}{2}\cdot 2^n\text{dla}n\ge 1.\end{array}$

Udowodnijmy indukcyjnie ze względu na $n$ , że

$T\left(2^n\right)=\frac{3}{2}n{2}^n.$

Dla jednej karty mamy:

$\frac{3}{2}\cdot 0\cdot 2^0=0=T\left(1\right)=T\left(2^0\right),$

Przejdźmy więc do przypadku, gdy $n>0$ . Korzystając z założenia indukcyjnego otrzymujemy:

$\begin{array}{rl}T\left(2^n\right)& =2T\left(2^{n-1}\right)+\frac{3}{2}\cdot 2^n\\ & =2\left(\frac{3}{2}(n-1)2^{n-1}\right)+\frac{3}{2}\cdot 2^n\\ & =\frac{3}{2}n{2}^n-\frac{3}{2}\cdot 2^n+\frac{3}{2}\cdot 2^n\\ & =\frac{3}{2}n{2}^n,\end{array}$

co kończy dowód.

Ćwiczenie 6

Rozwiąż równanie rekurencyjne:

$\{\begin{array}{rl}T\left(2\right)& =0,\\ T\left(n\right)& =2T\left(\sqrt{n}\right)+1\text{dla}n\ge 1,\end{array}$

przy czym $n$ jest postaci $2^{2^k}$ , gdzie $k$ jest liczbą naturalną.

Wskazówka

Policz kilka pierwszych wyrazów tego ciągu. Zaobserwuj, że $T\left(2^{2^k}\right)=k$ , a następnie udowodnij indukcyjnie, że w istocie tak jest.

Rozwiązanie

Po zapisaniu $n$ w postaci $2^{2^k}$ otrzymujemy równanie:

$\{\begin{array}{rl}T\left(2\right)& =0,\\ T\left(2^{2^k}\right)& =2T\left(2^{2^{k-1}}\right)+1\text{dla}k\ge 1,\end{array}$

Udowodnimy indukcyjnie ze względu na $k\ge 0$ , że

$T\left(2^{2^k}\right)=k.$

Dla początkowej wartości $k=0$ otrzymujemy, że

$T\left(2^{2^0}\right)=T\left(2\right)=0.$

Przejdźmy więc do przypadku, gdy $k\ge 0$ . Korzystając z założenia indukcyjnego otrzymujemy, że

$T\left(2^{2^k}\right)=2T\left(2^{2^{k-1}}\right)+1=(k-1)+1=k.$

W konsekwencji, gdy $n$ jest postaci $2^{2^k}$ , czyli $k=\lg \lg n$ , otrzymujemy:

$T\left(n\right)=\lg \lg n.$