Prove the sum of any 10 consecutive terms of the Fibonacci sequence is multiple of 11?

Answer 1

Let's pull two consecutive numbers out of the fibonacci sequence to build a "basis" for our ten. Call them a1 and a2. They can be any numbers out of the sequence that we like, so long as a2 comes right after a1.

The question is, how can we show that the expression a1+a2+a3+a4+a5+a6+a7+a8+a9+a10 is divisible by 11.

All we need to do is rewrite the a1...a10 sequence in terms of a1 and a2. remember that
a3 = a1+a2
a4 = a2+a3 = a2+a1+a2 = a1 + 2a2, and so on and so forth.

Sum these all up and you'll end up with 55a1 + 88a2. No matter what the values of a1 and a2 are, the sum will always be divisible by 11 because 11 is a factor of the coefficients.

Answer 2

The first answer demonstrates that this holds good for any series generated by the rule "each term is the sum of the previous two terms", not just for the original Fibonacci series starting 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 etc

Suppose the series starts with 2, 7 and proceeds 9, 16, 25, 41, 66, 107, 173, 280, 453

The first ten terms add up to 726 = 11 x 66 (11 x the 7th term) = 55 x a1 (2) + 88 x a2 (7) = 110 + 616

Terms a2 to a11 add up to 1177 = 11 x 107 (again 11 x the 7th term) = 55 x a2 (7) + 88 x a3 (9) = 385 + 792 = 1177

And the reason is that the divisibility by 11 of the sum (55 x a1 + 88 x a2) is independent of the particular values of a1 and a2 that you care to insert,

The discovery that the sum of the ten terms a1 through a10 is precisely 11 x a7 is a pleasing one, Would anyone like to prove it!?

Answer 3

Yeah, like John C said.

Alternately, use the identity F(n+i)= F(n-1) *F(i) + F(n) *F(i+1) with n=10 to get F(i+10) = F(9)*F(i) + F(10)*F(i+1) = 34*F(i) + 55F(i+1). So then you use this as part of your inductive step. Show by calculating that F0+...+F9 is divisible by 11. Inductively, assume Fi+...+F(i+9) is divisible by 11. What's the next term? F(i+1)+...+F(i+10) which is the = to old sum + {F(i+10) - F(i)} and that new add-on is F(i+10)-F(i) = 34*F(i) + 55F(i+1) - F(i) = 33*F(i) + 55F(i+1) which is divisible by 11. So the new sum is the sum of two terms each divisible by 11.

Answer 4

John C pretty much already proved that the sum is 11a7. The total sum is 55a1 + 88a2. a7 = a5 + a6 = a3+a4+a4+a5 = a1 + a2 + a2 + a3 +a2 +a3 + a3 + a4 or a1 + 3a2 + 3a3 + a4. That equals a1 + 3a2 + 3a1 + 3a2 +a2 + a3 = 4a1 + 7a2 +a1 + a2 = 5a1 + 8a2, which is 1/11 of the sum 55a1 + 88a2.

Answer 5

F[n] = ((1+Sqrt[5])^n - (1-Sqrt[5])^n))/(Sqrt[5] 2^n)
S = Sum_{n:k,k+9}[F[n] = 11 function[k]
function[k] must be an integer ==> S divides by 11.