Ciąg mieszany (albo coś w tym stylu)

[varian]

Załóżmy, że mamy ciąg, który powstaje poprzez pomnożenie poprzedniego elementu przez jakąś stałą "a" i dodanie do tego iloczynu jakiejś stałej "b". Możemy dla przejrzystości zapisać pierwsze cztery elementy:
\(\displaystyle{ \begin{displaymath}
a_{1}=1 \\
a_{2}=a+b \\
a_{3}=(a+b)*a+b \\
a_{4}=[(a+b)*a+b]*a+b \\
\end{displaymath}}\)
Można łatwo napisać algorytm, który liczy n-ty element a, ale nie wiem jak sformalizować matematycznie wzór na n-ty element a, żeby nie odwoływać się w nim do elementu numer (n-1), ale wyrazić go tylko w kategoriach wartości początkowej (tutaj 1) oraz "a" i "b" prawdopodobnie używając operatorów \(\displaystyle{ \sum czy \prod}\) . Wie ktoś jak to wyrazić?

[kropka+]

A może być tak?

\(\displaystyle{ a _{1}=1\\
a _{n}=a ^{n-1}+b \sum_{i=0}^{n-2}a ^{i}}\)

[a4karo]

Może być. Ale to się da ładnie zwinąć... do roboty kropeczko

[varian]

@kropka+

Dzięki!
Niestety nie przyszło mi to do głowy, aby rozpisać te elementy i wtedy pomyśleć nad wzorem... Będę więc miał niezłą nauczkę!

@a4akro

Jeśli to się da jeszcze lepiej zapisać, to też oczywiście jestem tego ciekaw.

[a4karo]

wsk: suma w kropkowym wzorze to suma wyrazów ciągu geometrycznego

[varian]

To coś takiego?

\(\displaystyle{ \begin{displaymath}
a_{n}= a^{n-1}+ \frac{b(1-a^{n-1})}{1-a}
\end{displaymath}}\)

[a4karo]

Tak

[mmttdd]

Dzięki!
Niestety nie przyszło mi to do głowy, aby rozpisać te elementy i wtedy pomyśleć nad wzorem... Będę więc miał niezłą nauczkę!

Nie jest konieczne nad niczym myśleć, gdyż mamy tu zupełnie standardowy problem, liniowe równanie rekurencyjne. Istnieje kilka metod rozwiązywania takich równań, możesz sobie poczytać.
Można też zastosować podstawienie \(\displaystyle{ a _{n}=b _{n} +c}\) i tak dobrać wartość parametru \(\displaystyle{ c}\), żeby pozbyć się z równania wyrazu wolnego. Wtedy \(\displaystyle{ \left( b _{n} \right)}\) będzie ciągiem geometrycznym i łatwo można znaleźć jego ogólny wzór i wrócić do ciągu \(\displaystyle{ \left( a _{n} \right)}\).

[Jarmil]

W ten sposób można obliczyć minimalną liczbę ruchów przy wieży hanoi dla a=2 b=1. Właściwe posunięcia idealnie wpisują się w przedstawiony ciąg.

i dostajemy an=2^n-1