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

  • 1
    $\begingroup$ There is no recurrence. $\endgroup$ – Nap D. Lover Apr 7 '19 at 19:58
  • 1
    $\begingroup$ 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})$. $\endgroup$ – Nap D. Lover Apr 7 '19 at 20:00
  • $\begingroup$ 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? $\endgroup$ – Brownie Apr 7 '19 at 20:00
  • 1
    $\begingroup$ both are defined by the formula provided its given for $n=0,1,2,...$, just compute them: $a_0=2$ and $a_1=-2$. $\endgroup$ – Nap D. Lover Apr 7 '19 at 20:04
  • 1
    $\begingroup$ 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. $\endgroup$ – 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}$$

  • $\begingroup$ 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? $\endgroup$ – Brownie Apr 7 '19 at 20:42
  • 2
    $\begingroup$ 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. $\endgroup$ – Peter Foreman Apr 7 '19 at 20:45
  • $\begingroup$ Sorry if I misunderstood, but then shouldn't it be $(r^{2} -2)$ instead of (r-2) $\endgroup$ – Brownie Apr 7 '19 at 20:48
  • 2
    $\begingroup$ 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. $\endgroup$ – Peter Foreman Apr 7 '19 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.