2
$\begingroup$

What would be the solution to $a_n = 7a_{n−2} + 6a_{n−3}$ with $a_0 = 9$, $a_1 = 10$, and $a_2 = 32$

I can find it for a specific value of (n), but not for just a general solution. Thanks!

$\endgroup$
  • $\begingroup$ Still open for a non-generating function answer! $\endgroup$ – tekman22 Apr 15 '13 at 16:59
  • $\begingroup$ Ok, done. :) The generating function approach requires solving exactly the same characteristic function, but its advantage is apparently that you don't have to solve a system of equations to account for the initial conditions. $\endgroup$ – ShreevatsaR Apr 15 '13 at 17:04
  • $\begingroup$ @ShreevatsaR just want to make sure that these two answers don't contradict each other - mind giving this a look? gyazo.com/bf0f0684693bcb9a2b3fb7c1590beeb9 Thanks! $\endgroup$ – tekman22 Apr 15 '13 at 17:10
  • $\begingroup$ I've replied to the comment on my answer: that linked image is wrong. $\endgroup$ – ShreevatsaR Apr 15 '13 at 17:15
2
$\begingroup$

By the general theory of such linear recurrence relations, the solutions to $a_n = 7a_{n-2} + 6a_{n-3}$ will all be of the form $a_n = c_1 r_1^n + c_2r_2^n + c_3r_3^n$, where $r_1, r_2, r_3$ are all solutions to $r^n = 7r^{n-2} + 6r^{n-3}$, i.e. to $r^3 = 7r + 6$. This is called the characteristic equation.

It turns out (or you can find by trial and error) that the solutions to the characteristic equation are $-1$, $-2$, and $3$.

So we have $a_n = c_1(-1)^n + c_2(-2)^n + c_33^n$. Putting your initial conditions given, namely $a_0 = 9$, $a_1 = 10$, and $a_2 = 32$, we get the equations

$$\begin{aligned} c_1 + c_2 + c_3 &= 9 \\ -c_1 - 2c_2 + 3c_3 &= 10 \\ c_1 + 4c_2 + 9c_3 &= 32 \end{aligned}$$ solving which gives $c_1 = 8$, $c_2 = -3$, and $c_3 = 4$. So $a_n = 8(-1)^n - 3(-2)^n + 4(3)^n$.

$\endgroup$
  • $\begingroup$ Hmm..are you sure this is right? $\endgroup$ – tekman22 Apr 15 '13 at 17:08
  • $\begingroup$ This seems to contradict this method: gyazo.com/bf0f0684693bcb9a2b3fb7c1590beeb9 $\endgroup$ – tekman22 Apr 15 '13 at 17:08
  • $\begingroup$ @jtm22: Yes I'm sure this is right. Just put $n = 3$ to check: the recurrence relation $a_n = 7a_{n-2} + 6a_{n-3}$ gives $a_3 = 7a_1 + 6a_0 = 7(10) + 6(9) = 124$. My expression $a_n = 8(-1)^n - 3(-2)^n + 4(3)^n$ gives $a_3 = -8 - 3(-8) + 4(27) = 124$, while the linked (wrong) solution $a_n = 3 + 5(2^n) + (-3)^n$ gives $a_3 = 3 + 5(8) + (-27) = 16$, which is wrong. $\endgroup$ – ShreevatsaR Apr 15 '13 at 17:14
  • $\begingroup$ Makes sense. Thank you! $\endgroup$ – tekman22 Apr 15 '13 at 17:15
  • $\begingroup$ I just checked it with a spreadsheet and it solves the problem correctly. $\endgroup$ – Ross Millikan Apr 15 '13 at 17:19
2
$\begingroup$

Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, and write the recurrence as: $$ a_{n + 3} = 7 a_{n + 1} + 6 a_n \quad a_0 = 9, a_1 = 10, a_2 = 32 $$ By properties of ordinary generating funtions: $$ \frac{A(z) - a_0 - a_1 z - a_2 z^2}{z^3} = \frac{A(z) - a_0}{z} + 6 A(z) $$ Writing as partial fractions: $$ A(z) = 4 \cdot \frac{1}{1 - 3 z} - 3 \cdot \frac{1}{1 + 2 z} + 8 \cdot \frac{1}{1 + z} $$ Expanding the various geometric series: $$ a_n = 4 \cdot 3^n - 3 \cdot (-2)^n + 8 \cdot (-1)^n $$

$\endgroup$
  • $\begingroup$ I am not familiar with generating functions, although you seem to live by them vonbrand! Haha, could we use another way possibly? $\endgroup$ – tekman22 Apr 15 '13 at 16:53
  • $\begingroup$ @jtm22, there certainly are other ways. This is just by far the simplest. $\endgroup$ – vonbrand Apr 15 '13 at 16:54
  • $\begingroup$ What is the characteristic equation? $\endgroup$ – tekman22 Apr 15 '13 at 16:54
  • $\begingroup$ @jtm22, $(1 - 3 z) (1 + 2 z) (1 + z)$ $\endgroup$ – vonbrand Apr 15 '13 at 16:56
  • $\begingroup$ Thanks. You wouldn't mind solving it with regular characteristic equations, though, would you? $\endgroup$ – tekman22 Apr 15 '13 at 16:59

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.