Question

Prove Theorem 6.

Short answer

$P\left(k\right)$ is true, for all positive integers $k$.

When$s$ is not a root of the characteristic equation, then

$\left(p_t{n}^t+p_{t-1}{n}^{t-1}+\dots +p_{1}n+p_0\right)s^n$ is a particular solution.

When $s$is a root of the characteristic equation, then

$n^m\left(p_t{n}^t+p_{t-1}{n}^{t-1}+\dots +p_{1}n+p_0\right)s^n$is a particular solution.

Step-by-step solution

Previous Theorem

Theorem 1

The solution of the recurrence relation is of the form ${\mathit{a}}_{\mathbf{n}}\mathbf{=}{\mathit{\alpha }}_{\mathbf{1}}{\mathit{r}}_{\mathbf{1}}^{\mathbf{n}}\mathbf{+}{\mathit{\alpha }}_{\mathbf{2}}{\mathit{r}}_{\mathbf{2}}^{\mathbf{n}}$when${\mathit{r}}_{\mathbf{1}}$and${\mathit{r}}_{\mathbf{2}}$the distinct roots of the characteristic equation.

Theorem 2

The solution of the recurrence relation is of the form${\mathit{r}}_{\mathbf{1}}\mathbf{,}{\mathit{r}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{r}}_{\mathbf{k}}$${\mathit{a}}_{\mathbf{n}}\mathbf{=}{\mathit{\alpha }}_{\mathbf{1}}{\mathit{r}}_{\mathbf{1}}^{\mathbf{n}}\mathbf{+}{\mathit{\alpha }}_{\mathbf{2}}\mathit{n}{\mathit{r}}_{\mathbf{1}}^{\mathbf{n}}$with${\mathit{r}}_{\mathbf{1}}$a root with multiplicity$\mathit{k}$of the characteristic equation.

Theorem 3

If a characteristic equation has the distinct roots${\mathit{r}}_{\mathbf{1}}\mathbf{,}{\mathit{r}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{r}}_{\mathbf{k}}$(each multiplicity l), then the recurrence relation has a solution of the form:${\mathit{a}}_{\mathbf{n}}\mathbf{=}{\mathit{\alpha }}_{\mathbf{1}}{\mathit{r}}_{\mathbf{1}}^{\mathbf{n}}\mathbf{+}{\mathit{\alpha }}_{\mathbf{2}}{\mathit{r}}_{\mathbf{2}}^{\mathbf{n}}\mathbf{+}\mathbf{\dots }\mathbf{.}\mathbf{+}{\mathit{\alpha }}_{\mathbf{k}}{\mathit{r}}_{\mathbf{k}}^{\mathbf{n}}$

Use previous theorem 1

$\left\{a_n\right\}$ satisfies the linear non homogeneous recurrence relation

$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}+F\left(n\right)$

$c_1,c_2,\dots ,c_k$ are real numbers

$F\left(n\right)=\left(b_t{n}^t+b_{t-1}{n}^{t-1}+\dots +b_{1}n+b_0\right)s^n$

$b_0,b_1,\dots ,b_t,s$ are real numbers

To proof: When is not a root of the characteristic equation, then

$\left(p_t{n}^t+p_{t-1}{n}^{t-1}+\dots +p_{1}n+p_0\right)s^n$is a particular solution.

When is a root of the characteristic equation, then

$n^m\left(p_t{n}^t+p_{t-1}{n}^{t-1}+\dots +p_{1}n+p_0\right)s^n$is a particular solution.

Let $P\left(t\right)$ be "When $s$is not a root of the characteristic equation, then

$\left(p_t{n}^t+p_{t-1}{n}^{t-1}+\dots +p_{1}n+p_0\right)s^n$is a particular solution. When $s$is a root of the

characteristic equation, then $n^m\left(p_t{n}^t+\right.\left.p_{t-1}{n}^{t-1}+\dots +p_{1}n+p_0\right)s^n$ is a particular solution.

Use previous theorem 2

Let $t=0$and consider $s$is not a root, then:

$$\begin{gathered} c_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}+F\left(n\right)\left.=c_1{p}_0{s}^{n-1}+c_2{p}_0{s}^{n-2}+\dots .+c_k{p}_0{s}^{n-k}\right)+b_0{s}^n \\ {c}_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}+F\left(n\right)=p_0{a}_n^{\left(h\right)}+b_0{s}^n \\ {c}_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}+F\left(n\right)=p_0{a}_n^{\left(h\right)}+F\left(n\right) \end{gathered}$$

