I want to know, is there any other way to find the $n$-th term of recursive sequence without the direct method or matrix exponentiation? Please tell me if you know. Thank you very much.
Example: $A_n = 3A_{n-1} + 4A_{n-2}, \; A_0=3, \; A_1=2$ - I want to know the method to find $A_n$ without the direct method or use matrix exponentiation.
Consider the following recursion:
$$x_{n+k} = a_{k-1} x_{n+k-1} + \dots + a_0 x_n$$
with $x_0, \dots, x_{k-1}$ and $a_0, \dots, a_{k-1}$ given.
The first step is to solve the associated algebraic equation obtained by formally replacing $x_{n-i}$ in the recurrence formula by $r^i$:
$$r^k = a_{k-1} r^{k-1} + \dots + a_1 r + a_0 .$$
If $r_1, \dots, r_p$ are the roots, each one with multiplicity $m_1, \dots, m_p$, then the general solution of the recurrence is
$$x_n = \sum _{i=1} ^p \sum _{j=1} ^{m_p} \alpha_{ij} \ n^{j-1} r_i ^n .$$
In order to find out the values of the coefficients $\alpha_{ij}$, solve the $k$-dimensional linear system
$$\begin{cases} x_0 &=& \sum _{i=1} ^p \sum _{j=1} ^{m_p} \alpha_{ij} \ n^{j-1} \\ x_1 &=& \sum _{i=1} ^p \sum _{j=1} ^{m_p} \alpha_{ij} \ n^{j-1} r_i ^1 \\ \vdots \\ x_{k-1} &=& \sum _{i=1} ^p \sum _{j=1} ^{m_p} \alpha_{ij} \ n^{j-1} r_i ^{k-1} . \end{cases}$$
Of course, solving a general $k$-th degree algebraic equation is not going to be easy...