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 Generalized! by nikki)

Ack! I was too hasty and didn’t check the sum of the first k Nikki numbers thoroughly. I assumed it was uninteresting. Here are the real answers, along with their proofs.

For any series defined as follows:
N(1) = a
N(2) = b
For k>2, N(k) = N(k-1) + N(k-2)

The following is true:

The sum of the first k Nikki numbers is
N(k+2) – N(2) = N(k+2) – b

The sum of the squares of the first k Nikki numbers is
N(k)*N(k+1) + N(1)*[N(1) – N(2)]
Or
N(k)*N(k+1) + a*(a–b)

First Proof: SN(k) = N(k+2) – N(2) Base case.
SN(1) = N(1)
Using our proposed formula,
SN(1) = N(1+2) – N(2) = N(3) – N(2).
SN(1) = [N(2) + N(1)] – N(2)
SN(1) = N(1).
So the formula is true for the base case.

Inductive step.
Let’s suppose that SN(k) = N(k+2) – N(2) is true.
We expect to prove that SN(k+1) = N(k+3) – N(2)

SN(k+1) = N(0) + N(1) + N(2) + … N(k+1) + N(k) + N(k+1)
SN(k+1) = SN(k) + N(k+1)
SN(k+1) = N(k+2) – N(2) + N(k+1)
Since N(k) = N(k-1) + N(k-2) is the same thing as saying N(k+3) = N(k+2) + N(k+1)
SN(k+1) = N(k+3) – N(2)

QED

Second Proof: SSN(k) = N(k)*N(k+1) + N(1)*[N(1) – N(2)]

Base case.
SSN(1) = N(1)^2
Using our proposed formula,
SSN(1) = N(1)*N(1+1) + N(1)*[N(1) – N(2)]
SSN(1) = N(1)*N(2) + N(1)^2 – N(1)*N(2)
SSN(1) = N(1)^2
So the formula is true for the base case.

Inductive step.
Net’s suppose that SSN(k) = N(k)*N(k+1) + 2
We expect to prove that SSN(k+1) = N(k+1)*N(k+2) +2

SSN(k+1) = N(0)^2 + N(1)^2 + N(2)^2 + … N(k+1)^2 + N(k)^2 + N(k+1)^2
SSN(k+1) = SSN(k) + N(k+1)^2
SSN(k+1) = N(k)*N(k+1) + N(1)*[N(1) – N(2)] + N(k+1)^2
SSN(k+1) = N(k+1)*[N(k) + N(k+1)] + N(1)*[N(1) – N(2)]
SSN(k+1) = N(k+1)*[N(k+2)] + N(1)*[N(1) – N(2)]
SSN(k+1) = N(k+1)*N(k+2) + N(1)*[N(1) – N(2)]

QED

Posted by nikki on 2004-10-08 09:15:31