Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Short Answer

Prove Theorem 6.

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

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

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

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

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

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step 1: Previous Theorem

Theorem 1

The solution of the recurrence relation is of the form $a_{n} = α_{1} r_{1}^{n} + α_{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}, \dots, r_{k}$ $a_{n} = α_{1} r_{1}^{n} + α_{2} n r_{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}, \dots, r_{k}$ (each multiplicity l), then the recurrence relation has a solution of the form: $a_{n} = α_{1} r_{1}^{n} + α_{2} r_{2}^{n} + \dots . + α_{k} r_{k}^{n}$

Step 2: Use previous theorem 1

$\{a_{n}\}$ 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 (n)$

$c_{1}, c_{2}, \dots, c_{k}$ are real numbers

$F (n) = (b_{t} n^{t} + b_{t - 1} n^{t - 1} + \dots + b_{1} n + b_{0}) 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

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

When is a root of the characteristic equation, then

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

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

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

characteristic equation, then $n^{m} (p_{t} n^{t} + p_{t - 1} n^{t - 1} + \dots + p_{1} n + p_{0}) 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 (n) = c_{1} p_{0} s^{n - 1} + c_{2} p_{0} s^{n - 2} + \dots . + c_{k} p_{0} s^{n - k}) + b_{0} s^{n} c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} + F (n) = p_{0} a_{n}^{(h)} + b_{0} s^{n} c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} + F (n) = p_{0} a_{n}^{(h)} + F (n)$

$c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} + F (n) = 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 (n) = c_{1} p_{0} (n - 1)^{m} s^{n - 1} + c_{2} p_{0} (n - 2)^{m} s^{n - 2} + \dots . + c_{k} p_{0} {(n - k)}^{m} s^{n - k}) + b_{0} s^{n} c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} + F (n) = p_{0} (n - 1) (n - 2) \dots (n - k) a_{n}^{(h)} + F (n)$

$c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} + F (n) = a_{n}$ for some choice of $p_{-} 0$

Thus $P (0)$ is true.

Step 4: Use previous theorem 3

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

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

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

We need to proof that $P (k + 1)$ is true and is not a root $c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} + F (n) = 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 (n) = p_{k + 1} (n - 1)^{k + 1} a_{n}^{(h)} + b_{0} s^{n} c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} + F (n) = p_{k + 1} (n - 1)^{k + 1} + F (n)$

$c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} + F (n) = 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 (n) = 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 (n) = p_{k + 1} (n - 1)^{k + 1} a_{n}^{(h)} + b_{0} s^{n} c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} + F (n) = p_{k + 1} (n - 1)^{k + 1} + F (n)$

$c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} + F (n) = 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, $(p_{k} n^{k} + p_{k - 1} n^{k - 1} + \dots + p_{1} n + p_{0}) s^{n}$ is also a particular solution as $P (k)$ is

true and thus $p_{k + 1} n^{k + 1} s^{n} + (p_{k} n^{k} +$

$p_{k - 1} n^{k - 1} + \dots + p_{1} n + p_{0}) s^{n} = (p_{k + 1} n^{k + 1} + p_{k} n^{k} + p_{k - 1} n^{k - 1} + \dots + p_{1} n + p_{0}) 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} (p_{k} n^{k} + p_{k - 1} n^{k - 1} + \dots + p_{1} n + p_{0}) s^{n}$ is also a particular solution as $P (k)$ is true and

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

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

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

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

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

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

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

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Prove Theorem 6.

Step by Step Solution

Step 1: Previous Theorem

Step 2: Use previous theorem 1

Step 3: Use previous theorem 2

Step 4: Use previous theorem 3

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Prove Theorem 6.

Step by Step Solution

Step 1: Previous Theorem

Step 2: Use previous theorem 1

Step 3: Use previous theorem 2

Step 4: Use previous theorem 3

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Calculus

Pure Maths