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$ – user5713492 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$ – Mostafa Ayaz 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$ – HeatTheIce Mar 4 '18 at 21:06

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$ – Jaideep Khare 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$ – gimusi Mar 4 '18 at 18:24

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


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.