edited by
394 views
0 votes
0 votes

Some linear recurrence relations that do not have constant coefficients can be systematically solved. This is the case for recurrence relations of the form $f (n)a_{n} = g(n)a_{n-1} + h(n).$ Exercises $48–50$ illustrate this.

  1. Show that the recurrence relation $f (n)a_{n} = g(n)a_{n-1} + h(n),$ for $n \geq 1,$ and with $a_{0} = C,$ can be reduced to a recurrence relation of the form $b_{n} = b_{n-1} + Q(n)h(n),$ where $b_{n} = g(n + 1)Q(n + 1)a_{n},$ with $Q(n) = \dfrac{(f (1)f (2) \dots f (n - 1))}{(g(1)g(2) \dots g(n))}.$
  2. Use part $(A)$ to solve the original recurrence relation to obtain $a_{n} = \dfrac{C +\displaystyle{} \sum_{i = 1}^{n}Q(i)h(i)}{g(n + 1)Q(n + 1)}$
edited by

1 Answer

0 votes
0 votes

The following is based on the solution book and you can try to get one.

  1. Both sides multiply $Q(n)$ and use $f(n)Q(n)=g(n+1)Q(n+1)$
  2. By induction, $b_n=\sum_{i=1}^n Q(i)h(i)+C$, then use $b_n=g(n+1)Q(n+1)a_n$.

Related questions