9. Linear Recurrences

a Fibonacci sequence defined by
satisfies a LR of order 2

We will be mostly interested in k=2
then

for all

Let be a sequence satisfying **
consider

thus

Let denote the set of all complex sequence satisfying

clearly if
then

where

then is vector space over
since and completely determine it then it follows that

let

then

also

Hence and

Satisfying the recurrence relation

chose a and such that then
are distinct

if dependent the fact they are distinct

suppose

the discriminant is

then

Proof.

we have

as is a root of

then

so
also are linearly independent
for if they were linearly independent then we would have

for some

ie,

for

hence

□