Fibonacci sequence: $a_1 = 1, a_2 = 1, a_n = a_{n-1} + a_{n-2}$
Derivation:
Let $a_n + x a_{n-1} = y(a_{n-1} + x a_{n-2})$
$a_n + x a_{n - 1} = y a_{n-1} + xya_{n-2}$
$a_{n} = (y-x) a_{n-1} + x y a_{n-2}$
Then:
$\begin{cases} y - x = 1 \ xy = 1 \end{cases} \Rightarrow \begin{cases} x = \frac{\sqrt{5} - 1}{2} \ y = \frac{\sqrt{5} + 1}{2} \end{cases}$
$a_n + \frac{\sqrt{5} - 1}{2} a_{n-1} =\frac{\sqrt{5} + 1}{2} (a_{n-1} + \frac{\sqrt{5} - 1}{2} a_{n-2})$
Let: $b_n = a_n + \frac{\sqrt{5} - 1}{2} a_{n-1}$
Then: $b_n = \frac{\sqrt{5}+1}{2}b_{n-1}$
And: $b_2 = a_2 + \frac{\sqrt{5} - 1}{2} a_1 = 1 + \frac{\sqrt{5} - 1}{2} = \frac{\sqrt{5} + 1}{2}$
So: $b_n = (\frac{\sqrt{5} + 1}{2}) ^ {n-1}$
$b_n = \frac{(\frac{\sqrt{5} + 1}{2}) ^ {n-1} \sqrt{5}}{\sqrt{5}} \ = \frac{(\frac{\sqrt{5} + 1}{2}) ^ {n-1} \frac{2\sqrt{5}}{2}}{\sqrt{5}} \ = \frac{(\frac{\sqrt{5} + 1}{2}) ^ {n-1} (\frac{1 + \sqrt{5}}{2} - \frac{1 - \sqrt{5}}{2}))}{\sqrt{5}} \ = \frac{(\frac{1 + \sqrt{5}}{2}) ^ {n} - (\frac{1 - \sqrt{5}}{2})(\frac{\sqrt{5} + 1}{2}) ^ {n-1}}{\sqrt{5}} = \frac{(\frac{1 + \sqrt{5}}{2}) ^ {n}}{\sqrt{5}} - \frac{(\frac{1 - \sqrt{5}}{2})(\frac{1 + \sqrt{5}}{2}) ^ {n-1}}{\sqrt{5}}$
$\because b_n = a_n + \frac{\sqrt{5} - 1}{2} a_{n-1}$
$\therefore a_n -\frac{(\frac{1 + \sqrt{5}}{2}) ^ {n}}{\sqrt{5}} = \frac{1 - \sqrt{5}}{2} a_{n-1} - \frac{(\frac{1 - \sqrt{5}}{2})(\frac{1 + \sqrt{5}}{2})^{n-1}}{\sqrt{5}}$
$a_n -\frac{(\frac{1 + \sqrt{5}}{2}) ^ {n}}{\sqrt{5}} = \frac{1 - \sqrt{5}}{2} ( a_{n-1} - \frac{(\frac{1 + \sqrt{5}}{2})^{n-1}}{\sqrt{5}} )$
Let: $C_n = a_n - \frac{(\frac{1 + \sqrt{5}}{2}) ^ {n}}{\sqrt{5}}$
$C_1 = a_1 - \frac{(\frac{1 + \sqrt{5}}{2}) ^ {1}}{\sqrt{5}} = \frac{\sqrt{5} - 1}{2\sqrt{5}}$
$C_n = \frac{\sqrt{5} - 1}{2\sqrt{5}} (\frac{1 - \sqrt{5}}{2})^{n-1}$
Then:
$a_n = \frac{(\frac{1 + \sqrt{5}}{2}) ^ {n}}{\sqrt{5}} + C_n \ = \frac{(\frac{1 + \sqrt{5}}{2}) ^ {n}}{\sqrt{5}} + \frac{\sqrt{5} - 1}{2\sqrt{5}} (\frac{1 - \sqrt{5}}{2})^{n-1} \ = \frac{(\frac{1+\sqrt{5}}{2})^{n} - (\frac{1-\sqrt{5}}{2})^{n}}{\sqrt{5}}$