This is my first time working through this type of problem and I am looking to see if I have worked it out correctly, thanks!

Solve the reccurence relation $$a_n = 3a_{n-1}+4a_{n-2}, a_0=a_1 = 1$$

First we get the characteristic equation:

$$x^n = 3x^{n-1}+4x^{n-2}$$

Dividing by the smallest we get,

$$x^2=3x+4$$ $$x^2-3x-4 = 0 $$ $$x = 4,-1$$

Using the auxiliary equation we get the general solution:

$$a_n = A_1x^{n+1} + A_2x^{n+1}$$

Using conditions in the equation and our solution for $x$ gives,

$$a_0 = 1 = A_1(4) + A_2(-1) = 4A_1 - A_2$$ $$a_1 = 1 = A_1(4)^2 + A_2(-1)^2 = 16A_1 + A_2$$

Solving for $A_1, A_2$ I got $A_1 = \frac{1}{10}, A_2 = -\frac{3}{5}$

Therefore plugging into the general solution I got,

$$a_n =\left(\frac{1}{10}\right)(4)^{n+1}+\left(-\frac{3}{5}\right)(-1)^{n+1}$$

Did my workings come out correct?

  • 1
    $\begingroup$ Looks good but I would change one equation to $$a_n=A_1x_1^{n+1}+A_2x_2^{n+1}$$ because it's ambiguous as currently written. $\endgroup$ Mar 4 '18 at 18:12
  • $\begingroup$ good catch, thanks for that! $\endgroup$
    – user123
    Mar 4 '18 at 18:15
  • $\begingroup$ Sounds well to me! $\endgroup$ Mar 4 '18 at 18:17
  • 1
    $\begingroup$ An easy way how to prove it is just to check if the values are right. So you have to take your result and calculate $a_0$ and $a_1$ and then try to put your solution into $a_{n-1}$ and $a_{n-2}$ to get your $a_n$. If you get those things right, then your solution has to be right. $\endgroup$
    – CryoDrakon
    Mar 4 '18 at 21:06

Yes it is correct. We can check it with the use of generating functions.
Transform $a_n = 3a_{n-1} + 4a_{n-2}$ to $$a_{n+2} = 3a_{n+1} + 4a_n \tag{1}$$.

Let $A(x) := \sum_{n \geq 0} a_n x^n$ then we get from (1)

$$ \begin{eqnarray*} \sum_{n \geq 0} a_{n+2} x^n &=& 3 \sum_{n \geq 0} a_{n+1} x^n + 4 \sum_{n \geq 0} a_n x^n \\ \Leftrightarrow \frac{A(x)}{x^2} - \frac{1}{x^2} - \frac{1}{x} &=& 3\Big(\frac{A(x)}{x} - \frac{1}{x}\Big) + 4 A(x) \\ \Leftrightarrow A(x) -1 -x &=& 3A(x)x-3x + 4A(x)x^2 \\ \Leftrightarrow A(x) &=& \frac{2x-1}{4x^2+3x-1} \end{eqnarray*} $$ With partial fractions we further obtain that $A(x) = \frac{3}{5(x+1)} + \frac{2}{5(1-4x)}$ and in series representation this is equivalent to $$ A(x) = \sum_{n \geq 0} x^n \Big(\frac{1}{5} 3(-1)^n + \frac{2}{5} 4^n \Big) $$ If we look now at the coefficient of $[x^n]$ in $A(x)$ we see that $$ a_n = \Big(\frac{1}{5} 3(-1)^n + \frac{2}{5} 4^n \Big) $$


Yes it is correct and we can simplify a little as

$$a_n =\frac{2}{5}4^{n}+\frac{3}{5}(-1)^{n}$$

  • 2
    $\begingroup$ Can't this be better as a comment? $\endgroup$ Mar 4 '18 at 18:20
  • $\begingroup$ The OP is asking for correctness of the solution, I’ve precisely answered to it and given an hint to simplify the final expression. What is the problem? $\endgroup$
    – user
    Mar 4 '18 at 18:24

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.