# How do you solve a linear recurrence relation for $a_{n}$ given the solution

I'm a beginner who is starting to learn about linear recurrence relations. I've just come across a problem where I'm not sure how to progress.

Going off of my notes linear recurrence was solved using this form

$$a_{n}= C_{1}a_{n-1}+C_{2}a_{n-2}$$

where the C's are constants

that form is then manipulated and used with the quadratic formula ... etc..

My problem is since this method uses $$a_{n-1}$$ and $$a_{n-2}$$, I'm not sure how to solve a linear recurrence problem for a formula that doesn't have those.

For reference here is the problem

$$a_{n} = 2^{n}(1 + (−2)^{n})$$

What is the method used to solve these types of recurrence problems?

After some clarification I realized that the problem is asking for me to find the linear recurrence of the form $$a_{n}= C_{1}a_{n-1}+C_{2}a_{n-2}$$, but I'm still not sure how to do this

• There is no recurrence. – Nap D. Lover Apr 7 '19 at 19:58
• If $a_n$ is defined in terms of $n$ then that is it. Maybe you can express it in nicer ways but recursion requires to express it as $a_n=f(a_{n-1})$. – Nap D. Lover Apr 7 '19 at 20:00
• here is the entire question in case i left out some crucial information. Find a linear recurrence relation for an that satisfies the formula $a_{n} = 2^{n}(1 + (−2)^{n})$ State the initial conditions for a0 and a1. Does this change anythinh? – Brownie Apr 7 '19 at 20:00
• both are defined by the formula provided its given for $n=0,1,2,...$, just compute them: $a_0=2$ and $a_1=-2$. – Nap D. Lover Apr 7 '19 at 20:04
• Oh sorry, actually it seems they want you to try to re-express the given formula as a recurrence relation, i.e. to find the coefficients $C$ such that $a_n=C_1a_{n-1} + C_2 a_{n-2}$ where $a_n$ is as given. It is not immediate to me but you should be able to play around and solve for $C$ if its homework. – Nap D. Lover Apr 7 '19 at 20:07

As you have stated $$a_{n} = 2^{n}(1 + (−2)^{n})=2^n+(-4)^n$$ So the recurrence relation must have an auxiliary equation given by $$(r-2)(r+4)=0$$ in order to have the solutions $$r=2,-4$$. Expanding this gives $$r^2+2r-8=0$$ $$r^2=-2r+8$$ Hence the original recurrence relation is $$a_n=-2a_{n-1}+8a_{n-2}$$
• Alright so if I'm following your solution correctly. Step 1 you distributed the $2^{n}$. Step 2 i'm a little fuzzy on the reasoning as to why r is used but I can see what you did. Step 3 you basically found the quadratic formula that has the roots 2 and -4, and rewrote it. Step 4, you used $a_{n}= C_{1}a_{n-1}+C_{2}a_{n-2}$ to rewrite it in the correct form? – Brownie Apr 7 '19 at 20:42
• Yes, any recurrence relation of the form $a_n=C_1a_{n-1}+C_2a_{n-2}$ has an auxiliary equation $r^2-C_1r-C_2=0$ which (if having two unique solutions) gives $r_0,r_1$ for the solution $a_n=Ar_0^n+Br_1^n$. Working backwards allows one to find the original relation. – Peter Foreman Apr 7 '19 at 20:45
• Sorry if I misunderstood, but then shouldn't it be $(r^{2} -2)$ instead of (r-2) – Brownie Apr 7 '19 at 20:48
• If $a_n$ is given by $a_n=Ar_0^n+Br_1^n$ for constants $A,B$ then the values $r_0,r_1$ are solutions to the equation $r^2-C_1r-C_2=0$. One can rewrite this as $(r-r_0)(r-r_1)=0$ for the solutions to the equation given. I then expanded this and rearranged to give $C_1,C_2$ explicitly. – Peter Foreman Apr 7 '19 at 20:51