- #1

- 93

- 0

## Main Question or Discussion Point

Why does the characteristic equation of a linear recurrence relation always look like

a

a

_{n}= series of constants multiplied by a number raised to n- Thread starter japplepie
- Start date

- #1

- 93

- 0

Why does the characteristic equation of a linear recurrence relation always look like

a_{n} = series of constants multiplied by a number raised to n

a

- #2

Stephen Tashi

Science Advisor

- 7,027

- 1,250

Unless a specific statement is made about the relation between the characteristic equation and the recurrence, we don't have any theorem to prove. The definition of the characteristic equation gives the form of the equation. Definitions are stipulations, not things to be proven or disproven. We can explain the motivation for the definition by doing some algebra.Why does the characteristic equation of a linear recurrence relation always look like

a_{n}= series of constants multiplied by a number raised to n

You didn't establish much notation, so let's use the notation of the Wikipedia article http://en.wikipedia.org/wiki/Recurrence_relation.

In that article, the recurrence relation is:

[itex] a_n = c_1a_{n-1} + c_2a_{n-2}+\cdots+c_da_{n-d} [/itex] .

Assume [itex] a_n = t^n [/itex] for some unknown [itex] t [/itex]. Substitute a [itex]t^k [/itex] for each [itex] a^k [/itex] in the recurrence relation.

This gives:

[itex] t^n = c_1t^{n-1} + c_2t^{n-2}+\cdots+c_dt^{n-d} [/itex]

Assuming [itex] t\ne 0 [/itex] multiply both sides of the above equation by [itex] t^{d-n} [/itex] :

[itex] t^d = c_1 t^{d-1} + c_2t^{d-2}+\cdots+ c_d^0 [/itex]

Which is equivalent to:

[itex] 0 = t^d - c_1 t^{d-1} - c_2t^{d-2}-\cdots- c_d^0 [/itex]

---------

The above is the same as the characteristic equation:

[itex] 0 = t^d - c_1t^{d-1} - c_2t^{d-2}-\cdots-c_{d} [/itex]

Which comes from setting zero equal to the characteristic polynomial, which is:

[itex] p(t)= t^d - c_1t^{d-1} - c_2t^{d-2}-\cdots-c_{d} [/itex]

.

- Last Post

- Replies
- 3

- Views
- 5K

- Last Post

- Replies
- 22

- Views
- 8K

- Replies
- 3

- Views
- 583

- Replies
- 1

- Views
- 1K

- Replies
- 1

- Views
- 2K

- Replies
- 7

- Views
- 5K

- Replies
- 1

- Views
- 3K

- Last Post

- Replies
- 11

- Views
- 6K

- Last Post

- Replies
- 12

- Views
- 775

- Last Post

- Replies
- 5

- Views
- 3K