Matematyka.pl

Mam problem z takim typem zadań, byłabym wdzięczna gdyby ktoś mnie nakierował na sposób rozwiązania

Pokaż, że jeśli funkcja \(\displaystyle{ T: \NN \rightarrow \NN \cup \left\{ 0 \right\}}\) spełnia warunki:
\(\displaystyle{ T(1) = 0}\), \(\displaystyle{ T(n) = T( \lceil \frac{n}{2} \rceil ) + 1}\) dla \(\displaystyle{ n \ge 2}\) to:
\(\displaystyle{ T(n) = \lceil {\log_2 (n)} \rceil}\)

W drugim kroku indukcyjnym załóżmy, że wzór jest prawdziwy dla wszystkich liczb mniejszych niż \(\displaystyle{ n}\) i pokażmy jego prawdziwość dla \(\displaystyle{ n}\) (oczywiście \(\displaystyle{ n>1}\)).

Jeśli \(\displaystyle{ n=2k}\) dla pewnego \(\displaystyle{ k}\) całkowitego, to z uwagi na \(\displaystyle{ k<n}\) wiemy, że wzór jest prawdziwy dla \(\displaystyle{ k}\), mamy zatem:
\(\displaystyle{ T(n)=T(2k) = T(k)+1 = \lceil {\log_2k} \rceil + \log_22=\\ = \lceil {\log_2k} + \log_22\rceil=\lceil \log_2(2k)\rceil =\lceil \log_2n\rceil}\)
Jeśli natomiast \(\displaystyle{ n=2k-1}\) dla pewnego \(\displaystyle{ k}\) całkowitego, to z uwagi na \(\displaystyle{ k<n}\) wiemy, że wzór jest prawdziwy dla \(\displaystyle{ k}\), mamy zatem:
\(\displaystyle{ T(n)=T(2k-1) = T(k)+1 = \ldots =\lceil \log_2 (2k)\rceil = \lceil \log_2 (2k-1)\rceil =\lceil \log_2n\rceil}\)
(przedostatnia równość wynika z tego, że \(\displaystyle{ 2^l<2k-1\le 2^{l+1}}\) wtedy i tylko wtedy gdy \(\displaystyle{ 2^l<2k\le 2^{l+1}}\))

Q.