How can I rewrite recursive function as single formula?

Question

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.

Answer 1

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 $$

Answer 2

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$$

Answer 3

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 $$