0
$\begingroup$

I have the following non-homogenous recurrence relation and I'm trying to solve it using characteristics roots method :

$a_n = 10a_{n-1} -37a_{n-2} + 60a_{n-3} -36a_{n-4} +4$ for $n \ge4$ and $ a_3 = a_2 = a_1 = a_0 = 1$

I found the particular solution p =1 and I'm trying to solve the homogenous equation when $a_n = r^n$ but it will be an equation of the fourth order !!My question is whether this is the right path or there's any shortcut to solve this problem?

$\endgroup$
1
$\begingroup$

We have $$(a_n+1)-10(a_{n-1}+1)+37(a_{n-2}+1)-60(a_{n-3}+1)+36(a_{n-4}+1)=0$$

Set $a_n+1=b_n$ and use this

$\endgroup$
  • $\begingroup$ Why you added 1 to each an? $\endgroup$ – Lisa Apr 14 '14 at 5:01
  • $\begingroup$ @Lisa, to balance out $4=1-10+37-60+36$ $\endgroup$ – lab bhattacharjee Apr 14 '14 at 5:03
  • $\begingroup$ But how will you solve the fourth ordered equation? $\endgroup$ – Lisa Apr 14 '14 at 5:04
  • $\begingroup$ @Lisa, fortunately, the roots are $$3,3,2,2$$ $\endgroup$ – lab bhattacharjee Apr 14 '14 at 5:06
  • $\begingroup$ How could you know? $\endgroup$ – Lisa Apr 14 '14 at 5:06
0
$\begingroup$

Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write the recurrence without subtractions in indices: $$ a_{n + 4} = 10 a_{n + 3} - 37 a_{n + 2} + 60 a_{n + 1} - 36 a_n + 4 $$ Multiply by $z^n$, sum over $n \ge 0$ and recognize sums like: $$ \sum_{n \ge 0} a_{n + k} z^n = \frac{A(z) - a_0 - a_1 z - \ldots - a_{k - 1} z^{k - 1}}{z^k} $$ to get: $$ \frac{A(z) - 1 - z - z^2 - z^3}{z^4} = 10 \frac{A(z) - 1 - z - z^2}{z^3} - 37 \frac{A(z) - 1 - z}{z^2} + 60 \frac{A(z) - 1}{z} - 36 A(z) + 4 \frac{1}{1 - z} $$ Surprisingly it turns out that: $$ A(z) = \frac{1}{1 - z} $$ so that $$ a_n = 1 $$

maxima did the heavy lifting.

$\endgroup$

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.