 Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q52E

Expert-verified Found in: Page 527 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Prove Theorem 6.

$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.

See the step by step solution

## Step 1: Previous Theorem

Theorem 1

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

Theorem 2

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

Theorem 3

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

## Step 2: 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}+{p}_{t-1}{n}^{t-1}+\dots +{p}_{1}n+{p}_{0}\right){s}^{n}$ is a particular solution.

## Step 3: Use previous theorem 2

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

${c}_{1}{a}_{n-1}+{c}_{2}{a}_{n-2}+\dots +{c}_{k}{a}_{n-k}+F\left(n\right)={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}\phantom{\rule{0ex}{0ex}}{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}\phantom{\rule{0ex}{0ex}}{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)$

${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

${c}_{1}{a}_{n-1}+{c}_{2}{a}_{n-2}+\dots +{c}_{k}{a}_{n-k}+F\left(n\right)={c}_{1}{p}_{0}\left(n-1{\right)}^{m}{s}^{n-1}+{c}_{2}{p}_{0}\left(n-2{\right)}^{m}{s}^{n-2}+\dots .+{c}_{k}{p}_{0}{\left(n-k\right)}^{m}{s}^{n-k}\right)+{b}_{0}{s}^{n}\phantom{\rule{0ex}{0ex}}{c}_{1}{a}_{n-1}+{c}_{2}{a}_{n-2}+\dots +{c}_{k}{a}_{n-k}+F\left(n\right)={p}_{0}\left(n-1\right)\left(n-2\right)\dots \left(n-k\right){a}_{n}^{\left(h\right)}+F\left(n\right)$

${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.

## Step 4: 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}+\dots +{p}_{1}n+{p}_{0}\right){s}^{n}$ is a particular solution.

We need to proof that$P\left(k+1\right)$ is true and is not a root${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}\left(n-1{\right)}^{k+1}{s}^{n-1}+{c}_{2}{p}_{k+1}\left(n-2{\right)}^{k+1}{s}^{n-2}+{b}_{0}{s}^{n}\phantom{\rule{0ex}{0ex}}{c}_{1}{a}_{n-1}+{c}_{2}{a}_{n-2}+\dots +{c}_{k}{a}_{n-k}+F\left(n\right)={p}_{k+1}\left(n-1{\right)}^{k+1}{a}_{n}^{\left(h\right)}+{b}_{0}{s}^{n}\phantom{\rule{0ex}{0ex}}{c}_{1}{a}_{n-1}+{c}_{2}{a}_{n-2}+\dots +{c}_{k}{a}_{n-k}+F\left(n\right)={p}_{k+1}\left(n-1{\right)}^{k+1}+F\left(n\right)$

${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.

${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}\left(n-1{\right)}^{k+1}{s}^{n-1}+{c}_{2}{p}_{k+1}\left(n-2{\right)}^{k+1}{s}^{n-2}+{b}_{0}{s}^{n}\phantom{\rule{0ex}{0ex}}{c}_{1}{a}_{n-1}+{c}_{2}{a}_{n-2}+\dots +{c}_{k}{a}_{n-k}+F\left(n\right)={p}_{k+1}\left(n-1{\right)}^{k+1}{a}_{n}^{\left(h\right)}+{b}_{0}{s}^{n}\phantom{\rule{0ex}{0ex}}{c}_{1}{a}_{n-1}+{c}_{2}{a}_{n-2}+\dots +{c}_{k}{a}_{n-k}+F\left(n\right)={p}_{k+1}\left(n-1{\right)}^{k+1}+F\left(n\right)\text{}$

${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}+$

${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\left(k+1\right)$ 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. ### Want to see more solutions like these? 