# Closed form of recursively defined sequence

Let $a_0, a_1 \in \mathbb R$. I am given the sequence $(a_n)_{n\in \mathbb N}$ recursively defined by $$a_n = \frac{2}{5} a_{n-2} + \frac{3}{5} a_{n-1}$$ for $n \geq 2$. I want to find an explicit term describing $a_n$, I tried to figure it out by writing out the first 3-4 terms but I can't really find a pattern since the coefficients are not monotone. Or is there another, easier way to show that the sequence converges?

• Hint: $a_n - a_{n-1} = -\frac25(a_{n-1}-a_{n-2})$ – achille hui Dec 4 '16 at 16:26
• – lab bhattacharjee Dec 4 '16 at 17:14

Hint to see that the sequence converges:

Note that the term $a_{n+2}$ is a weighted mean of its two predecessors.

Hint to find the limit:

Try with $a_0=0$ and $a_1=1$. Then, scale and translate.

• I see a pattern plugging in concrete values, but I am not able to find an explicit formula I could then proof (by induction for example). – Staki42 Dec 4 '16 at 20:38

Given the recurrence $$a_{\,n} = \frac{3} {5}a_{\,n - 1} + \frac{2} {5}a_{\,n - 2} \quad \left| {\;a_{\,n\, < \,0} = 0} \right.$$ in my opinion, the best way to solve it is through the generating function.
So let's write it as: $$a_{\,n} - \frac{3} {5}a_{\,n - 1} - \frac{2} {5}a_{\,n - 2} - \left[ {1 = n} \right]a_{\,1} - \left[ {0 = n} \right]a_{\,0} = 0\quad \left| {\;a_{\,n\, < \,0} = 0} \right.$$ where $[P]$ is the Iverson bracket $$\left[ P \right] = \left\{ {\begin{array}{*{20}c} 1 & {P = TRUE} \\ 0 & {P = FALSE} \\ \end{array} } \right.$$ Then, multiplying by $z^n$ and summing $$\begin{gathered} 0 = \sum\limits_{0\, \leqslant \,n} {a_{\,n} \;z^{\,n} } - \frac{3} {5}\sum\limits_{0\, \leqslant \,n} {a_{\,n - 1} z^{\,n} } - \frac{2} {5}\sum\limits_{0\, \leqslant \,n} {a_{\,n - 2} z^{\,n} } - a_{\,1} \sum\limits_{0\, \leqslant \,n} {\left[ {1 = n} \right]z^{\,n} } - a_{\,0} \sum\limits_{0\, \leqslant \,n} {\left[ {0 = n} \right]z^{\,n} } = \hfill \\ = \sum\limits_{0\, \leqslant \,n} {a_{\,n} \;z^{\,n} } - \frac{3} {5}z\sum\limits_{0\, \leqslant \,n} {a_{\,n - 1} z^{\,n - 1} } - \frac{2} {5}z^{\,2} \sum\limits_{0\, \leqslant \,n} {a_{\,n - 2} z^{\,n} } - a_{\,1} \;z - a_{\,0} = \hfill \\ = A(z) - \frac{3} {5}z\,A(z) - \frac{2} {5}z^{\,2} \,A(z) - a_{\,1} \;z - a_{\,0} \hfill \\ \end{gathered}$$ which gives: $$\begin{gathered} A(z) = \frac{{a_{\,1} \;z + a_{\,0} }} {{1 - \frac{3} {5}\,z - \frac{2} {5}z^{\,2} }} = 5\frac{{a_{\,1} \;z + a_{\,0} }} {{5 - 3\,z - 2z^{\,2} }} = \hfill \\ = \frac{5} {7}\left( {\frac{{a_{\,1} \; + a_{\,0} }} {{1 - z}} + \frac{{2a_{\,0} - 5a_{\,1} }} {{5 + 2z}}} \right) = \hfill \\ = \frac{1} {7}\left( {\frac{{5\left( {a_{\,0} + a_{\,1} } \right)}} {{1 - z}} + \frac{{\left( {2a_{\,0} - 5a_{\,1} } \right)}} {{\left( {1 - \left( { - \frac{2} {5}z} \right)} \right)}}} \right) = \hfill \\ = \frac{1} {7}\left( {\frac{{5\left( {a_{\,0} + a_{\,1} } \right)}} {{1 - z}} + \frac{{\left( {2a_{\,0} - 5a_{\,1} } \right)}} {{\left( {1 - \left( { - \frac{2} {5}z} \right)} \right)}}} \right) = \hfill \\ = \frac{1} {7}\left( {\sum\limits_{0\, \leqslant \,n} {\left( {5\left( {a_{\,0} + a_{\,1} } \right) + \left( {2a_{\,0} - 5a_{\,1} } \right)\left( { - 1} \right)^{\,n} \frac{{2^{\,n} }} {{5^{\,n} }}} \right)\;z^{\,n} } } \right) = \hfill \\ = \frac{{5\left( {a_{\,0} + a_{\,1} } \right)}} {7}\left( {\sum\limits_{0\, \leqslant \,n} {\left( {1 + \left( {\frac{{2a_{\,0} - 5a_{\,1} }} {{a_{\,0} + a_{\,1} }}} \right)\left( { - 1} \right)^{\,n} \frac{{2^{\,n} }} {{5^{\,n + 1} }}} \right)\;z^{\,n} } } \right) \hfill \\ \end{gathered}$$ That tells you that $a(n)$ is converging, oscillating, to $5/7(a_0+a_1)$.

• Thanks for your in-depth answer! – Staki42 Dec 4 '16 at 20:15
• @lappen68: glad to help ! – G Cab Dec 5 '16 at 1:37