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?
Fixed a minor sign error.
The sum of the first k Lucas numbers is L
k+2-1. This can be seen by simple induction; it is clear when k=1, and we note that (L
k+2-1) + L
k+1 = (L
k+1+L
k+2)-1 = L
k+3-1.
The sum of the squares of the first k Lucas numbers depends on whether k is even or odd. If k is odd, it is given by (L
2k+3), while if k is even, it is given by (L
2k+1).
I'm afraid I'm not sure how to show this by simple induction, so I'll
have to break out a bit more sophisticated tricks:
Let p= (1+sqrt(5))/2, and q=(1-sqrt(5))/2. We can show by a straightforward induction (omitted here) that L
k=p^(n-1)+q^(n-1). Since pq=-1, this means that
L
k^2=p^(2n-2)+q^(2n-2)+2(-1)^(n-1).
Summing the squares of the first k Lucas numbers then gets us
(1+p^2+p^4+...+p^(2k-2)) + (1+q^2+q^4+...+q^(2k-2)) + x,
where x is 2 if k is odd and 0 if k is even. Summing the infinite geometric series gets us
(p^(2k)-1)/(p^2-1) + (q^(2k)-1)/(q^2-1) + x,
or using the fact that p^2-p-1=q^2-q-1=0,
(p^(2k)-1)/(p) + (q^(2k)-1)/(q) + x,
or using the fact that pq=-1 again,
p^(2k-1)+q^(2k-1)+(p+q)+x.
Since p+q=1, this gives us the desired solution.
Edited on October 7, 2004, 1:37 pm
Solution
