Please help with solving the recurrences to get closed form formulas for $a_n$, $b_n$ and $c_n$. Be sure to clearly label the characteristic equation, the roots of the characteristic equation, the general solution and the specific solution.

$a_n=a_{n-1}+2a_{n-2}$ for $n\geq 2$, $a_0=2$ ,$a_1=-5$

$b_n=8b_{n-1}+16b_{n-2}$ for $n\geq 2$, $b_0=-3$, $b_1=-4$

$c_n=3c_{n-1}+6c_{n-2}-24c_{n-3}+24c_{n-4}$ for $n\geq 3$ $c_0=-2$, $c_1=10$, $c_2=-10$, $c_3=54$

This topic is a little hard for me. Do I just plug in $a_0$ and $a_1$ into the equation? Any tips will be helpful. Thank you.

  • $\begingroup$ Well, start by finding the characteristic equations for each of those recurrences. What equations do you get? $\endgroup$ – Tobias Kildetoft Apr 1 '13 at 17:32
  • 1
    $\begingroup$ @Cheal: Thank you for improving your question. Though in the future, you should edit your question when you want to make a change, not delete it and repost it. $\endgroup$ – Zev Chonoles Apr 1 '13 at 17:33

Rewrite the first equation as $a_n - 2 a_{n-1} = -\left( a_{n-1} - 2 a_{n-2} \right)$. This has the form $g_n = -g_{n-1}$ with the general solution $g_n = (-1)^{n-1} g_1$. Therefore $$ a_n - 2 a_{n-1} = (-1)^{n-1} (a_1 - 2 a_0) = 9 (-1)^n $$ Let $b_n = 2^{-n} a_n$. Multiplying the above recurrence equation with $2^{-n}$ we get $$\begin{eqnarray} b_n - b_{n-1} = 9 (-2)^{-n} \implies b_n &=& b_0 + 9 \sum_{k=1}^n (-2)^{-k} \\ &=& b_0 + 9 \frac{-1/2}{1-(-1/2)} (1 - (-2)^{-n}) \\ &=& -1 + 3 (-1)^n 2^{-n} \end{eqnarray} $$ Hence $$ a_n = 2^n b_n = 3 (-1)^n - 2^n $$

Generally, one solves such recurrence equations using trick with linearity. Suppose a particular solution to your recurrence has a form $a_n = q^n$. Substituting this into the recurrence you find $q^{n+2} = q^{n+1} + 2 q^{n}$, implying that $q$ must satisfy $q^2 = q + 2$ which has two roots, $q=2$ and $q=-1$. Since the recurrence equation is linear, general solution is a linear combination of these two solutions: $$ a_n = c_1 (-1)^n + c_2 2^{n} $$ Initial conditions determine $c_1$ and $c_2$.

You are now well equipped to tackle the remaining two problems by yourself.

  • $\begingroup$ From the formulation, it seems that the OP should be familiar with the characteristic polynomial (he writes equation) and the general form of a solution to problems like these. It would be easier to give good hints if you let him respond to the comments first. $\endgroup$ – Tobias Kildetoft Apr 1 '13 at 18:11
  • $\begingroup$ This is elementary than mine and thus better than mine. +1 $\endgroup$ – Orat Apr 1 '13 at 18:19

Define formal power series $g \in \mathbb{R}[[x]]$ by $$g(x) = \sum_{n = 0}^\infty a_n x^n.$$ From the recurrence condition and initial conditions, $$g(x) - xg(x) - 2x^2g(x) = 2 -7x$$ and solve this equation for $g(x)$ gives $$g(x) = \frac{2 -7x}{1 - x - 2x^2} = \frac{1}{2x - 1}+ \frac{3}{x + 1}. $$ Therefore, the general term is given by its derivative: $$ a_n = \frac{1}{n!}\frac{d^n g}{dx^n}(0) = \frac{(-2)^n}{(2 \cdot 0 - 1)^{n + 1}} + \frac{(-1)^n 3}{(0 + 1)^{n + 1}} = -2^n + (-1)^n 3.$$

Rest of your questions can be done with the same method.

  • $\begingroup$ This is clearly not the way the OP was intended to solve this, given the formulation of the question. You might be able to provide better help if you wait until the OP has responded to the comments. $\endgroup$ – Tobias Kildetoft Apr 1 '13 at 18:07
  • $\begingroup$ @TobiasKildetoft Absolutely. I just forgot a solution like user40314 gives. To Cheal Min: I strongly recommend the user40314's solution. It's standard one. If you're interested in a solution like I did, google "generating function" for example. $\endgroup$ – Orat Apr 1 '13 at 18:17

$a_n=a_{n-1}+2a_{n-2}$, rewrite it as $a_n-a_{n-1}-2a_{n-2}=0$, then the characteristic equation is $r^2-r-2=0\implies (r-2)(r+1)=0\implies$ $r=2$ or $r=-1$, so the general solution is $a_n=A(2)^n+B(-1)^n$. For the particular solution, since $a_0=2$ and $a_1=-5$, solve the equations: \begin{equation} 2=A(2)^0+B(-1)^0\\ -5=A(2)^1+B(-1)^1 \end{equation} then you get $A=-1$ and $B=3$, therefore $a_n=(-1)(2)^n+3(-1)^n$. You can solve the rest by using the same method

  • $\begingroup$ It's wrong. $r^2 - r - 2$ is equal to $(r - 2)(r + 1)$, not $(r + 2)(r - 1)$. See user40314's answer. $\endgroup$ – Orat Apr 2 '13 at 6:33
  • $\begingroup$ Sorry for the careless calculation, it's been corrected, and thanks to @Taro. $\endgroup$ – user62453 Apr 2 '13 at 15:53

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.