2
$\begingroup$

How to solve this recurrence relation in closed form? $$F(n) = aF(n-1) + bF(n-2) + cF(n-3) + dF(n-4)$$

I know how to solve recurrence relations for less than four calls by solving the characteristic polynomial. But are there other ways so that i don't have to solve the 4 degree characteristic polynomial to solve this recurrence relation?

$\endgroup$
4
  • $\begingroup$ so i just have to solve the polynomial equation ? $\endgroup$ – Zabir Al Nazi Jul 4 '15 at 22:24
  • $\begingroup$ You can solve it numerically, that gives some information, certainly. Depends upon what you hope to learn from the information. $\endgroup$ – Will Jagy Jul 4 '15 at 22:33
  • $\begingroup$ hmmm. yeah thanks :-) $\endgroup$ – Zabir Al Nazi Jul 4 '15 at 22:57
  • $\begingroup$ @znabil: Will Jagy is lying ;-). There is always a way of solving recurrence relations using backward iteration. However only in few cases(for example in the case when the coefficients are time independent) the resulting sums can be brought into closed form. $\endgroup$ – Przemo Feb 22 '17 at 14:29
0
$\begingroup$

One of the ways of solving such recurrences is backward iteration. Fix the value of $n\ge 1$. Note that the solution will be a sum of product of quantities $a$, $b$, $c$ and $d$ followed by $F_\xi$ where $\xi=0,\cdots,3$. Note that each $a$ diminishes the time index $n$ by unity, each $b$ diminishes it by a two, each $c$ by three and finally each $d$ by a four. Let us denote the number of $b$'s , $c$'s and $d$'s in a sequence as $P$, $q$ and $r$ respectively and let the time index run backwards from the left to the right. Luckily the coefficients do not depend on the time index so all what we need to count the number of strictly ordered sequences of length $P+q+r-1$ (note that the last $d$ quantity in the sequence is replaced by $F_{\xi+1}$) bounded from the below by unity and from the above by $n-\xi-P-2 q-3 r-1$. Therefore we have: \begin{equation} F_{n+2} = \sum\limits_{r=0}^n \sum\limits_{q=0}^n \sum\limits_{P=0}^n 1_{n-\xi \ge 2P + 3 q+ 4 r}\frac{(P+q+r)!}{P! q! r!} \binom{n-\xi-P-2 q-3r-1}{P+q+r-1} a^{n-\xi-2 P-3 q-4 r} b^P c^q d^r \cdot F_{\xi+1} \end{equation} for $\xi=1$ only. In this way we have obtained one ''mode'',i.e. one solution. The other three linearly independent solutions can be obtained using similar reasoning except that certain boundary conditions have to be taken into account. We will complete this later on.

$\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.