Prove: The sum of the first 20*A Fibonacci numbers is divisible by the 10*Ath Fibonacci number?

Let F[n] denote the nth Fibonacci number, then

the sum of the first 20*A of them is F[20A+2]-1.

This equals F[20A] + F[20A+1]-1; F[20A]/F[10A] = L[10A], where L[n] is the nth Lucas number. Also,

( F[20A+1] – 1) / F[10A] = L[10A+1].

So the result of the division is L[10A+2].

Identities used:

SUM [i = 1 to n] F[i] = F[n+2] – 1;

F[2n] / F[n] = L[n];

(F[4n+1] – 1) / F[2n] = L[2n+1].

Steve

EDIT –

Proofs of identities:

1) straightforward induction.

2) Use the identitites

(F)…. F[n] = [ φ^n – (1-φ)^n ] / √5

(L)…. L[n] = φ^n + (1-φ)^n

multiplying these together, and using the difference of two squares, we easily get F[2n].

3) Using identities (F) and (L), and expanding the product F[2n] * L[2n+1], it is easy to see this is equivalent to a certain difference** equaling √5. Using induction, it is equivalent to showing φ²(1-φ)² = 1, which follows immediately from φ(1-φ) = -1.

There are in fact proofs of (3) which can be done using induction and repeated use of (2), but I find this simpler and more “follow-your-nose”. There are also proofs using the hyperbolic functions cosh and sinh and de Moivre’s theorem.

** the difference is φ^(2n+1) * (1-φ)^(2n) – φ^(2n) * (1-φ)^(2n+1).

Will provide a proof for n = 2qA with q even-valued.

Define the sum of the first n Fibonacci numbers by S(n):

S(n) = u(1) + u(2) + … + u(n-1) + u(n),

where u(i) is the i’th Fibonacci number.

Then

S(n) = (u(3)-u(2)) + (u(4)-u(3)) + … + (u(n+1)-u(n)) + (u(n+2)-u(n+1))

==> S(n) = u(n+2) – 1, — (1)

since u(2) = 1.

Next, note the identity:

u(s+t) = u(s-1)*u(t) + u(s)*u(t+1), — (2)

which holds for all s >= 2, t >= 1.

(This can be easily proved by induction – e.g. over t for fixed s – but can also be “seen” by noting:

u(s+t) = u(1)*u(s+t-2) + u(2)*u(s+t-1)

= u(2)*u(s+t-3) + (u(1)+u(2))*u(s+t-2)

= u(2)*u(s+t-3) + u(3)*u(s+t-2) = …

= u(s-2)*u(t+1) + u(s-1)*u(t+2)

= u(s-1)*u(t) + u(s)*u(t+1).)

Now consider integers of the form n = 2qA, where q and A are integers with no restrictions on q (e.g. evenness) for the moment.

Applying (1):

S(2qA) = u(2qA+2) – 1

= u(qA-1)*u(qA+2) + u(qA)*u(qA+3) – 1, by (2)

= u(qA-1)*{u(qA-1)*u(2) + u(qA)*u(3)} + u(qA)*u(qA+3) – 1,

using (2) again.

==> S(2qA) = u(qA)*{2*u(qA-1) + u(qA+3)} + (u(qA-1)^2 – 1). — (3)

Just got to work on (u(qA-1)^2 – 1) and we’re done:

For this purpose, consider u(m-1)^2:

u(m-1)^2 = ( u(m) – u(m-2) )*( u(m-2) + u(m-3) )

= u(m)*u(m-2) + u(m)*u(m-3) – u(m-2)^2 – u(m-2)*u(m-3)

= u(m)*(u(m)-u(m-1)) + (2*u(m-2)+u(m-3))*u(m-3)

– u(m-2)^2 – u(m-2)*u(m-3)

==> u(m-1)^2 – u(m)^2 + u(m)*u(m-1)

= u(m-3)^2 – u(m-2)^2 + u(m-2)*u(m-3)

= … = u(1)^2 – u(2)^2 + u(2)*u(1), if m is even

= … = u(2)^2 – u(3)^2 + u(2)*u(3), if m is odd

==> u(m-1)^2 = u(m)^2 – u(m)*u(m-1) + (-1)^m. — (4)

Hence, by (4),

u(qA-1)^2 = (-1)^(qA) + u(qA)*(u(qA) – u(qA-1))

Subst. this into (3) and reduce resulting expression:

S(2qA) = u(qA)*{u(qA+1) + u(qA+3)} + ((-1)^(qA) – 1).

Hence,

if q is even (e.g. q = 10, like in the question), u(qA) | S(2qA),

if q is odd and A is even, u(qA) | S(2qA),

if q and A are odd, then u(qA) | (S(2qA) + 2).

