Recursively given sequence question about changing the sequence with exponent function We have a sequence given by:
$$a_1 = 1 \\ a_2 = b \\
a_{n+2}=a_{n+1}+a_n$$
We need to find the limit of the sequence. The procedure of getting the solution is that we $a_n = p^n$ and then somehow solve the equation $p^{n+2}=\frac{1}{3}p^n+\frac{2}{3}p^{n+1}\implies p^2 - \frac{2}{3}p-\frac{1}{3} = 0$
For this quadratic equation there are two solutions, that we input:
$$a_1 = A - \frac{1}{3}B = 1, a_2 = A +\frac{1}{9}B = b \implies A = \frac{1+3b}{4}, B = \frac{9(b-1)}{4}$$
However I do not understand this process. Why can we say that $a_n = p^n$ and what follows from it. Where can we use this technique?
 A: I guess what you are asking is how the "guess" $a_n = p^n$ can be justified, i.e. why is this the way to proceed and why is it complete, i.e. it produces all solutions.
Without having to develop a theory of difference equations from scratch, we can use mighty results from linear algebra. Transform your difference equation $a_{n+2}=a_{n+1}+a_n$ into a vector equation as follows:
$$
\left ( \begin{matrix}
    a_{n+2}\\a_{n+1}
   \end{matrix} \right ) = \left ( \begin{matrix}
    1&1\\1&0
   \end{matrix} \right )
\left ( \begin{matrix}
    a_{n+1}\\a_{n}
   \end{matrix} \right )
$$
Now writing for short the vector $
x_n = 
\left ( \begin{matrix}
    a_{n+1}\\a_{n}
   \end{matrix} \right )
$ and the matrix $A  = \left ( \begin{matrix}
    1&1\\1&0
   \end{matrix} \right )
$ we have $x_{n+1} = A \cdot x_n$ and hence $x_{n+1} = A^{n} \cdot x_1$. Your  $
x_1 = 
\left ( \begin{matrix}
    a_{2}\\a_{1}
   \end{matrix} \right )
=\left ( \begin{matrix}
    b\\1
   \end{matrix} \right )
$ is obviously a known start vector.
So the problem has been transferred to obtaining the power of a matrix $A$. Now the linear algebra results come in. Let $u_1$ and $u_2$ be the two eigenvectors of $A$ with corresponding eigenvalues $\lambda_1$ and $\lambda_2$, then the eigenvectors form a basis and you can write any initial condition as $x_1 = c_1 u_1  + c_2 u_2$ with constants $c_1$ and $c_2$. Then you have  $x_{n+1} = A^{n} \cdot x_1 = c_1 \lambda_1^n u_1  + c_2 \lambda_2^n u_2$.
So here you have the answer to the above question. Since taking the first component of $x_{n+1}$, which is $a_{n+2}$, gives    $a_{n+2} = d_1 \lambda_1^n   + d_2 \lambda_2^n$ with constant coefficients $d_1$ and $d_2$ depending on the initial conditions and on $A$. So we can deduce:
a) the ansatz $a_{n} = b_1 \lambda_1^n   + b_2 \lambda_2^n$ is correct and complete.
b) the $\lambda_1$ and  $\lambda_2$ in this ansatz are the eigenvalues of $A$.
c) the constants  $b_1$ and  $b_2$ in this ansatz have to be matched to the initial conditions.
So it was not by chance or by some phenomenal genius that a power law was "guessed" in the beginning. Also, the characteristic equation does not  appear from out of the blue, but is exactly what is needed to find the eigenvalues of $A$.
Obviously, this derivation generalizes to homogenous linear difference equations of any finite degree.
A: Here is some presentation without matrices, it is easy to understand for a recurrence with only two terms, but keep in mind that the generalization with many terms is easier to handle with linear algebra theory as in Andreas's answer.

*

*Let start with the simple case $x_{n+1}=ax_n$
It can be solved by induction to $x_n=a^nx_0$

*

*Now with $x_{n+1}=ax_n+bx_{n-1}$
Recall that the quadratic equation $$r^2-sr+p=0$$ has roots whose sum is $s$ and product $p$.
So let's call $r_1,r_2$ the roots of $r^2-ar-b=0$
We can rewrite our equation $x_{n+1}=(r_1+r_2)x_n-r_1r_2x_{n-1}\iff (\overbrace{x_{n+1}-r_1x_n}^{y_{n+1}})=r_2(\overbrace{x_n-r_1x_{n-1}}^{y_n})$
By first case then $$y_{n+1}=r_2y_n\iff y_n=C_2{r_2}^n$$
And since equation is linear, a solution is the sum of a general solution of homogeneous equation and a particular solution with RHS.
In this case $x_{n+1}-r_1x_n=\overbrace{C_2{r_2}^n}^{\text{RHS}}$
Solves to $x_n=C_1{r_1}^n+y_n=C_1{r_1}^n+C_2{r_2}^n$
Rem: here I assumed $r_1\neq r_2$, when they are equal the particular solution is different, but not let's compilate too much for the moment

*

*For the general case $x_{n+1}=\sum\limits_{i=1}^k a_ix_{n+1-i}$
We can proceed similarly using Newton's identities to express the $a_i$ in terms of the roots $r_i$ and rearrange the terms to make an expression $y_{n+1}=r_ky_n$ and solve it recursively like in the case with $k=2$.
This is why we generally solve the characteristic equation $r^k=\sum\limits_{i=1}^{k}a_ir^{i-1}$ whose roots are $r_i$.
And that we have a solution $x_n=C_1{r_1}^n+\cdots+C_k{r_k}^n$
This at least is in the ideal case where all roots are distinct, the complications arise when some roots have higher multiplicity, in which case the general solution for a root of multiplicity $m$ is $$(\alpha_0+\alpha_1n+\cdots+\alpha_{m-1}n^{m-1})r^n\quad\text{instead of}\quad (\alpha_0\,r^n)$$
