Question

a) Show that the recurrence relation

\(f(n){a_n} = g(n){a_{n - 1}} + h(n),\)

for\(n \ge 1\), and with\({a_0} = C\), can be reduced to a recurrence relation of the form.

\({{\bf{b}}_n} = {{\bf{b}}_{n - 1}} + {\bf{Q}}\left( {\bf{n}} \right){\bf{h}}\left( {\bf{n}} \right)\), where\({{\bf{b}}_n} = {\bf{g}}\left( {{\bf{n}} + {\bf{1}}} \right){\rm{ }}{\bf{Q}}\left( {{\bf{n}} + {\bf{1}}} \right){\rm{ }}{{\bf{a}}_n}\), with

\(Q(n) = (f(1)f(2) \cdots f(n - 1))/(g(1)g(2) \cdots g(n)).\)

b) Use part (a) to solve the original recurrence relation to obtain

\({a_n} = \frac{{C + \sum\limits_{i = 1}^n Q (i)h(i)}}{{g(n + 1)Q(n + 1)}}.\)

Short answer

(a) The given recurrence relation can be reduced to a recurrence relation form is:$b_n=b_{n-1}+Q\left(n\right)·h\left(n\right)$

(b) The relation obtained is:

$a_n=\frac{C+{\sum }_{i=1}^{n}Q\left(i\right)·h\left(i\right)}{g(n+1)Q(n+1)}$

Step-by-step solution

Linear Homogeneous Recurrence Relations with Constant Coefficients definition

Suppose that\(\left\{ {{a_n}} \right\}\)satisfies the linear non-homogeneous recurrence relation

\({a_n} = {c_1}{a_{n - 1}} + {c_2}{a_{n - 2}} + \cdots + {c_k}{a_{n - k}} + F(n),\)Where\({c_1},{c_2}, \ldots ,{c_k}\)are real numbers, and

\(F(n) = \left( {{b_f}{n^t} + {b_{f - 1}}{n^{t - 1}} + \cdots + {b_1}n + {b_0}} \right){s^n},\)Where\({b_0},{b_1}, \ldots ,{b_t}\)and\(s\)are real numbers.

When\(s\)is not a root of the characteristic equation of the associated linear homogeneous recurrence relation, there is a particular solution of the form\(\left( {{p_t}{n^t} + {p_{t - 1}}{n^{t - 1}} + \cdots + {p_{1n}} + {p_0}} \right){s^n}\)

When\(s\)is a root of this characteristic equation and its multiplicity is\(m\), there is a particular solution of the form:\({n^m}\left( {{p_t}{n^t} + {p_{t - 1}}{n^{t - 1}} + \cdots + {p_1}n + {p_0}} \right){s^n}.\)

Use Recurrence Relations for part (a) 

(a).

\(f(n){a_n} = g(n){a_{n - 1}} + h(n)n \ge 1{a_0} = C\)

Let \({b_n} = g(n + 1)Q(n + 1){a_n}\) and \(Q(n) = \frac{{f(1) \cdot f(2) \cdot \ldots \cdot f(n - 1)}}{{g(1) \cdot g(2) \cdot \ldots \cdot g(n)}}\)

\(\begin{aligned}{b_n} &= g(n + 1)Q(n + 1){a_n}\\{b_n} &= g(n + 1) \cdot \frac{{f(1) \cdot f(2) \cdot \ldots \cdot f(n)}}{{g(1) \cdot g(2) \cdot \ldots \cdot g(n + 1)}} \cdot {a_n}\\{b_n} &= \frac{{f(1) \cdot f(2) \cdot \ldots \cdot f(n)}}{{g(1) \cdot g(2) \cdot \ldots \cdot g(n)}} \cdot {a_n}\\{b_n} &= \frac{{f(1) \cdot f(2) \cdot \ldots \cdot f(n - 1)}}{{g(1) \cdot g(2) \cdot \ldots \cdot g(n)}} \cdot f(n) \cdot {a_n}\end{aligned}\)

Since,

\(\begin{aligned}f(n){a_n} &= g(n){a_{n - 1}} + h(n)\\f(n)a &= \frac{{f(1) \cdot f(2) \cdot \ldots \cdot f(n - 1)}}{{g(1) \cdot g(2) \cdot \ldots \cdot g(n)}} \cdot \left( {g(n){a_{n - 1}} + h(n)} \right)\\f(n)a &= g(n) \cdot \frac{{f(1) \cdot f(2) \cdot \ldots \cdot f(n - 1)}}{{g(1) \cdot g(2) \cdot \ldots \cdot g(n)}} \cdot {a_{n - 1}} + \frac{{f(1) \cdot f(2) \cdot \ldots \cdot f(n - 1)}}{{g(1) \cdot g(2) \cdot \ldots \cdot g(n)}} \cdot h(n)\\f(n)a &= g(n) \cdot Q(n) \cdot {a_{n - 1}} + Q(n) \cdot h(n)\\f(n)a &= {b_{n - 1}} + Q(n) \cdot h(n)\end{aligned}\)

Use Recurrence Relations for part (b)

(b).

Result part (a):\({b_n} = {b_{n - 1}} + Q(n) \cdot h(n)\)

Applying the recurrence relation repeatedly, we obtain:

\(\begin{aligned}{b_n} = {b_{n - 1}} + Q(n) \cdot h(n)\\{b_n} = {b_{n - 2}} + Q(n - 1) \cdot h(n - 1) + Q(n) \cdot h(n)\\{b_n} = {b_{n - 3}} + Q(n - 2) \cdot h(n - 2) + Q(n - 1) \cdot h(n - 1) + Q(n) \cdot h(n) = \ldots \\{b_n} = {b_1} + Q(2) \cdot h(2) + \ldots + Q(n - 1) \cdot h(n - 1) + Q(n) \cdot h(n)\\{b_n} = {b_0} + Q(1) \cdot h(1) + Q(2) \cdot h(2) + \ldots + Q(n - 1) \cdot h(n - 1) + Q(n) \cdot h(n)\\{b_n} = {b_0} + \sum\limits_{i = 1}^n Q (i) \cdot h(i)\end{aligned}\)

We defined\({b_n}\)as\({b_n} = g(n + 1)Q(n + 1){a_n}\)

\(\begin{aligned}{a_n} &= \frac{{{b_n}}}{{g(n + 1)Q(n + 1)}}\\ &= \frac{{{b_0} + \sum\limits_{i = 1}^n Q (i) \cdot h(i)}}{{g(n + 1)Q(n + 1)}}\\ &= \frac{{{a_0} + \sum\limits_{i = 1}^n Q (i) \cdot h(i)}}{{g(n + 1)Q(n + 1)}}\\ &= \frac{{C + \sum\limits_{i = 1}^n Q (i) \cdot h(i)}}{{g(n + 1)Q(n + 1)}}\end{aligned}\)