Discrete Mathematics Proof by Induction Problem The lucas nu

Discrete Mathematics, Proof by Induction Problem

The lucas numbers are a series defined as follows:

Thus the lucas numbers begin:

given L(0)=2

L(1)=1

L(n)=L(n-1)+L(n-2) for n>=2

so lucas numbers are 2,1,3,4,7,11,18,...

and Fibnocci numbers are

F(0)=0

F(1)=1

thus F(2)=0+1=1

thus F(n)=F(n-1)+F(n-2)

now the given statement is

S(n) be the statement thet F(2n)=F(n)*L(n) for n>=1

we prove that statement is true for n=1

F(2)=F(1)*L(1)

1=1*1=1

therefore statement is true for n=1

now assume that the statement is true for n=k

therefore S(k) : F(2k)=F(k)*L(k)

here we prove that the statement is true for n=k+1

F(2k+2)=F(2k+1)+F(2k)

=F(2k)+F(2k-1)+F(2k)

=2F(2k)+F(2k-1)

F(k+1)*L(k+1)={F(k)+F(k-1)}*{L(k)+L(k-1)}

= F(k)L(k)+F(k)L(k-1)+F(k-1)L(k)+F(k-1)L(k-1)

=F(2k)+F(2k-2)+F(k)L(k-1)+F(k-1)L(k)

=F(2k)+F(2k-1)+F(2k)+F(k)L(k-1)+F(k-1)L(k)

=2F(2k)+F(2k-1)+F(k)L(k-1)+F(k-1)L(k)

=2F(2k)+F(2k-1)

next terms are negligable

thus F(2(k+1))=F(k+1)*L(k+1)

therefore the statement is true for n=k+1

b ythe principle of mathematical induction the statement is true for all n>=1