Znajdź postać jawną dla ciągu zdefiniowanego

juicy152 · Post autor: **juicy152** » 17 lut 2018, o 13:35

Znajdź postać jawną dla ciągu zdefiniowanego rekurencyjnie:

\(\displaystyle{ T(1)=4T\left(\left[\frac{n}{2}\right]\right),\ T(1)=2}\)

i udowodnij zaproponowaną postać.

szw1710 · Post autor: **szw1710** » 17 lut 2018, o 14:45

Biorąc \(\displaystyle{ n=2k}\) przy ustalonym \(\displaystyle{ k\in\NN}\) mamy \(\displaystyle{ T(1)=4T(k)}\) dla każdego \(\displaystyle{ k\in\NN}\), a zatem \(\displaystyle{ T(k)=\frac{1}{2}}\) dla każdego \(\displaystyle{ k\in\NN}\).

Premislav · Post autor: **Premislav** » 17 lut 2018, o 15:24

Pewnie miało być \(\displaystyle{ T(n)=4T\left( \left\lfloor \frac n 2\right\rfloor\right)}\). No ale to forum matematyczne, a nie wrozka.pl, nie mamy obowiązku zgadywać.

Gdyby chodziło o \(\displaystyle{ T(n)=4T\left( \left\lfloor \frac n 2\right\rfloor\right), \ T(1)=2}\), to rozpisanie paru pierwszych wyrazów na karteluszku i w miarę przytomny rzut okiem na nie sugeruje, że
\(\displaystyle{ T(n)=2\cdot 4^{ \left\lfloor \frac n 2\right\rfloor}}\) (ta podłoga jest w wykładniku).
Pozostaje udowodnić tę prawidłowość indukcyjnie, co zostawiam jako ćwiczenie.