Question

Use Exercise 48 to solve the recurrence relation\((n + 1){a_n} = (n + 3){a_{n - 1}} + n\) , for \(n \geqslant 1\), with \({a_0} = 1\)

Short answer

Thus, the result is$a_n=\frac{5}{12}{n}^2+\frac{13}{12}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\)a root of this characteristic equation and its multiplicity is 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

The result from the previous exercise is\(f(n){a_n} = g(n){a_{n - 1}} + h(n)n \ge 1{a_0} = C\), then\({a_n} = \frac{{C + \sum\limits_{i = 1}^n Q (i) \cdot h(i)}}{{g(n + 1)Q(n + 1)}},\,\,Q(n) = \frac{{f(1) \cdot f(2) \cdot \ldots \cdot f(n - 1)}}{{g(1) \cdot g(2) \cdot \ldots \cdot g(n)}}\)

Solve:\((n + 1){a_n} = (n + 3){a_{n - 1}} + n{a_0} = 1\)

Since\(f(n){a_n} = g(n){a_{n - 1}} + h(n)\)and\({a_0} = C\)(in general):

\(f(n) = n + 1g(n) = n + 3h(n) = nC = 1\)

Let us first determine\(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{array}{l}Q(n) = \frac{{f(1) \cdot f(2) \cdot \ldots \cdot f(n - 1)}}{{g(1) \cdot g(2) \cdot \ldots \cdot g(n)}}\\Q(n) = \frac{{2 \cdot 3 \cdot \ldots \cdot n}}{{4 \cdot 5 \cdot \ldots \cdot (n + 3)}}\\Q(n) = \frac{{2 \cdot 3}}{{(n + 1) \cdot (n + 2) \cdot (n + 3)}}\\Q(n) = \frac{6}{{(n + 1) \cdot (n + 2) \cdot (n + 3)}}\end{array}\)

Then we obtain:

\(\begin{array}{c}\sum\limits_{i = 1}^n Q (i)h(i) = \sum\limits_{i = 1}^n {\frac{{6i}}{{(i + 1) \cdot (i + 2) \cdot (i + 3)}}} \\ = \frac{{3n(n + 1)}}{{2(n + 2)(n + 3)}}\end{array}\)

Use the results from the previous exercise

Using the result of the previous exercise, we then obtain:

$$\begin{gathered} a_n=\frac{C+{\sum }_{i=1}^{n}Q\left(i\right)·h\left(i\right)}{g(n+1)Q(n+1)} \\ {a}_n=\frac{1+\frac{3n(n+1)}{2(n+2)(n+3)}}{6} \\ {a}_n=\frac{1+\frac{3n(n+1)}{2(n+2)(n+3)}}{\frac{6}{(n+2)(n+3)}} \\ {a}_n=\frac{(n+2)(n+3)+\frac{3n(n+1)}{2}}{6} \\ {a}_n=\frac{2(n+2)(n+3)+3n(n+1)}{12} \\ {a}_n=\frac{2n^2+10n+12+3n^2+3n}{12} \\ {a}_n=\frac{5n^2+13n+12}{12} \\ {a}_n=\frac{5}{12}{n}^2+\frac{13}{12}n+1 \end{gathered}$$

Thus, the result is$a_n=\frac{5}{12}{n}^2+\frac{13}{12}n+1$