Question

Prove Theorem 4.

Short answer

A sequence $\left\{a_n\right\}$ is a solution of the recurrence relation $a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}$ if and only if $$\begin{gathered} a_n=\left({\alpha }_{1,0}+{\alpha }_{1,1}n+\dots +{\alpha }_{1,m_1-1}{n}^{m_1-1}\right)r_1^n \\ +\left({\alpha }_{2,0}+{\alpha }_{2,1}n+\dots +\right.\left.{\alpha }_{2,m_1-1}{n}^{m_1-1}\right)r_2^n+\dots \\ +\left(\alpha l,0+{\alpha }_{l,1}n+\dots +{\alpha }_{l,m_1-1}{n}^{m_1-1}\right)r_l^n \end{gathered}$$

for n = 0,1,2,.......where${\alpha }_i$ are constants.

Step-by-step solution

Previous Theorem

Theorem 1

The solution of the recurrence relation is of the form\({a_n} = {\alpha _1}r_1^n + {\alpha _2}r_2^n\)when\({r_1}\)and\({r_2}\)the distinct roots of the characteristic equation.

Theorem 2

The solution of the recurrence relation is of the form\({r_1},{r_2}, \ldots ,{r_k}\)\({a_n} = {\alpha _1}r_1^n + {\alpha _2}nr_1^n\)with\({r_1}\)a root with multiplicity\(k\)of the characteristic equation.

Theorem 3

If a characteristic equation has the distinct roots\({r_1},{r_2}, \ldots ,{r_k}\)(each multiplicity l), then the recurrence relation has a solution of the form:\({a_n} = {\alpha _1}r_1^n + {\alpha _2}r_2^n + \ldots . + {\alpha _k}r_k^n\)

Use previous theorem

