Równanie rekurencyjne

[adi191]

Witam. W podręczniku "Algorytmy i struktury danych" znalazłem następujący problem rekurencyjny:
\(\displaystyle{ \begin{cases} T(n)=T(\lfloor \frac{n}{4} \rfloor)+T(\lfloor \frac{3n}{4} \rfloor)+n \\ T(1)=1 \end{cases}}\).
W podręczniku tym problemy te rozwiązywano przez podstawienie \(\displaystyle{ n=2^{k}}\) więc i to zadanie powinno być tak rozwiązywalne. Proszę o pomoc.

[bartek118]

W tym przypadku sugerowałbym popatrzeć na przypadek \(\displaystyle{ n=4^k}\).

[adi191]

To rozumiem, ale jak uwzględnić mnożenie przez 3 w drugim wyrazie sumy?

[bartek118]

Masz
\(\displaystyle{ T(4^k) = T(4^{k-1}) + T(3 \cdot 4^{k-1}) + 4^k}\)

[adi191]

Po rozpisaniu tego otrzymuje:
\(\displaystyle{ T(4^{k})= \sum_{i=0}^{k} {k \choose i} T(3^{i}) +k4^{k}}\) i tu mam problem z wyrażeniami z potęgami 3.