Wieże Hanoi - najmniejsza ilość ruchów

[Krzyku]

Problem powszechnie znany jednak nie znalazłem odpowiedzi która by mnie satysfakcjonowała.
Mamy 3 paliki oraz n krążków. Mam podać najmniejszą ilość ruchów żeby przenieść wieżę z lewego na prawy palik.
To, że ilość przeniesień n krążków wynosi \(\displaystyle{ a_{n} = 2a_{n-1}+1}\) oraz warunek początkowy \(\displaystyle{ a_{1}=1}\). To rozumiem.
Dalej mam funkcję tworzącą \(\displaystyle{ \sum_{n=2}^{ \infty }a_{n} x^{n}=2\sum_{n=2}^{ \infty }a_{n-1}x^{n}+\sum_{n=2}^{ \infty }x^{n}}\)
Tutaj nie ogarniam co dalej się dzieje. Wg. moich notatek teraz wychodzi \(\displaystyle{ f(x)=2x f(x)+ \frac{1}{1-x}}\) i dalej rozwiązujemy to równanie \(\displaystyle{ f(x)= \frac{x}{(1-x)(1-2x)}=...}\) Oczywiście rozwiązania tego równania taż nie rozumiem :/ Czy ktoś może mi pomóc?

[Tytanowy Janusz]

Czego konkretnie nie rozumiesz?
Jak otrzymałeś wzór na funkcję tworzącą to teraz trzeba ją rozwinąć w szereg. Wyrażenie \(\displaystyle{ \frac{x}{(1-x)(1-2x)}}\) należy rozłożyć na ułamki proste, potem dla obu składników sumy skorzystać ze wzoru na sumę szeregu potęgowego. Na końcu odczytujesz postać jawną wzoru na \(\displaystyle{ a_{n}}\).