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ść.