### Fibonacci Multiple Puzzle

**Source:**Mailed to me by Kushagra Singhal, Ex-IIT Kanpur, PhD Student at University of Illinois at Urbana-Champaign

**Problem:**

Prove that for any positive K and a natural number n, every (n*K)th number in the Fibonacci sequence is a multiple of the Kth number in the Fibonacci sequence.

More formally, for any natural number n, let F(n) denote Fibonacci number n. That is, F(0) = 0, F(1) = 1, and F(n+2) = F(n+1) + F(n). Prove that for any positive K and natural n, F(n*K) is a multiple of F(K).

Lemma. F(n) = F(k+1).F(n-k) + F(k).F(n-k-1)

ReplyDeleteProof.

F(n)

= F(2).F(n-1) + F(1).F(n-2)

= F(3).F(n-2) + F(2).F(n-3)

= ...

= F(k+1).F(n-k) + F(k).F(n-k-1)

Now for proof of the main question, suppose F(k) divides F((n-1)k) [inductive hypothesis].

From above lemma, we have,

F(n.k) = F(k+1).F((n-1).k) + F(k).F((n-1)k - 1)

Since F(k) divides F((n-1)k), F(k) divides F(n.k).

QED

Use the formula for F_n given here. https://www.math.hmc.edu/funfacts/ffiles/10002.4-5.shtml

ReplyDeleteAlso, a-b divides a^n-b^n. Let a=Phi^k and b=phi^k. Observe that the factor (a^n-b^n)/(a-b) is an integer.

We prove this using induction. Before that, we make a small observation about Fibonacci numbers

ReplyDeleteFor any positive integer k,

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

F(k+3) = 2*F(k+1) + F(k)

F(K+4) = 3*F(k+1) + 2*F(k)

...

F(k+m) = F(m)*F(k+1) + F(m-1)*F(k)

where m is a positive integer

We need to prove that for a positive integers K and n, F(n*K) = c*F(K) where c is a positive integer.

Setting K to be any positive integer, and applying induction on n,

The base case is n = 1. F(K) = 1*F(K). Thus the base case holds.

Assuming the statement is true for some n. F(n*K) = c*F(K)

Now,

F((n+1)*K) = F(n*K+K) = F(K)*F(n*K+1) + F(K-1)*F(n*K)

But F(n*K) = c*F(K).

Thus F((n+1)*K) = F(K)*(F(n*K+1)+c*F(K-1)) = c'*F(K) where c' is a positive integer

Thus the induction holds.

The given statement is true for all positive integers K and n.

Lemma:

ReplyDeleteFor 0 <= k < n:

F(n) = F(k+1) * F(n-k) + F(k) * F(n-k-1)

This can be proven by induction on k.

base case k = 0:

F(n) = 1 * F(n) + 0 * F(n-1)

induction:

Since F(n-k) = F(n-k-1) + F(n-k-2), one can rearrange coefficients, so that

F(n) = F(k+1) * F(n-k) + F(k) * F(n-k-1)

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

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

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

To finish, use induction on n to show that F(n*K) is a multiple of F(K).

base case n = 0:

F(0) = 0 is a multiple of F(K)

induction:

By the lemma,

F((n+1)*K) = F(K+1) * F(n*K) + F(K) * F(n*K-1)

and since both F(n*K) and F(K) are multiple of K, so is F((n+1)*K)

Here is a brute force method:

ReplyDeleteits well known that F(n)= [a^n-b^n]/sqrt (5) where a= (1+sqrt(5))/2 and b= (1-sqrt(5))/2.

so its required to prove that [a^(n*k)-b^(n*k)]/(a^k-b^k) is a whole number.

in fact a little algebra shows that above expression is a whole number for natural n and k ,and real numbers a and b , provided a+b and a*b are whole numbers.

outline of proof:

let x=a^k and y=b^k.

prove by induction , that x^i+y^i is a whole number for any natural i.

its clear that for natural i , (x*y)^i is also a whole number as a*b is a whole number.

expression of interest = [x^n-y^n]/[x-y].

=sigma (x^i)* y^(n-1-i), i = 0 to n-1.

if n is even, the expression equals sigma (x*y)^i * [ (x^(n-1-2*i)+y^(n-1-2*i) ], i = 0 to (n-2)/2

if n is odd , the expression equals (x*y)^((n-1)/2) +sigma (x*y)^i * [ (x^(n-1-2*i)+y^(n-1-2*i) ], i = 0 to (n-3)/2.

hence proved as (x*y)^i and x^i+y^i are whole numbers for all natural numbers i.

Assume that F(nK) is a multiple of F(K). We shall prove that F((n+1)K) is also a multiple of F(K).

ReplyDeleteF(nK+2) = F(nK+1) + F(nK)

F(nK+3) = F(nK+2) + F(nK+1) = 2F(nK+1) + F(nK)

F(nK+4) = F(nK+3) + F(nK+2) = 3F(nK+1) + 2F(nK)

F(nK+5) = F(nK+4) + F(nK+3) = 5F(nK+1) + 3F(nK)

F(nK+6) = F(nK+5) + F(nK+4) = 8F(nK+1) + 5F(nK)

.

.

.

F(nK+i) = F(i) F(nK+1) + F(i-1) F(nK)

Thus, when i=K, we have F((n+1)K) = F(K) F(nK+1) + F(K-1) F(nK), which is a multiple of F(K) as both terms are multiples of F(K) (recall that F(nK) is a multiple of F(K)).

F(n+1) = F(n-1)+F(n)

ReplyDeleteF(n+2) = F(n-1)+2F(n)

F(n+3)= 2F(n-1)+3F(n)

.

.

.

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

so, F(2n) = F(n)F(n-1)+F(n+1)F(n) = t*F(n)

induction:

assume F(nk) = L*F(n) ( since we proved F(2n) = t*F(n))

F(n(k+1)) = F(nk+n)=F(n)F(nk-1)+F(n+1)(F(nk) = L*F(n))

rhs is divisible by F(n)

Any fibonacci number could be written as sum of any two (lower) value of fibonacci numbers. for example:

ReplyDeletef(10) = f(9) + f(8)

= 2f(8) + f(7)

= 3f(7) + 2f(6)

and so on..

So, if we split f(nk) it could be written as

f(nk) = x1*f(k+1) + x2*f(k)

These coefficients also follows fibonacci pattern. For example:

f(10) = f(2)*f(10-1) + f(1)*f(10-2)

= f(3)*f(10-2) + f(2)*f(10-3)

= f(4)*f(10-3) + f(3)*f(10-4)

and so on...

therefore x1 will be equals to f((n-1)k)

now the equation could be written as:

f(nk) = f((n-1)k)*f(k+1) + x2*f(k)

which could be re-written as

f(nk) = [ f((n-1)k) ] *f(k+1) + x2*f(k)

= [ x3*f(k+1) + x4*f(k) ] * f(k+1) + x2*f(k)

= [ f((n-2)k)*f(k+1) + x4*f(k) ] * f(k+1) + x2*f(k)

and so on...

and the final equation would be like:

f(nk) = f(k)*a1*f(k+1) + a2*f(k)

= f(k) [ a1*f(k+1) + a2 ]

and at one point the coefficient of f(k+1) will be a multiple of f(k).

Hence every f(nk) has f(k) as its factor.