$c_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}+F\left(n\right)=a_n$for some choice of is a root

$$\begin{gathered} c_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}+F\left(n\right)=c_1{p}_0(n-1{)}^m{s}^{n-1}+c_2{p}_0(n-2{)}^m{s}^{n-2}\left.+\dots .+c_k{p}_0{(n-k)}^m{s}^{n-k}\right)+b_0{s}^n \\ {c}_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}+F\left(n\right)=p_0(n-1)(n-2)\dots (n-k)a_n^{\left(h\right)}+F\left(n\right) \end{gathered}$$

$c_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}+F\left(n\right)=a_n$for some choice of$p_{-}0$

Thus $P\left(0\right)$ is true.

Use previous theorem 3

Let $P\left(0\right),P\left(1\right),\dots ,P\left(k\right)$be true.

When $s$is not a root of the characteristic equation, then

$\left(p_k{n}^k+p_{k-1}{n}^{k-1}+\dots +p_{1}n+p_0\right)s^n$is a particular solution. When $s$is a root of the characteristic equation, then $n^m\left(p_k{n}^k+p_{k-1}{n}^{k-1}+\right.\left.\dots +p_{1}n+p_0\right)s^n$is a particular solution.

We need to proof that$P(k+1)$is true and is not a root$$\begin{gathered} c_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}+F\left(n\right)=c_1{p}_{k+1}(n-1{)}^{k+1}{s}^{n-1}+c_2{p}_{k+1}(n-2{)}^{k+1}{s}^{n-2}+b_0{s}^n \\ {c}_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}+F\left(n\right)=p_{k+1}(n-1{)}^{k+1}{a}_n^{\left(h\right)}+b_0{s}^n \\ {c}_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}+F\left(n\right)=p_{k+1}(n-1{)}^{k+1}+F\left(n\right) \end{gathered}$$

$c_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}+F\left(n\right)=a_n$for some choice of is a root.

$$\begin{gathered} c_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}+F\left(n\right)=c_1{p}_{k+1}(n-1{)}^{k+1}{s}^{n-1}+c_2{p}_{k+1}(n-2{)}^{k+1}{s}^{n-2}+b_0{s}^n \\ {c}_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}+F\left(n\right)=p_{k+1}(n-1{)}^{k+1}{a}_n^{\left(h\right)}+b_0{s}^n \\ {c}_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}+F\left(n\right)=p_{k+1}(n-1{)}^{k+1}+F\left(n\right) \end{gathered}$$

$c_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}+F\left(n\right)=a_n$for some choice of $p_{-}k+1$

Thus $p_{k+1}{n}^{k+1}{s}^n$is a particular solution when is not a root.

However, $\left(p_k{n}^k+p_{k-1}{n}^{k-1}+\dots +p_{1}n+p_0\right)s^n$is also a particular solution as $P\left(k\right)$is

true and thus $p_{k+1}{n}^{k+1}{s}^n+\left(p_k{n}^k+\right.$

$\left.p_{k-1}{n}^{k-1}+\dots +p_{1}n+p_0\right)s^n=\left(p_{k+1}{n}^{k+1}+p_k{n}^k+p_{k-1}{n}^{k-1}+\dots +p_{1}n+p_0\right)s^n$is also a particular solution.

Similarly, $p_{k+1}{n}^m{n}^{k+1}{s}^n$is a particular solution when $s$is not a root. However,

$n^m\left(p_k{n}^k+p_{k-1}{n}^{k-1}+\dots +p_{1}n+p_0\right)s^n$is also a particular solution as $P\left(k\right)$ is true and

thus $p_{k+1}{n}^m{n}^{k+1}{s}^n+$$n^m\left(p_k{n}^k+p_{k-1}{n}^{k-1}+\dots +p_{1}n+p_0\right)s^n=n^m\left(p_{k+1}{n}^{k+1}+p_k{n}^k+p_{k-1}{n}^{k-1}+\dots +p_{1}n+p_0\right)s^n$is also a particular solution.

Thus $P(k+1)$is true.

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

When $s$is not a root of the characteristic equation, then

$\left(p_t{n}^t+p_{t-1}{n}^{t-1}+\dots +p_{1}n+p_0\right)s^n$ is a particular solution.

When $s$is a root of the characteristic equation, then

$n^m\left(p_t{n}^t+p_{t-1}{n}^{t-1}+\dots +p_{1}n+p_0\right)s^n$is a particular solution.