Given: Let $c_1,c_2,\dots ,c_k$'''' be real numbers.

$r^k-c_1{r}^{k-1}-\dots -c_k=0$has t distinct roots $r_1,r_2,\dots ,r_l$with multiplicities $m_1,m_2,\dots ,m_l$$\left.{\alpha }_{2,m_1-1}{n}^{m_1-1}\right)r_2^n+\dots +\left({\alpha }_{l,0}+{\alpha }_{l,1}n+\dots +{\alpha }_{l,m_1-1}{n}^{m_1-1}\right)r_l^n$for$n=0,1,2,\dots$, where ${\alpha }_i$are constants.

PROOF BY INDUCTION$\left.{\alpha }_{2,m_1-1}{n}^{m_1-1}\right)r_2^n+\dots +\left({\alpha }_{l,0}+{\alpha }_{l,1}n+\dots +{\alpha }_{l,m_1-1}{n}^{m_1-1}\right)r_l^n$for n = 0,1,'2,...... , where ${\alpha }_i$ are constants."

Basis step k = 1

Let us assume that $a_n=\left({\alpha }_{1,0}+{\alpha }_{1,1}n+\dots +{\alpha }_{1,m_1-1}{n}^{m_1-1}\right)r_1^n$ $r_1$is the only root of $r^k-c_1{r}^{k-1}-\dots -c_k=0$

$r_1^k=c_1{r}_1^{k-1}+\dots +c_k$

Next we check that $a_n=\left({\alpha }_{1,0}+{\alpha }_{1,1}n+\dots +{\alpha }_{1,m_1-1}{n}^{m_1-1}\right)r_1^n$ is a solution of the recurrence relation:

$$\begin{gathered} c_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}=c_1\left({\alpha }_{1,0}+{\alpha }_{1,1}(n-1)+\dots +{\alpha }_{1,m_1-1}{(n-1)}^{m_1-1}\right)r_1^{n-1} \\ +c_2\left({\alpha }_{1,0}+{\alpha }_{1,1}(n-2)+\dots +{\alpha }_{1,m_1-1}{(n-2)}^{m_1-1}\right)r_1^{n-2}+\dots \\ +c_k\left({\alpha }_{1,0}+{\alpha }_{1,1}(n-k)+\dots +{\alpha }_{1,m_1-1}{(n-k)}^{m_1-1}\right)r_1^{n-k} \\ {c}_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}={\alpha }_{1,0}{r}_1^{n-k}\left(c_1{r}^{k-1}+c_2{r}^{k-2}+\dots +c_k\right) \\ +n{\alpha }_{1,1}{r}_1^{n-k}\left(c_1{r}^{k-1}+c_2{r}^{k-2}+\dots +c_k\right)+\dots \\ +n^{m_1-1}{\alpha }_{1,m_1-1}{r}_1^{n-k}\left(c_1{r}^{k-1}+c_2{r}^{k-2}+\dots +c_k\right) \\ {c}_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}={\alpha }_{1,0}{r}_1^n+n{\alpha }_{1,1}{r}_1^n+\dots +n^{m_1-1}{\alpha }_{1,m_1-1}{r}_1^n \\ {c}_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}=\left[{\alpha }_{1,0}+n{\alpha }_{1,1}+\dots +n^{m_1-1}{\alpha }_{1,m_1-1}\right]r_1^n \\ {c}_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}=a_n \end{gathered}$$

Thus the sequence $\left\{a_n\right\}$ is a solution of the recurrence relation.

The solution of the recurrence relation is unique, thus $a_n=\left({\alpha }_{1,0}+\right.\left.{\alpha }_{1,1}n+\dots +{\alpha }_{1,m_1-1}{n}^{m_1-1}\right)r_1^n$ is the only solution.

Use previous theorem to further simplify

Let us assume that $P\left(q\right)$is true. We need to show that $P(q+1)$ is also true.

$r_1,r_2,\dots ,r_q,r_{q+1}$are the distinct roots of $r^k-c_1{r}^{k-1}-\dots -c_k=0$

Since $P\left(q\right)$is true:$a_n^{\left(1\right)}=\left({\alpha }_{1,0}+{\alpha }_{1,1}n+\dots +{\alpha }_{1,m_1-1}{n}^{m_1-1}\right)r_1^n+\left({\alpha }_{2,0}+{\alpha }_{2,1}n+\dots +{\alpha }_{2,m_1-1}{n}^{m_1-1}\right)r_2^n+\dots +\left({\alpha }_{q,0}+{\alpha }_{q,1}n+\dots +{\alpha }_{q,m_1-1}{n}^{m_1-1}\right)r_q^n$

By the basis step of the proof, $P\left(1\right)$ is true for root :$r_{q+1}$

$a_n^{\left(2\right)}=\left({\alpha }_{1,0}+{\alpha }_{1,1}n+\dots +{\alpha }_{1,m_{q+1}-1}{n}^{m_{q+1}-1}\right)r_{q+1}^n$

We have then obtained two parts of the solution: $a_n^{\left(1\right)}$ and $a_n^{\left(2\right)}$. Since both expressions need to be part of the solution of the recurrence relation and since both expressions have no terms in common, the solution needs to be equal to the sum of both expressions:

$$\begin{gathered} a_n=a_n^{\left(1\right)}+a_n^{\left(2\right)}=\left({\alpha }_{1,0}+{\alpha }_{1,1}n+\dots +{\alpha }_{1,m_1-1}{n}^{m_1-1}\right)r_1^n+\left({\alpha }_{2,0}+{\alpha }_{2,1}n+\dots +{\alpha }_{2,m_1-1}{n}^{m_1-1}\right)r_2^n+\dots \\ +\left({\alpha }_{q,0}+{\alpha }_{q,1}n+\dots +{\alpha }_{q,m_1-1}{n}^{m_1-1}\right)r_q^n+\left({\alpha }_{1,0}+{\alpha }_{1,1}n+\dots +{\alpha }_{1,m_{q+1}-1}{n}^{m_{q+1}-1}\right)r_{q+1}^n \end{gathered}$$

thus $P(q+1)$is true.

Conclusion by the principal of mathematical induction:$P\left(k\right)$ is true, for all positive integers k .

A sequence$\left\{a_n\right\}$ is a solution of the recurrence relation

$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}$if and only if

$$\begin{gathered} a_n=\left({\alpha }_{1,0}+{\alpha }_{1,1}n+\dots +{\alpha }_{1,m_1-1}{n}^{m_1-1}\right)r_1^n \\ +\left({\alpha }_{2,0}+{\alpha }_{2,1}n+\dots +\right.\left.{\alpha }_{2,m_1-1}{n}^{m_1-1}\right)r_2^n+\dots \\ +\left(\alpha l,0+{\alpha }_{l,1}n+\dots +{\alpha }_{l,m_1-1}{n}^{m_1-1}\right)r_l^n \end{gathered}$$

for n = 0,1,2,..... where ${\alpha }_i$are constants.