Some Remarks On the Equation F_{n} = kF_{m} In Fibonacci Numbers

M. Farrokhi D. G. Faculty of Mathematical Sciences Ferdowski University of Mashhad Iran

                   m.farrokhi.d.g@gmail.com

Abstract Let {F_{n}}_{n=1}^{∞} = {1, 1, 2, 3, …} be the sequence of Fibonacci numbers. In this paper we give some sufficient conditions on a natural number k such that the equation F_{n} = kF_{m} is solvable with respect to the unknowns n and m. We also show that for k > 1 the equation F_{n} = kF_{m} has at most one solution (n, m).

1 Preliminaries

Let F_{n} be the nth Fibonacci number, i.e.,

F_{1} = F_{2} = 1 , F_{n+2} = F_{n} + F_{n+1}, ∀n ∈ ℕ.

It is known that these numbers have the following properties :

(1) F_{m+n} = F_{m−1}F_{n} + F_{m}F_{n+1};

(2) gcd(F_{m}, F_{n}) = F_{gcd(m,n)};

(3) if m|n, then F_{m}|F_{n};

(4) if F_{m}|F_{n} and m > 2, then m|n. Now, put

P = {k ∈ ℕ : ∃m, n ∈ ℕ, F_{n} = kF_{m}},
Q = {k ∈ ℕ : ∄m, n ∈ ℕ, F_{n} = kF_{m}}.

A simple computations show that the natural numbers which satisfy in P, less than 100, are as follows:

1, 2, 3, 4, 5, 7, 8, 11, 13, 17, 18, 21, 29, 34, 47, 48, 55, 72, 76, 89.

By definition of P and the properties (3) and (4), for each k ∈ P there exist m, n ∈ ℕ such that k = \frac{F_{mn}}{F_{n}}. However, it seems that the elements of Q do not have any special form.

Using a theorem of R. D. Carmichael [2], it can be shown that the product of Fibonacci numbers and their quotients belong to Q except for some cases (see Theorem 3.10).

In this paper, we use elementary methods to prove our claim. In section 3, we obtain some more properties of P. For example, we show that for every element k(> 1) of P, the equation F_{n} = kF_{m} has a unique solution (n, m). Moreover, we give a necessary and sufficient condition for which the product of two elements of P is again in P.

2 The Main Theorem

In this section, we introduce some elements k in Q, so that for each fixed n ∈ ℕ,

k = F_{a_{1}}F_{a_{2}} ⋯ F_{a_{n}}

belongs to Q, for all natural numbers a_{1}, …, a_{n} but a finite number.

In order to prove the above claim, we need the following elementary properties of Fibonacci numbers.

Lemma 2.1. For all a, b, c, a_{1}, a_{2}, …, a_{n} ∈ ℕ, the following conditions hold a) F_{a+b−1} = F_{a}F_{b} + F_{a−1}F_{b−1};

b) F_{a+b−2} = F_{a}F_{b} − F_{a−2}F_{b−2};

c) F_{a+b+c−3} = F_{a}F_{b}F_{c} + F_{a−1}F_{b−1}F_{c−1} − F_{a−2}F_{b−2}F_{c−2};

d) if n ≥ 3, then F_{a_{1}+···+a_{n}−n} ≥ F_{a_{1}}F_{a_{2}} ⋯ F_{a_{n}}.

Proof. Parts (a) and (b) are easily verified.

(c) Using (1), we obtain

F_{a+b+c−3} = F_{a−1}F_{b+c−3} + F_{a}F_{b+c−2}
= F_{a−1}(F_{b−2}F_{c−2} + F_{b−1}F_{c−1}) + F_{a}(F_{b}F_{c} − F_{b−2}F_{c−2})
= F_{a}F_{b}F_{c} + F_{a−1}F_{b−1}F_{c−1} − (F_{a} − F_{a−1})F_{b−2}F_{c−2}
= F_{a}F_{b}F_{c} + F_{a−1}F_{b−1}F_{c−1} − F_{a−2}F_{b−2}F_{c−2}.

(d) We use induction on n. By part (c), the result holds for n = 3. Now assume it is true for n ≥ 3. Clearly

