The Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13...; starting with 0 and 1, each number is the sum of the two previous numbers.

The Lucas numbers follow the same rule, but start with 2 and 1: 2, 1, 3, 4, 7, 11, 18,...

What's the sum of the first k Lucas numbers?
What's the sum of the squares of the first k Lucas numbers?

(In reply to Like "Fibonacci sums" by Richard)

I happened to take the same route as Richard… I remembered Fibonacci Sums and used that as a starting point. Once I saw the pattern, I was able to prove it as follows:

Similar to the regular Fibonacci sums, the sum of the Lucas numbers is Sum L(k) = L(k+2)-1, and the sum of the squares of the Lucas numbers is Sum L(k)^2 = L(k)*L(k+1)+2 I will call the first function SL(k) which means Sum of the first k Lucas numbers.

I will call the second function SSL(k) which means Sum of the Squares of the first k Lucas numbers.

Base case.
SL(0) = 2
Using our proposed formula, SL(0) = L(0+2) – 1 = 3 – 1 = 2.
So the formula is true for the base case.

Inductive step.
Let’s suppose that SL(k) = L(k+2) – 1 is true.
We expect to prove that SL(k+1) = L(k+3) – 1 SL(k+1) = L(0) + L(1) + L(2) + … L(k+1) + L(k) + L(k+1)
SL(k+1) = SL(k) + L(k+1)
SL(k+1) = L(k+2) – 1 + L(k+1)
Since L(k) = L(k-1) + L(k-2) is the same thing as saying L(k+3) = L(k+2) + L(k+1)
SL(k+1) = L(k+3) – 1

QED

Now for SSL(k) = L(k)*L(k+1) + 2

Base case.
SSL(0) = 2^2 = 4
Using our proposed formula, SSL(0) = L(0)*L(0+1) + 2 = 2*1 + 2 = 4
So the formula is true for the base case.

Inductive step.
Let’s suppose that SSL(k) = L(k)*L(k+1) + 2
We expect to prove that SSL(k+1) = L(k+1)*L(k+2) +2

SSL(k+1) = L(0)^2 + L(1)^2 + L(2)^2 + … L(k+1)^2 + L(k)^2 + L(k+1)^2
SSL(k+1) = SSL(k) + L(k+1)^2
SSL(k+1) = L(k)*L(k+1) + 2 + L(k+1)^2
SSL(k+1) = L(k+1)*[L(k) + L(k+1)] + 2
SSL(k+1) = L(k+1)*[L(k+2)] +2
SSL(k+1) = L(k+1)*L(k+2) +2

QED

Posted by nikki on 2004-10-07 16:55:00