Discrete Math Proof by Induction Problem The lucas series i

Discrete Math - Proof by Induction Problem

The lucas series is defined as:

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

as follows: 2, 1, 3, 4, 7, 11, 18, 29, etc.

Let L(n) be the nth Lucas number in the series (starting from L(0) = 2, L(1) = 1, and so forth), and let F(n) be the nth Fibonacci number (where F(0) = 0, F(1) = 1, and so forth).

Show by induction that F(2n) = F(n)* L(n) for n>= 1.

Solution

By using induction. You get two proofs for the price of one.

To prove need to prove for: F(2n) = F(n)L(n)

Show base cases are true by using n=1     {F(2n) = F(n)* L(n) for n>= 1. }

Assume that the following are true for k <= n:
F(2k) = F(k)L(k) for k value it is true.
   Show the following are true for n+1:
F(2(n+1)=F(n+1)L(n+1)

Proof:

for n=n+1

then F(2n) = F(n)* L(n) for n>= 1.
F(n+1)L(n+1) = [(F(n)+F(n-1)][L(n)+L(n-1)] =
F(n)L(n) + [F(n)L(n-1) + F(n-1)L(n)] + F(n-1)L(n-1) = (by induction hypothesis)
F(2n) + 2F(2n-1) + F(2n-2) =
[F(2n) + F(2n-1)] + [F(2n-1) + F(n-2)] =
F(2n+1) + F(2n) = F(2n+2) = F(2(n+1))