F_{a_{1}+···+a_{n+1}−(n+1)} = F_{a_{n+1}−1}F_{a_{1}+···+a_{n}−(n+1)} + F_{a_{n+1}}F_{a_{1}+···+a_{n}−n}
≥ F_{a_{n+1}}F_{a_{1}+···+a_{n}−n}
≥ F_{a_{1}}F_{a_{2}} ⋯ F_{a_{n+1}},

which gives the assertion.

Remark 1. In Lemma 2.1(d), if a_{1} = ⋯ = a_{n} = 1, then a_{1} + ⋯ + a_{n} − (n + 1) = −1 and by generalizing the recursive relation for negative numbers, we get F_{−1} = F_{1} − F_{0} = 1.

Remark 2. Note that all the formulas in Lemma 2.1 can be also deduced from Binet’s formula

F_{n} = \frac{α^{n} − β^{n}}{\sqrt{5}} ,

where

α = \frac{1 + \sqrt{5}}{2}, β = \frac{1 − \sqrt{5}}{2}.

Lemma 2.2. Suppose m, n and k are any natural numbers with k|n, then

\frac{F_{mn}}{F_{n}} ≡^{F_{k}} mF_{n−1}^{m−1}.

Proof. We proceed by induction on m. Clearly, the result is true for m = 1. Assume it is true for m. Now, using (1) and (3), we have

\frac{F_{(m+1)n}}{F_{n}} ≡^{F_{k}} F_{n−1} \frac{F_{mn}}{F_{n}} + F_{mn+1}
≡^{F_{k}} mF_{n−1}^{m} + F_{mn+1}
≡^{F_{k}} mF_{n−1}^{m} + F_{n−1}F_{(m−1)n+1} + F_{n}F_{(m−1)n+2}
≡^{F_{k}} mF_{n−1}^{m} + F_{n−1}F_{(m−1)n+1}
⋮
≡^{F_{k}} mF_{n−1}^{m} + F_{n−1}^{m}
≡^{F_{k}} (m + 1)F_{n−1}^{m}.

Lemma 2.3. Let a_{1}, …, a_{n}, n ≥ 3 and F_{a_{1}}F_{a_{2}} ⋯ F_{a_{n}} = F_{b}, then

b + n ≤ a_{1} + ⋯ + a_{n} ≤ b + 2n − 2.

Proof. By Lemma 2.1, F_{b} = F_{a_{1}}F_{a_{2}} ⋯ F_{a_{n}} ≤ F_{a_{1}+a_{2}+···+a_{n}−n} and hence b ≤ a_{1} + a_{2} + ⋯ + a_{n} − n. This gives the left hand side of the inequality. By repeated application of Lemma 2.1 we have

F_{b} = F_{a_{1}}F_{a_{2}} ⋯ F_{a_{n}}
≥ F_{a_{1}+a_{2}−2}F_{a_{3}} ⋯ F_{a_{n}}
≥ F_{a_{1}+a_{2}+a_{3}−4}F_{a_{4}} ⋯ F_{a_{n}}
⋮
≥ F_{a_{1}+···+a_{n}−2(n−1)},

and so b ≥ a_{1} + ⋯ + a_{n} − 2(n − 1), which completes the proof.

Remark 3. Note that using Binet’s formula, for n > 2, one obtains

(1 − β^{8})α^{n} ≤ \sqrt{5}F_{n} ≤ (1 + β^{6})α^{n},

which implies the following inequalities

vn − u ≤ a_{1} + ⋯ + a_{n} − b ≤ un − v,

where

u = −\frac{log((1 − β^{8})/\sqrt{5})}{log α} = 1.717 …

and

v = −\frac{log((1 + β^{6})/\sqrt{5})}{log α} = 1.559 ….

One observes that the above inequalities are sharper than Lemma 2.3.

Definition. A solution of the equation F_{a_{1}}F_{a_{2}} ⋯ F_{a_{n}} = F_{b} is said to be nontrivial, whenever a_{1}, …, a_{n} ≥ 3 or equivalently F_{a_{1}}, …, F_{a_{n}} > 1.

Lemma 2.4. The equation F_{a}F_{b} = F_{c} has no nontrivial solution, for any natural numbers a, b and c.

