2

So here i have this non homogeneous recurrence relation i need to solve: $$a_{n}=12a_{n-2}+16a_{n-3}+9\cdot 4^{n}+81n,$$ where $a_{0}=0$, $a_{1}=1$ $a_{2}=98$. I'm confused at the homogeneous relation part of this relation. What's the characteristic of this type of homogeneous relation? I am planning to solve this like solving a second order recurrence, but is there any simpler way to deal with this?

David
  • 82,662
Doh
  • 21

2 Answers2

1

Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write the recurrence with no index subtractions: $$ a_{n + 3} = 12 a_{n + 1} + 16 a_n + 576 \cdot 4^n + 81 n + 243 $$ The resulting recurrence is now valid for $n \ge 0$ ( no terms for negative index allowed originally). Multiply by $z^n$, sum over $n \ge 0$, recognize some sums: \begin{align} \sum_{n \ge 0} a_{n + r} z^n &= \frac{A(z) - a_0 - a_1 z - \ldots - a_{r - 1} z^{r - 1}}{z^r} \\ \sum_{n \ge 0} z^n &= \frac{1}{1 - z} \\ \sum_{n \ge 0} n z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \\ &= \frac{z}{(1 - z)^2} \end{align} and get: $$ \frac{A(z) - z - 98 z^2}{z^3} = 12 \frac{A(z)}{z} + 16 A(z) + 576 \frac{1}{1 - 4 z} + 81 \frac{z}{(1 - z)^2} + 243 \frac{1}{1 - z} $$ Written as partial fractions: $$ A(z) = \frac{1}{(1 - 4 z)^2} - \frac{1}{1 - 4 z} + \frac{6}{(1 + 2 z)^2} + \frac{14}{1 + 2 z} - \frac{3}{(1 - z)^2} - \frac{5}{1 - z} $$ Use geometric series and the generalized binomial theorem to read off the coefficients: $$ \binom{-m}{k} = (-1)^k \binom{m + k - 1}{m - 1} $$ Note in particular that: $$ \binom{-2}{n} = (-1)^n (n + 1) $$ So: \begin{align} a_n &= (n + 1) \cdot 4^n - 4^n + 6 (n + 1) \cdot (-2)^n + 14 \cdot (-2)^n - 3 (n + 1) - 5 \\ &= n \cdot 4^n + (6 n + 20) \cdot (-2)^n - 3 n - 8 \end{align}

vonbrand
  • 27,812
  • Wow, thanks. If possible could you explain your method a bit in depth? – Doh Apr 29 '14 at 12:48
  • @Doh, please read it through and ask if you have some specific step that isn't clear. To use this is is useful to have a catalogue of "known series" and operations on such, check e.g. Wilf's "generatingfunctionology" – vonbrand Apr 29 '14 at 12:52
  • ah ok. I'm a bit confused at the generating function. Why does it look a bit odd? Some of the generating function i often look at in is a bit more straight forward – Doh Apr 29 '14 at 12:59
  • @Doh, what do you find odd? Yes, the recurrence is quite complex, and so the generating function turns out a bit more of a mess. Other than that, I find it quite straightforward. – vonbrand Apr 29 '14 at 13:16
  • Ah ok. It just looked a bit messy to me that's all. Thanks. – Doh Apr 29 '14 at 13:19
  • @Doh, note that I had the sign of 2 in the solution wrong. – vonbrand Apr 29 '14 at 13:21
  • So it should be n.4^n + (6n + 20).2^n - 3n - 8 instead? – Doh Apr 29 '14 at 14:05
  • @Doh, no. I found out and fixed it. It should be right now. Check anyway, please. – vonbrand Apr 29 '14 at 16:51
  • Alright, just checked it. Thanks :D I have a follow up question related to this recurrence relation. Would you mind taking a look at it? – Doh Apr 30 '14 at 11:39
  • @Doh, post it as a separate question (citing this one, if appropiate) – vonbrand Apr 30 '14 at 15:57
  • Ah, I just checked. It was a seperated question so nvm. However i reread this question again and noticed that another constraint of the recurrence relation is n >= 3. Does it make your answer any different? – Doh May 01 '14 at 03:00
  • @Doh, neither recurrence uses $a_n$ for $n<0$. Answer edited to clarify this – vonbrand May 01 '14 at 07:14
0

It's best to write this with all the $a_k$ terms on one side: $$a_{n}-12a_{n-2}-16a_{n-3}=9\times4^{n}+81n\ .$$ The homogeneous part is $$a_{n}-12a_{n-2}-16a_{n-3}=0\ ,$$ and you solve this exactly as for a second-order recurrence. The only difference is that as this one is third order, your characteristic equation will be cubic instead of quadratic, and therefore possibly harder to solve.

David
  • 82,662