Zależność rekurencyjna, sufity i podłogi

[lennyh]

Mając daną zależność rekurencyjną:

\(\displaystyle{ C_N = C_{\left\lfloor \frac{N}{2} \right\rfloor} + C_{\left\lceil \frac{N}{2} \right\rceil} + N,\ \ N \ge 2}\)
\(\displaystyle{ C_1 = 0}\)

wyznacz rekurencję dla \(\displaystyle{ C_{N+1} - C_N}\). Wykorzystaj ją do pokazania, że

\(\displaystyle{ C_N = \sum_{1 \le k < N} \left( \left\lfloor \lg k + 2 \right\rfloor \right)}\)

Udowodnij, że \(\displaystyle{ C_N = N \left\lceil \lg N \right\rceil + N - 2^{\left\lceil \lg N \right\rceil}}\).

[arek1357]

łatwo zauważyć, że ciąg ten to taki zmutowany ciąg arytmetyczny i zachodzi:

\(\displaystyle{ 2^n+1 \le i,i+1 \le 2^{n+1}}\)

\(\displaystyle{ C_{i+1}-C_{i}=n+2}\)