Proof. We may assume a ≤ b and the triple (a, b, c) is a nontrivial solution of the equation, i.e., a, b ≥ 3. Clearly, F_{b}|F_{c} and hence b|c. Now put c = kb which gives k ≥ 2 and therefore F_{a}F_{b} = F_{kb} ≥ F_{2b} = F_{b}(F_{b−1} + F_{b+1}) > F_{b}^{2} ≥ F_{a}F_{b}, which is impossible.

We are now able to prove the main theorem of this section.

Theorem 2.5. For each fixed n ≥ 2, the equation F_{a_{1}}F_{a_{2}} ⋯ F_{a_{n}} = F_{b} has at most finitely many nontrivial solutions.

Proof. By Lemma 2.4, the result follows for n = 2. Assume, n ≥ 3 and let (a_{1}, …, a_{n}; b) be a nontrivial solution of the equation. Without loss of generality, we may assume 3 ≤ a_{1} ≤ a_{2} ≤ ⋯ ≤ a_{n}. Put a_{1} + ⋯ + a_{n} = b + k. Clearly, by Lemma 2.3 there are only finitely many natural numbers k, which can satisfy the latter equation. As F_{a_{n}}|F_{b} and a_{n} ≥ 3, we have a_{n}|b and so b = k′a_{n} for some k′ ∈ ℕ. Similarly, F_{a_{n−1}}|F_{b} = F_{k′a_{n}} and a_{n−1} ≥ 3, which implies that a_{n−1}|k′a_{n} and so a_{n−1} = k′′k′′′ with k′′|k′ and k′′′|a_{n}. Now since F_{k′′′}|F_{a_{n−1}}|\frac{F_{k′an}}{F_{an}}, Lemma 2.2 implies that F_{k′′′}|k′. By Lemma 2.3, there are only finitely many k, k′, k′′, k′′′ satisfying these equations. Thus there are only finitely many choices for a_{n−1} and consequently for a_{1}, …, a_{n−2}. Finally, there are only finitely many choices for a_{n} and b satisfying the equation.

Remark 4. The above theorem shows that except finitely many cases if k = F_{a_{1}} ⋯ F_{a_{n}}, where a_{1}, …, a_{n} ≥ 3 the equation F_{t} = kF_{s} has no solution.

3 Some More Results

In this section, we consider some more properties of the elements of P and Q. For instant, it is shown that every element k > 1 of P satisfies a unique equation of the form F_{n} = kF_{m}.

Theorem 3.1. The equation F_{a}F_{b} = F_{c}F_{d} holds for natural numbers a, b, c, d if and only if F_{a} = F_{c} and F_{b} = F_{d}, or F_{a} = F_{d} and F_{b} = F_{c}.

Proof. Clearly, if one the numbers a, b, c or d, (a, say), is less than 3 then F_{b} = F_{c}F_{d} and Lemma 2.4 implies that either F_{c} = F_{a} = 1 and F_{b} = F_{d}, or F_{d} = F_{a} = 1 and F_{b} = F_{c}. Therefore, we assume that a, b, c, d ≥ 3 and by symmetry we may assume that 3 ≤ a ≤ b, c, d. Using Lemma 2.1, we have

F_{a+b−2} < F_{a}F_{b} = F_{c}F_{d} < F_{c+d−1},

which implies that a + b − 2 < c + d − 1 and hence a + b ≤ c + d. Similarly c + d ≤ a + b and so a + b = c + d. By repeated application of Lemma 2.1, we obtain

F_{a}F_{b} = F_{c}F_{d}
⇒ F_{a−1}F_{b−1} = F_{c−1}F_{d−1}
⋮
⇒ F_{2}F_{b−a+2} = F_{c−a+2}F_{d−a+2}
⇒ F_{b−a+2} = F_{c−a+2}F_{d−a+2}.

Now by Lemma 2.4, F_{c−a+2} = 1 or F_{d−a+2} = 1, which implies that either a = c and b = d, or a = d and b = c.

The following corollaries follow immediately.

Corollary 3.2. Suppose \frac{F_{a}}{F_{b}} = \frac{F_{c}}{F_{d}} ≠ 1, then F_{a} = F_{c} and F_{b} = F_{d}.

Corollary 3.3. Every element k > 1 of P satisfies a unique equation of the form F_{n} = kF_{m}, for some natural numbers m and n.

Corollary 3.4. The least common multiple of two Fibonacci numbers is again a Fibonacci number if and only if one divides the other.

