równanie wież Hanoi metodą sumacyjną

[FantaZy]

Czy mógłby ktoś pomóc i objaśnić ten przykład metodą sumacyjną. Ile potrafiłem tyle napisałem.

\(\displaystyle{ T_n=\begin{cases} 0 & n=0\\2T_{n-1}+1 & n>0\end{cases}}\)

\(\displaystyle{ a_n = 1\
b_n = 2\
c_n=1}\)

\(\displaystyle{ s_n=\frac{a_{n-1}}{b_n}s_{n-1}=\frac{1}{2^n}}\)

\(\displaystyle{ T_n=2T_{n-1}+1}\)

\(\displaystyle{ s_nT_n=2\frac{1}{2^{n}}T_{n-1}+\frac{1}{2^{n}}}\)

\(\displaystyle{ U_n=U_{n-1}+\frac{1}{2^n}}\)

[bartek118]

No teraz rozwiązujesz rekurencję ze względu na \(\displaystyle{ U_n}\). Formuła rekurencyjna sugeruje postać: \(\displaystyle{ U_n = 1 + \frac{1}{2} + \frac{1}{2^2} + ... + \frac{1}{2^n}}\)

[FantaZy]

czyli idąc dalej, coś takiego:
\(\displaystyle{ U_n=U_0+\sum_{k=1}^{n} \frac{1}{2^{k-1}}}\)

[bartek118]

Tak, ale u Ciebie \(\displaystyle{ U_0 = 0}\). I prawie - powinno być \(\displaystyle{ U_n=U_0+\sum_{k=1}^{n} \frac{1}{2^{k}}}\). I na tę sumę jest wzór - suma ciągu geometrycznego.

[FantaZy]

czy to \(\displaystyle{ \frac{1}{2^n}}\) jest poprawne?

[bartek118]

Tak, a czemu nie?

[FantaZy]

w książce z której mam ten przykład jest podane \(\displaystyle{ s_n=\frac{2}{2^n}}\)

[bartek118]

Też się sprawdzi, czynników sumacyjnych jest wiele, w książce jest taki, a u Ciebie jest inny, ważne, że spełnia równość, którą ma spełniać.

[FantaZy]

idąc dalej(podstawiając za \(\displaystyle{ U_n=s_nT_n}\)
\(\displaystyle{ \frac{1}{2^n}T_n=(0+\sum_{k=1}^{n} \frac{1}{2^k}) //:\frac{1}{2^n}}\)
\(\displaystyle{ T_n=\frac{1}{\frac{1}{2^n}} \cdot\sum_{k=1}^{n}\frac{1}{2^k}=2^n\sum_{k=1}^{n}\frac{1}{2^k}}\)

co mogę dalej z tym zrobić? w książce ostateczny wynik to \(\displaystyle{ T_n=2^n-1}\)(mieli nieco inne \(\displaystyle{ s_n}\))