How can I rewrite recursive function as single formula?

There is following recursive function

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

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.

• This is called a linear recurrence. Jun 24, 2016 at 22:06

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

• Thank you. All is clear now. Jun 24, 2016 at 22:34
• An ansatz is an assumed form for a mathematical statement that is not based on any underlying theory or principle. Jun 25, 2016 at 10:17
• @StevenGregory Also known as an (educated) guess :-)
– Ant
Jun 25, 2016 at 11:05

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

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

• Thank you for answer. Now I understand. Jun 24, 2016 at 22:35