Proof. Suppose lcm(F_{m}, F_{n}) = F_{k}, for some natural numbers m and n. Then clearly

F_{m}F_{n} = gcd(F_{m}, F_{n})lcm(F_{m}, F_{n}) = F_{gcd(m,n)}F_{k}

and so gcd(F_{m}, F_{n}) = F_{gcd(m,n)} is either F_{m} or F_{n}. Hence either F_{m}|F_{n} or F_{n}|F_{m}.

Theorem 3.5. For any natural numbers a, b, c, d and e, the equation F_{a}F_{b}F_{c} = F_{d}F_{e} has no nontrivial solution.

Proof. Assume (a, b, c; d, e) is a nontrivial solution of the equation F_{a}F_{b}F_{c} = F_{d}F_{e}. Hence a, b, c, d, e ≥ 3. By Lemma 2.1, we have

F_{a+b+c−4} < F_{a}F_{b}F_{c} = F_{d}F_{e} < F_{d+e−1}

and

F_{d+e−2} < F_{d}F_{e} = F_{a}F_{b}F_{c} ≤ F_{a+b+c−3},

which imply that a + b + c = d + e + 2. Using Lemma 2.1 once more and noting the identity a + b + c − 3 = d + e − 1, we obtain

F_{d+e−4} ≤ F_{d−1}F_{e−1}
= F_{a−1}F_{b−1}F_{c−1} − F_{a−2}F_{b−2}F_{c−2}
< F_{a−1}F_{b−1}F_{c−1}
≤ F_{a+b+c−6}.

Thus d + e + 2 < a + b + c, which is impossible.

Theorem 3.6. Let (a, b, c; d, e, f) be a nontrivial solution of the equation F_{a}F_{b}F_{c} = F_{d}F_{e}F_{f}, then a, b, c are equal to d, e, f, in some order.

Proof. Without loss of generality, we may assume that a ≤ d, 3 ≤ a ≤ b ≤ c and 3 ≤ d ≤ e ≤ f. If a = d, the result follows immediately by Theorem 3.1. Now assume that a < d. Using Lemma 2.1, we have

F_{a+b+c−4} < F_{a}F_{b}F_{c} = F_{d}F_{e}F_{f} ≤ F_{d+e+f−3}

and

F_{d+e+f−4} < F_{d}F_{e}F_{f} = F_{a}F_{b}F_{c} ≤ F_{a+b+c−3}.

Thus a + b + c = d + e + f, and so by Lemma 2.1 we obtain

F_{a−1}F_{b−1}F_{c−1} − F_{a−2}F_{b−2}F_{c−2} = F_{d−1}F_{e−1}F_{f−1} − F_{d−2}F_{e−2}F_{f−2}
2F_{a−2}F_{b−2}F_{c−2} − F_{a−3}F_{b−3}F_{c−3} = 2F_{d−2}F_{e−2}F_{f−2} − F_{d−3}F_{e−3}F_{f−3}
⋮

Hence for each i ≥ 1

F_{i+1}F_{a−i}F_{b−i}F_{c−i} − F_{i}F_{a−i−1}F_{b−i−1}F_{c−i−1} = F_{i+1}F_{d−i}F_{e−i}F_{f−i} − F_{i}F_{d−i−1}F_{e−i−1}F_{f−i−1}.

By replacing i by a in the above equality, we obtain

0 ≥ −F_{a}F_{b−a−1}F_{c−a−1} = F_{a+1}F_{d−a}F_{e−a}F_{f−a} − F_{a}F_{d−a−1}F_{e−a−1}F_{f−a−1} ≥ 0.

Then

F_{a+1}F_{d−a}F_{e−a}F_{f−a} − F_{a}F_{d−a−1}F_{e−a−1}F_{f−a−1} = 0,

which is impossible, since otherwise we must have

F_{d−a}F_{e−a}F_{f−a} = F_{d−a−1}F_{e−a−1}F_{f−a−1} = 0,

which implies that d = a.

The following corollary is an immediate consequence of the above theorem.

Corollary 3.7. Let x = \frac{F_{a}}{F_{b}} , y = \frac{F_{c}}{F_{d}} be in P. Then xy ∈ P if and only if one of the following occurs

i) x = 1;

ii) y = 1;

iii) x = y = 2;

