====== Matematyka dyskretna (M) - Lista 3. ======

=====Zadanie 1.======
Indukcja:\\
\\
Baza:\\
$f(1) = 0 + f(1) + f(0) = f(1)$\\
OK.\\
Krok:\\
$ f(n+1) = \sum_{k=1}^{n+1} {\lceil \log_2{k} \rceil}= n-1 +f(\lceil n/2 \rceil)+f(\lfloor n/2 \rfloor) + \lceil log_2{ (n+1)} \rceil = $\\
Dla parzystych:\\
$ n -1 + 2 \cdot \sum_{k=1}^{\frac{n}{2}} {\lceil \log_2{k} \rceil} + \lceil \log_2{(n+1)} \rceil =$\\
$ n + 1 + 2 \cdot \sum_{k=3}^{\frac{n}{2}} {\lceil \log_2{k} \rceil} + \lceil \log_2{\frac{n+1}{2}} + \log_2{2} \rceil =$\\
$ n + 2 + 2 \cdot \sum_{k=3}^{\frac{n}{2}} {\lceil \log_2{k} \rceil} + \lceil \log_2{\frac{n+1}{2}}\rceil =$\\
$ n + 2 \cdot \sum_{k=1}^{\frac{n}{2}} {\lceil \log_2{k} \rceil} + \lceil \log_2{\frac{n+1}{2}}\rceil =$\\
$ n + \sum_{k=1}^{\frac{n}{2}} {\lceil \log_2{k} \rceil} +\sum_{k=1}^{\frac{n}{2}} {\lceil \log_2{k} \rceil} + \lceil \log_2{\frac{n+1}{2}}\rceil =$\\
$ n + \sum_{k=1}^{\lfloor \frac{n+1}{2} \rfloor} {\lceil \log_2{k} \rceil} +\sum_{k=1}^{\lceil \frac{n+1}{2} \rceil} {\lceil \log_2{k} \rceil} =$\\
$ n + f(\lfloor \frac{n+1}{2} \rfloor ) + f(\lceil \frac{n+1}{2} \rceil)$\\
Dla nieparzystych:\\
$ n - 1 + \sum_{k=1}^{\lceil \frac{n}{2} \rceil} {\lceil \log_2{k} \rceil}+ \sum_{k=1}^{\lfloor \frac{n}{2} \rfloor} {\lceil \log_2{k} \rceil} + \lceil \log_2{(n+1)} \rceil =$\\
$ n + 1 + \sum_{k=3}^{\lceil \frac{n}{2} \rceil} {\lceil \log_2{k} \rceil}+ \sum_{k=3}^{\lfloor \frac{n}{2} \rfloor} {\lceil \log_2{k} \rceil} + \lceil \log_2{\frac{n+1}{2}} + \log_2{2} \rceil =$\\
$ n + 2 + \sum_{k=3}^{\lceil \frac{n}{2} \rceil} {\lceil \log_2{k} \rceil}+ \sum_{k=3}^{\lfloor \frac{n}{2} \rfloor} {\lceil \log_2{k} \rceil} + \lceil \log_2{\frac{n+1}{2}}\rceil =$\\
$ n + \sum_{k=1}^{\lceil \frac{n}{2} \rceil} {\lceil \log_2{k} \rceil}+ \sum_{k=1}^{\lfloor \frac{n}{2} \rfloor} {\lceil \log_2{k} \rceil} + \lceil \log_2{\frac{n+1}{2}}\rceil =$\\
$ n + \sum_{k=1}^{\lceil \frac{n}{2} \rceil} {\lceil \log_2{k} \rceil}+ \sum_{k=1}^{\lceil \frac{n}{2} \rceil - 1} {\lceil \log_2{k} \rceil} + \lceil \log_2{\frac{n+1}{2}}\rceil =$\\
$ n + \sum_{k=1}^{\frac{n+1}{2} } {\lceil \log_2{k} \rceil}+ \sum_{k=1}^{\frac{n+1}{2} - 1} {\lceil \log_2{k} \rceil} + \lceil \log_2{\frac{n+1}{2}}\rceil =$\\
$ n + \sum_{k=1}^{\frac{n+1}{2} } {\lceil \log_2{k} \rceil}+ \sum_{k=1}^{\frac{n+1}{2}} {\lceil \log_2{k} \rceil} =$\\
$ n + f(\lceil \frac{n+1}{2} \rceil) + f(\lfloor \frac{n+1}{2} \rfloor)$

I co jest śmieszne, pokazaliśmy, że ze wzoru z sumą wynika związek rekurencyjny, a teraz pokażemy, że ze związku wynika wzór z sumą.\\
\\
Indukcja:\\
\\
Baza:\\
$f(1)=\lceil \log_2{1} \rceil = 0$\\
OK.\\
Krok:\\
$f(n+1)= n + f(\lceil \frac{n+1}{2} \rceil ) + f(\lfloor \frac{n+1}{2} \rfloor )=$\\
Dla n nieparzystych:\\
$n + 2 \cdot \sum^{\frac{n+1}{2}}_{k=1}=$\\
$(n - 1) + 1 + \sum^{\frac{n+1}{2}}_{k=1}{\lceil \log_2{k} \rceil} + \sum^{\frac{n-1}{2}}_{k=1}{\lceil \log_2{k} \rceil} + {\lceil \log_2{\frac{n+1}{2}} \rceil} =$\\
$f(n) + 1 + {\lceil \log_2{\frac{n+1}{2}} \rceil} =$\\
$f(n) + \log_2{2} + {\lceil \log_2{\frac{n+1}{2}} \rceil} =$\\
$f(n) + {\lceil \log_2{(n+1)} \rceil} =$\\
$\sum_{k=1}^{n+1}{\lceil \log_2{k} \rceil}$\\
Dla n parzystych:\\
$n + \sum^{\frac{n}{2}+1}_{k=1}{\lceil \log_2{k} \rceil}+ \sum^{\frac{n}{2}}_{k=1}{\lceil \log_2{k} \rceil}=$\\
$(n-1) +1  + \sum^{\frac{n}{2}+1}_{k=1}{\lceil \log_2{k} \rceil}+ \sum^{\frac{n}{2}}_{k=1}{\lceil \log_2{k} \rceil}=$\\
$(n-1) +1  + \sum^{\frac{n}{2}}_{k=1}{\lceil \log_2{k} \rceil} + \sum^{\frac{n}{2}}_{k=1}{\lceil \log_2{k} \rceil} + \lceil \log_2{\frac{n+1}{2}} \rceil =$\\
$f(n) + 1  + \lceil \log_2{\frac{n+1}{2}} \rceil=$\\
$f(n) +  \log_2{2}  + \lceil \log_2{\frac{n+1}{2}}\rceil=$\\
$f(n) +  \lceil \log_2{(n+1)} \rceil=$\\
$\sum^{n+1}_{k=1}{\lceil \log_2{k} \rceil}$\\
\\
Załóżmy, że istnieje $f'$ spełniające zależność rekurencyjną i $ f \neq f'$.\\
To znaczy, że istnieje takie $x_0$, że $f(x_0) \neq f'(x_0)$.\\
Weźmy więc takie $x_0$ i sprawdzmy wartość funkcji $f$ i $f'$ w tym punkcie.\\
$f(x) = \sum_{k=1}^{x}{\lceil \log_2{k} \rceil}$\\
Z dowodu wyżej:\\
$f'(x) = \sum_{k=1}^{x}{\lceil \log_2{k} \rceil}$\\
A powinny sie różnić - sprzeczność.\\

===== Zadanie 4. =====
{{tag>[listy_zadan]}}