I have managed to make some progress so far by utilizing some modular arithmetic. I partition the first 4n Fibonacci numbers into the two sets {F(1), F(2), …, (F(2n – 1)}, {F(2n+1), F(2n+2), …, F(4n – 1)} and {F(2n), F(4n)}. We can relate residue classes (mod F(2n)) of the second set to those of the first by:

F(2n + k) ≡ F(k)F(2n – 1) (mod F(2n)), 1 < k < 2n.

The proof is naturally by induction: clearly F(2n + 1) = F(2n) + F(2n – 1) ≡ 0 + F(2n – 1) = F(1)F(2n – 1) (mod F(2n)), and F(2n + 2) = F(2n + 1) + F(2n) ≡ F(2n – 1) (mod F(2n)). Supposing the truth of the statement for k and k + 1, we obtain:

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

≡ F(k+1)F(2n – 1) + F(k)F(2n – 1) (mod F(2n))

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

= F(k+2)F(2n – 1), as needed.

Clearly, F(2n) and F(4n) ≡ 0 (mod F(2n)) [1]. We may write:

Σ[1:4n] Fi = Σ[1:2n] Fi + Σ[1:2n] F(2n + i)

= Σ[1:2n – 1] Fi + Σ[1:2n – 1] F(2n + i) + F(2n) + F(4n)

≡ Σ[1:2n – 1] Fi + Σ[1:2n – 1] F(i)F(2n – 1) (mod F(2n))

= [Σ[1:2n – 1] F(i)][F(2n – 1) + 1]

Using the formula Σ[1:k] F(i) = F(k+2) – 1, we obtain:

[F(2n+1) – 1][F(2n – 1) + 1] ≡ S (mod F(10n))

Further, this expression can be expanded to:

F(2n + 1)F(2n – 1) + F(2n+1) – F(2n-1) – 1

=[F(2n) + F(2n-1)]F(2n-1) + F(2n) – 1

=F(2n)F(2n – 1) + F(2n-1)² + F(2n) – 1

≡ F(2n – 1)² – 1 (mod F(2n))

If we can establish that F(2n – 1)² – 1 is divisible by F(2n), it will follow that the complete sum is. I have an inkling of where to go from there, but I am far too tired to pursue it further at present.

As an aside, I think it is possible to extend the result to “the sum of the first 4n Fibonacci numbers is divisible by the 2nth.” Unfortunately, I’ve only verified this up to n = 9.

Edit: It looks like both of these conjectures are true; that is, both F(10n – 1)² ≡ 1 (mod F(10n)), and that we may safely replace 10n and 20n with 2n and 4n, respectively. In fact, I conjecture that F(2n – 1)² – 1 = F(2n)F(2n – 2), from which the needed congruence falls out. I suspect this claim will be susceptible to an inductive proof, which I will provide as soon as I finish with some errands.

Edit 2: As I suspected, F(2n – 1)² – 1 = F(2n)F(2n – 2) is easily proved by induction: clearly, for n = 1 we have F(1)² – 1 = 1 – 1 = 0, and F(2)F(0) = (1)(0) = 0. If we suppose F(2k – 1)² – 1 = F(2k)F(2k – 2), then we can determine that:

F(2k + 1)² – 1 = [F(2k) + F(2k – 1)]² – 1

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

= F(2k)² + 2F(2k)F(2k – 1) + F(2k)F(2k – 2) (ind. hyp.)

= F(2k)[F(2k) + 2F(2k – 1) + F(2k – 2)]

= F(2k)[(F(2k) + F(2k – 1)) + (F(2k – 1) + F(2k – 2))]

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

= F(2k)F(2k + 2), as needed.

I have gone ahead and taken the liberty of editing my original argument from mod F(10n) to mod F(2n); the argument, however, remains the same.

I would also like to express admiration for Barney’s proof, who followed through with my initial instinct to use the closed-form formula for F(n), and managed to do it much more elegantly than my attempt looked. Only one thing is sort of lacking, and that is that it might be worthwhile to prove that your quantity g^(10m+2) + (-1/g)^(10m+2) is truly an integer, so that F(10m)(g^(10m+2) + (-1/g)^(10m+2)) is indeed a factorization of the sum.

Edit 3: Accolades to Steve’s proof as well! Both of you have offered much more elegant solutions than mine. Truly, it seems the relationship between the Fibonacci and Lucas numbers is very useful in this problem. It is also worth noting that Steve’s proof also generalizes easily to show that the sum of the first 4n Fibonacci numbers is divisible by the 2nth.

Source(s): [1] http://en.wikipedia.org/wiki/Fibonacci_number; “Identity for doubling n”51

Let F_n be the nth Fibonacci number, n = 0, 1, 2, ….

Then F_n = ( g^n – (-1/g)^n)/Sqrt(5),

where g = (1 + Sqrt(5))/2 and (-1/g) = (1 – Sqrt(5))/2.

Note that 1 – g = -1/g

Sum F_n from 0 to 20m to get

S = [ ( 1 – g^(20m+1))/(1-g) – ( 1 – (-1/g)^(20m+1))/(1 – (-1/g)) ]/Sqrt(5)

= [ g^(20m+2) – ( g + 1/g) – (-1/g)^(20m+2) ]/Sqrt(5)

Factor (-1/g)^(20m+2) out of the expression and use the fact that

g + 1/g = Sqrt(5) to get

S = (-1/g)^(20m+2)[ g^(40m+4) – Sqrt(5)g^(20m+2) – 1 ]/Sqrt(5)

Factor the expression in brackets by factoring the quadratic

x^2 – Sqrt(5)x – 1. From the quadratic formula, this has factors

x = (3 + Sqrt(5))/2 = g^2 and x = (-3 + Sqrt(5))/2 = -1/g^2.

Applying this factorization to the bracketed term gives

S = (-1/g)^(20m+2)[ g^(20m+2) – g^2 ][ g^(20m+2) + 1/g^2 ]/Sqrt(5)

= { [ g^(10m) – (-1/g)^(10m)]/sqrt(5)}*[ g^(10m+2) + (-1/g)^(10m+2)]

= F_10m*[ g^(10m+2) + (-1/g)^(10m+2)]

Source(s): http://en.wikipedia.org/wiki/Fibonacci_number#Clos…51