iv) F_{a} = F_{d}, or

v) F_{b} = F_{c}.

Now we turn to the equation F_{a_{1}}F_{a_{2}} ⋯ F_{a_{n}} = F_{b}. The special case when a_{i}’s are equal follows easily from the following theorem. We are not aware of its proof so we prove it here (see [3]).

Theorem 3.8. Let p be a prime and let m and n be natural numbers such that p ∤ m and p^{α}∥F_{n}, for α > 0. Then

i) p^{α+1}∥F_{nmp}, if (p, α) ≠ (2, 1);

ii) p^{α+2}∥F_{nmp}, if (p, α) = (2, 1).

Proof. By the assumption and Lemma 2.2,

\frac{F_{nm}}{F_{n}} ≡^{p} mF_{n−1}^{m−1}.

Thus if p ∤ m then p^{α}∥F_{nm} and hence it is enough to show that p^{α+1}∥F_{np}. By repeated applications of (1), we have

\frac{F_{pn}}{F_{n}} = F_{n−1} \frac{F_{(p−1)n}}{F_{n}} + F_{(p−1)n+1}
= F_{n−1} (F_{n−1} \frac{F_{(p−2)n}}{F_{n}} + F_{(p−2)n+1}) + F_{(p−1)n+1}
⋮
= F_{n−1}^{p−1} + F_{n−1}^{p−2}F_{n+1} + F_{n−1}^{p−3}F_{2n+1} + ⋯ + F_{n−1}F_{(p−2)n+1} + F_{(p−1)n+1}.

Now, for each k ∈ ℕ

F_{kn+1} = F_{n}F_{(k−1)n} + F_{n+1}F_{(k−1)n+1}
≡^{p^{2α}} F_{n+1}F_{(k−1)n+1}
⋮
≡^{p^{2α}} F_{n+1}^{k}
≡^{p^{2α}} (F_{n} + F_{n−1})^{k}
≡^{p^{2α}} kF_{n}F_{n−1}^{k−1} + F_{n−1}^{k}.

Hence

\frac{F_{pn}}{F_{n}} ≡^{p^{2α}} F_{n−1}^{p−1} + F_{n−1}^{p−2}F_{n+1} + ⋯ + F_{n−1}F_{(p−2)n+1} + F_{(p−1)n+1}
≡^{p^{2α}} F_{n−1}^{p−1} + F_{n−1}^{p−2}(F_{n} + F_{n−1}) + ⋯ + F_{n−1} ((p − 2)F_{n}F_{n−1}^{p−3} + F_{n−1}^{p−1})
+ ((p − 1)F_{n}F_{n−1}^{p−2} + F_{n−1}^{p−1})
≡^{p^{2α}} \frac{p(p − 1)}{2}F_{n}F_{n−1}^{p−2} + pF_{n−1}^{p−1},

which implies that p^{α+1}∥F_{np} whenever (p, α) ≠ (2, 1). This proves (i).

Now, if (p, α) = (2, 1) then F_{n} is even, 3|n and \frac{n}{3} is odd. On the other hand, 8∥F_{6} and by the proof of part (i), 8∥F_{2n} which completes the proof of part (ii).

Theorem 3.9. For all k > 1, the equation F_{n} = F_{m}^{k} has only the solutions F_{m} = F_{n} = 1, or k = 3, m = 3 and n = 6.

Proof. Let k > 1, n ≥ m ≥ 3 and F_{n} = F_{m}^{k}. As F_{m}|F_{n}, we have m|n and so n = dm, for some d ∈ ℕ. Also, by Lemma 2.2, F_{m}|d. Now, if p is a prime divisor of F_{m} such that p^{a}∥F_{m}, where (p, a) ≠ (2, 1), then p is also a divisor of d and by Theorem 3.8, p^{a+b}∥F_{n}, where p^{b}∥d. On the other hand, p^{ka}∥F_{n} and so a + b = ka, i.e., b = (k − 1)a. Now, we have

k − 1 ≥ d = p^{b}d′ ≥ p^{b} = p^{(k−1)a} ≥ p^{k−1} ≥ k,

which is impossible and hence F_{m} = 2. If p > 3 and p divides n, then F_{p}|2^{k}, which is also impossible. Hence n = 2^{s}3^{t} and as F_{4}, F_{9} ∤ 2^{k}, we must have n = 6.

