How can I rewrite recursive function as single formula? There is following recursive function
$$
\begin{equation}
    a_n=
    \begin{cases}
      -1, & \text{if}\ n = 0 \\
      1, & \text{if}\ n = 1\\
      10a_{n-1}-21a_{n-2}, & \text{if}\ n \geq 2
    \end{cases}
\end{equation}
$$
I know this can be rewritten as 
$$
a_n=7^n-2\cdot3^n
$$
But how can I reach that statement? I found this problem on some particular website. My skills are not enough to solve such things. Someone told me I have to read about Generating function but it didn't help me. 
I would be thankful if someone explained it to me.
 A: This is called a linear homogeneous recurrence relation. If we look at the recursive case, we find that the coefficient of $a_{n-1}$ is $10$ and the coefficient of $a_{n-2}$ is $-21$. This means the "characteristic polynomial," which is basically the polynomial which tells us what the bases of the explicit formula will be, is like this:
$$x^2-10x+21$$
Notice how we made the leading coefficient $1$, and then took the negative coefficient of $a_{n-1}$, and then took the negative of the coefficient of the $a_{n-2}$. This process is how we find the characteristic polynomial.
Now, if we factor the polynomial:
$$x^2-10x+21=(x-3)(x-7)$$
We find that the roots are $3$ and $7$. This means that the formula must be in the following form:
$$a_n=A\cdot 3^n+B \cdot 7^n$$
Now, we know that this is true for $n=0$ and $n=1$, so we find that:
$$n=0 \implies A\cdot 3^0+B\cdot 7^0=A+B=-1$$
$$n=1 \implies A\cdot 3^1+B\cdot 7^1=3A+7B=1$$
Now, we have a system of linear equations. If we solve this system, we get $A=-2$ and $B=1$, so we get:
$$a_n=-2\cdot 3^n+7^n$$
A: This is a homogeneous linear recurrence relation with constant coefficients. From
$$
a_n = 10 a_{n-1} -21 a_{n-2} 
$$
you can infer the order $d=2$ and the characteristic polynomial:
$$
p(t) = t^2 - 10 t + 21
$$
Calculating the roots:
$$
0 = p(t) = (t - 5)^2 - 25 + 21 \iff
t = 5 \pm 2
$$
this gives the general solution
$$
a_n = k_1 3^n + k_2 7^n
$$
The two constants have to be determined from two initial conditions:
$$
-1 = a_0 = k_1 + k_2 \\
1 = a_1 = 3 k_1 + 7 k_2
$$
This leads to $4 = 4 k_2$ or $k_2 = 1$ and thus $k_1 = -2$.
So we get
$$
a_n = -2 \cdot 3^n + 7^n
$$
A: The way to do this without generating functions is to start with the ansatz that 
$$
a_n = x^n
$$
satisfies the recursion but possibly not the starting points at $n=0$ and $1$.
If we have that solution then any $a_nkx^n$ satisfies the recursion as well.  
And if we have two such solutions $x^n$ and $y^n$ then any linear combination $a_n=kx^n+my^n$ will satisfy the recursion, and we can adjust $k,m$ to fit the starting points.
Well, if $a_n = x^n$ then 
$$
x^n = 10 x^{n-1} - 21x^{n-2} \\
x^2 = 10 x -21 \\
x = 7 \mbox{ or } x=3
$$
So the general solution of the recursion is 
$$
a_n = k\cdot 7^n + m \cdot 3^n
$$
Now plug in $n=0$ and $n=1$ to satisfy the starting points:
$$
k \cdot 7^0 + m \cdot 3^0 = -1 \\
k \cdot 7^1 + m \cdot 3^1 = +1 $$
which gives $$ k = 1 \\m = -2$$
so the particular solution is 
$$
a_n = 7^n -2\cdot 3^n
$$
