Równanie rekurencyjne - metoda podstawienia

Poszukujaca · Post autor: **Poszukujaca** » 7 gru 2016, o 17:34

Metodą podstawienia rozwiąż:
\(\displaystyle{ T(n) = \begin{cases} 0, \ n=0 \\ 2T(n-1)+1, \ n \ge 1 \end{cases}}\)

Czy będzie ktoś w stanie wytłumaczyć metodę podstawienia, tak krok po kroku?

arek1357 · Post autor: **arek1357** » 7 gru 2016, o 18:03

Na pewno ktoś w stanie będzie.

Ja ze swej skromnej strony proponuję funkcje tworzące...

Mruczek · Post autor: **Mruczek** » 7 gru 2016, o 20:39

Moim zdaniem podstawieniem będzie szybciej i bardziej elementarnie.

\(\displaystyle{ T _{n} = 2 T_{n - 1} + 1 \\
T _{n} + 1 = 2 T_{n - 1} + 2 \\
T _{n} + 1 = 2 \left( T_{n - 1} + 1\right)}\)

Podstawmy \(\displaystyle{ A_{n} = T_{n} + 1}\):

\(\displaystyle{ A_{n} = 2 A_{n - 1} = 4A_{n - 2}= ... = 2^{n}A_{0} = 2^{n} \cdot 1 = 2^{n} \\
T_{n} = A_{n} - 1 = 2^{n} - 1}\)

Poszukujaca · Post autor: **Poszukujaca** » 8 gru 2016, o 00:04

Mruczek, sprytnie. Ale czy tutaj nie jest potrzebny jeszcze dowód przez indukcję?

arek1357 · Post autor: **arek1357** » 8 gru 2016, o 00:19

Nie zawadzi.
Ale bez szału...

a4karo · Post autor: **a4karo** » 8 gru 2016, o 09:40

Poszukujaca pisze:Mruczek, sprytnie. Ale czy tutaj nie jest potrzebny jeszcze dowód przez indukcję?

Jak bardzo chcesz... Ale może wystarczy powołać się na wiedzę o ciągach geometrycznych

Mariusz M · Post autor: **Mariusz M** » 26 gru 2016, o 01:17

arek1357, ja też funkcjami tworzącymi bym się bawił

Janusz Tracz · Post autor: **Janusz Tracz** » 29 gru 2016, o 10:58

Można transformatą \(\displaystyle{ \mathcal{Z}}\) też całkiem szybko to policzyć.

Zapiszmy równanie porządkowe przesunięte o \(\displaystyle{ 1}\)

\(\displaystyle{ t(n+1)=2t(n)+1 \ \ | \mathcal{Z}}\)

\(\displaystyle{ z(T-t(0))=2T+ \frac{z}{z-1}}\)

Warunek początkowy to \(\displaystyle{ t(0)=0}\) ,wyznaczamy \(\displaystyle{ T}\) i transformujemy odwrotnie \(\displaystyle{ \mathcal{Z}^{-1}}\)

\(\displaystyle{ T=z \frac{1}{(z-2)(z-1)} = \frac{z}{z-2} - \frac{z}{z-1} \ \ | \mathcal{Z}^{-1}}\)

\(\displaystyle{ t(n)=2^n-1}\)

Użyte przemienienie oznaczenia zmieniają tyle że ja używam małego \(\displaystyle{ t}\) na początku i dużego \(\displaystyle{ T}\) jako transformowanego.