R. D. Carmichael [2] showed that if n > 2 and n ≠ 6, 12 then F_{n} has a prime divisor p, which does not divide the Fibonacci numbers F_{m}, for all 1 ≤ m < n. Applying this result one can obtain the general solutions of the equation F_{a_{1}} ⋯ F_{a_{m}} = F_{b} and more generally the solutions of the equation F_{a_{1}} ⋯ F_{a_{m}} = F_{b_{1}} ⋯ F_{b_{n}}. For some applications of this beautiful theorem, see [1].

We say a solution of the equation F_{a_{1}} ⋯ F_{a_{m}} = F_{b_{1}} ⋯ F_{b_{n}} is nontrivial, whenever a_{i}, b_{j} ≥ 3 and a_{i} ≠ b_{j}, for all i = 1, …, m and j = 1, …, n.

Theorem 3.10. i) The only nontrivial solutions of the equation F_{a_{1}}F_{a_{2}} ⋯ F_{a_{n}} = F_{b} with n > 1 and a_{1} ≤ ⋯ ≤ a_{n} are

(3, 3, 3; 6) , (3, 4, 4, 6; 12) , (3, 3, 3, 3, 4, 4; 12)

ii) The only nontrivial solutions of the equation F_{a_{1}} ⋯ F_{a_{m}} = F_{b_{1}} ⋯ F_{b_{n}} are

(3, …, 3; 6, …, 6) , m = 3n
(\overbrace{3, …, 3}^{a}, \overbrace{6, …, 6}^{b}, 4, …, 4; 12, …, 12) , a + 3b = 4n
(\overbrace{3, …, 3}^{a}, 4, …, 4; \overbrace{6, …, 6}^{b}, 12, …, 12) , a = 3b + 4n
(\overbrace{6, …, 6}^{a}, 4, …, 4; \overbrace{3, …, 3}^{b}, 12, …, 12) , 3a = b + 4n

Proof. The proofs of both parts follow easily from Carmichael’s theorem.

The following theorem is another consequence of Carmichael’s theorem.

Theorem 3.11. Suppose p_{1}, p_{2}, …, p_{n} are arbitrary distinct prime numbers. Then there are only finitely many n-tuples (a_{1}, …, a_{n}) of nonnegative integers such that p_{1}^{a_{1}} ⋯ p_{n}^{a_{n}} ∈ P.

Proof. Assume {(a_{i_{1}}, …, a_{i_{n}})}_{i=1}^{∞} is an infinite sequence of distinct n-tuples such that for each i the number k_{i} = p_{1}^{i_{1}} ⋯ p_{n}^{i_{n}} belongs to P. Then there exist some natural numbers m_{i} and n_{i} such that F_{n_{i}} = k_{i}F_{m_{i}}. Without loss of generality, we may assume that n_{i} ≠ m_{i} and n′_{i}s are all distinct and greater than 12. Since there are infinitely many n-tuples, we may ignore the prime factors of the equations F_{n_{i}} = k_{i}F_{m_{i}} so that we obtain an equation of type as in Theorem 3.10, which contradicts Theorem 3.10.

Although we were able to obtain the general solutions of the equation F_{a_{1}} ⋯ F_{a_{n}} = F_{b} using Carmichael’s theorem, an elementary proof may nevertheless be of interest.

4 Acknowledgment

The author would like to thank the referee for some useful suggestions and corrections.

References

[1] Y. Bugeaud, F. Luca, M. Mignotte and S. Siksek, On Fibonacci numbers with few prime divisors, Proc. Japan Acad. Ser. A 81 (2005), 17–20.

[2] R. D. Carmichael, On the numerical factors of the arithmetic forms α^{n} ± β^{n}, Ann. Math. (2) 15 (1913/14), 30–48.

[3] S. Vajda, Fibonacci & Lucas Numbers, and the Golden Section, Ellis Horwood Limited, Chichester, England, 1989.

2000 Mathematics Subject Classification: Primary 11B39; Secondary 11B50, 11D99. Keywords: Fibonacci numbers.

(Concerned with sequence \underline{A000045}.)

Received March 28 2007; revised version received May 22 2007. Published in Journal of Integer Sequences, June 4 2007.

Return to Journal of Integer Sequences home page.