Matematyka.pl

Rozwiąż układ równań rekurencyjnych (zakładając, że N jest potęgą dwójki)
\(\displaystyle{ T(1) = 1}\)
\(\displaystyle{ T(N) = c (\lg N) + T(N/2)}\) dla \(\displaystyle{ N \ge 2}\)


Próbowałem w taki sposób :
\(\displaystyle{ T(N) = c(\lg N) + c(\lg \frac{N}{2}) + c(\lg \frac{N}{4}) + ... + c (\lg 2) + 1}\)
\(\displaystyle{ T(N) = c (\lg (N * \frac{N}{2} * \frac{N}{4} * ... * 2) )+ 1 =
c (\lg ( N^{n} * (\frac{1}{2}) ^{0+1+2+...+n-1} ) + 1}\)

Nie wiem w jaki sposób wyrazić \(\displaystyle{ n}\), a może w ogóle źle do tego podchodzę? Proszę o pomocne wskazówki.

Zrób podstawienie:
\(\displaystyle{ N=2^k}\)

Dokładnie tak - tym bardziej, że prowadzący pod oznaczeniem \(\displaystyle{ \lg}\) rozumie logarytm binarny, a nie dziesiętny.
Temat uważam za zamknięty.