Fibonacci Generating Functions

Michael P. Knapp Department of Mathematics and Statistics Loyola University Maryland 4501 North Charles Street Baltimore, MD 21210 USA

                      mpknapp@loyola.edu

Abstract

Define an integer sequence (G_{n})_{n∈ℤ} by setting G_{0} = a, G_{1} = b, and G_{n} = G_{n−1} + G_{n−2} for all n. In this paper, we explore the problem of finding all rational numbers x such that the generating function of the sequence yields an integer when evaluated at x. We show that these numbers can be naturally divided into families and find some families that are always present. Then we give an algorithm that, for each choice of a and b, reduces the problem of finding all of the families to a finite computation.

1 Introduction

In a 2015 article [3] in the College Mathematics Journal, Hong studied the generating functions for the Fibonacci (\underline{A000045}) and Lucas (\underline{A000032}) numbers. For each sequence, Hong found a set of rational values of x such that the generating function evaluated at x is an integer, and asked whether more such values existed. This question was answered in 2017 by Pongsriiam [7], who found additional values of x which worked, and gave a proof that he had found all such values. Around the same time Bulawa & Lee [1] proved that for the Fibonacci sequence, if one only considers values inside the interval of convergence of the generating function, then Hong had found all the values of x such that the generating function is an integer. Moreover, they extended this work to more general sequences. If (a_{n})_{n≥0} is a sequence with a_{0} = 0 and a_{1} = 1 that satisfies a recurrence of the form a_{n} = Ma_{n−1} +Na_{n−2}, where M, N are positive integers with N|M, then Bulawa & Lee found all values of x in the interval of convergence of the generating function which make the generating function an integer.

In this article, we prove similar results for every sequence satisfying the Fibonacci recurrence. For integers a, b, we define the Fibonacci-like sequence G_{n}^{(a,b)} by

G_{0}^{(a,b)} = a, G_{1}^{(a,b)} = b, and G_{n}^{(a,b)} = G_{n−1}^{(a,b)} + G_{n−2}^{(a,b)} for n ≥ 2.

For example, the G_{n}^{(3,1)} sequence (\underline{A104449}) begins

3, 1, 4, 5, 9, 14, 23, 37, 60, 97, 157, 254, 411, ….

Setting (a, b) = (0, 1) gives the Fibonacci sequence F_{n}, and setting (a, b) = (2, 1) gives the Lucas sequence. Note that we can extend these sequences to negative indices by using the recurrence relation. For example, the relation says that we should have G_{1}^{(3,1)} = G_{0}^{(3,1)}+G_{−1}^{(3,1)}, and so we obtain G_{−1}^{(3,1)} = −2. This generalization of the Fibonacci sequence has been studied by many authors over a long period of time. See [8, 4, 5, 6, 2] for some examples of work done with these sequences. These are only examples, as a search for “generalized Fibonacci” on MathSciNet yields almost 2,000 results.

For each of these sequences, our goal is to find all the rational x-values which make its generating function an integer. We will show how to find all of these x-values for each possible pair (a, b). It turns out that these x-values come in families, where the elements of each family are ratios of consecutive terms of a sequence satisfying the Fibonacci recurrence. We show this in our first theorem.

Theorem 1. Let (a, b) ∈ ℤ^{2}, define the sequence G_{n}^{(a,b)} as above and let G^{(a,b)}(x) be the generating function for this sequence. Suppose that G^{(a,b)}(p/q) is an integer, where p and q are relatively prime integers. If p + q ≠ 0, then G^{(a,b)}(q/(p + q)) is an integer. Also, if p ≠ 0, then G^{(a,b)}((q − p)/p) is an integer.

After proving Theorem 1, we prove a corollary which, for each (a, b), gives two families of rational x-values such that G^{(a,b)}(x) is an integer. This corollary generalizes some of Pongsriiam’s results [7].

Corollary 2. Let (a, b) ∈ ℤ^{2} and define G_{n}^{(a,b)} and G^{(a,b)}(x) as above. The values F_{n}/F_{n+1} produce integer values of G^{(a,b)}(x) for all integers n ≠ −1, and the values x = −G_{n+1}^{(a,b)}/G_{n}^{(a,b)} produce integer values of G^{(a,b)}(x) whenever G_{n}^{(a,b)} ≠ 0.

As we will see in Lemmas 8 and 9, we can also describe the second family as ratios of consecutive terms of a sequence H_{n} satisfying the Fibonacci recurrence, where H_{0} = −b and H_{1} = a. To make our results somewhat easier to state, we will say that a number x is good for (a, b) if x is rational and G^{(a,b)}(x) is an integer. For example, the first part of Corollary 2 says that the ratio F_{n}/F_{n+1} is good for all (a, b) whenever n ≠ −1. If the pair (a, b) is clear from context, then we will just say that the number x is good.

Our next theorem is a partial converse of Theorem 1, in which we start with a given sequence H_{n}.

Theorem 3. Suppose that p and q are integers with gcd(p, q) = 1, and let H_{n} be the sequence with H_{0} = p, H_{1} = q, and H_{n} = H_{n−1} + H_{n−2} for all integers n. Then there exist infinitely many pairs (a, b) such that all the values x = H_{n}/H_{n+1} (with H_{n+1} ≠ 0) are good for (a, b). Specifically, these ratios are good for (a, b) if and only if

a ≡ −bp(q − p)^{−1} ≡ −bqp^{−1} (mod |q^{2} − pq − p^{2}|).

In this theorem, if |q^{2} − pq − p^{2}| = 1, then we interpret congruence modulo 1 as being the trivial ring, and so the congruence condition is always satisfied. This occurs when H_{n} is the sequence of Fibonacci numbers, possibly multiplied by −1 and possibly with shifted indices (for example, when H_{n} = F_{n+3}). In particular, this interpretation gives meaning to the theorem when either p or q − p equals 0.

Finally, given the pair (a, b), we show how to find all x-values that are good for (a, b). We will prove the following theorem.

Theorem 4. Let (a, b) ∈ ℤ^{2} with (a, b) ≠ (0, 0), and define G^{(a,b)}(x) as above. Set

C = \begin{cases}\sqrt{|a^{2} + ab − b^{2}|}, & if a^{2} + ab − b^{2} < 0; \\ \sqrt{\frac{1}{5}(a^{2} + ab − b^{2})}, & if a^{2} + ab − b^{2} > 0, \end{cases}

and find all integers M with |M| ≤ C such that the equation M^{2} + 3MN + N^{2} = a^{2} + ab − b^{2} has an integer solution N. For each of these M-values, let k be a nonzero integral solution of the equation M^{2} = 5k^{2} + (2b − 6a)k + (a − b)^{2}, and set x = (a − b − k + M)/2k. Then x is good for (a, b) and generates a family of good values. All families of good values for (a, b) can be found in this way, except possibly the one corresponding to the Fibonacci sequence and the one containing the solution of G^{(a,b)}(x) = 0.

The remainder of this article is divided into three sections. In the next section, we will give the relatively simple proofs of Theorem 1, Corollary 2, and Theorem 3. In Section 3, we prove Theorem 4 and give some examples of using the method to find all the good values for some specific choices of (a, b). The final section acknowledges the contributions of colleagues with whom the author had some valuable conversations.

2 Families of good x-values

In this section, we prove Theorem 1, Corollary 2, and Theorem 3. For a pair (a, b), define the sequence G_{n}^{(a,b)} as in the introduction. Since this notation is somewhat awkward, we will drop the superscript from all of our notation unless we need the superscript to ensure clarity. Thus we will write G_{0} = a, G_{1} = b, etc., and the generating function for this sequence will be written as G(x).

As a trivial case, if a = b = 0, then G_{n} = 0 for all n, and G(x) is identically zero. Clearly, every rational number is good, and then Theorem 1, Corollary 2, and the congruence in Theorem 3 are trivially true. For the rest of this article, we will assume that (a, b) ≠ (0, 0).

We begin by finding a formula for G(x).

Lemma 5. The generating function for the sequence G_{n} is

G(x) = \frac{(b − a)x + a}{1 − x − x^{2}}.  (1)

Proof. The generating function for our sequence is

G(x) = G_{0} + G_{1}x + G_{2}x^{2} + G_{3}x^{3} + G_{4}x^{4} + · · · .

This immediately yields

xG(x) = G_{0}x + G_{1}x^{2} + G_{2}x^{3} + G_{3}x^{4} + ⋯

and

x^{2}G(x) = G_{0}x^{2} + G_{1}x^{3} + G_{2}x^{4} + · · · .

We can then see that

G(x) − xG(x) − x^{2}G(x)
= G_{0} + (G_{1} − G_{0})x + (G_{2} − G_{1} − G_{0})x^{2} + (G_{3} − G_{2} − G_{1})x^{3} + ⋯
= a + (b − a)x.

Note that the recursion relation for the sequence ensures that the coefficients of x^{2}, x^{3}, … are all zero. The formula for G(x) now follows.

Now that we have a formula for G(x), we prove a lemma about when a rational number p/q is good for (a, b). This allows us to avoid repeating the same argument several times in the proofs below.

Lemma 6. Suppose that (a, b) ≠ (0, 0), and suppose that p and q are relatively prime integers. Then x = p/q is good for (a, b) if and only if we have

a ≡ −bp(q − p)^{−1} ≡ −bqp^{−1} (mod |q^{2} − pq − p^{2}|).

Proof. Since gcd(p, q) = 1, it is easy to check that gcd(q − p, q^{2} − pq − p^{2}) = gcd(p, q^{2} − pq − p^{2}) = 1, and so both inverses exist. Moreover, since p^{2} ≡ q(q − p) (mod |q^{2} − pq − p^{2}|), we always have −bp(q − p)^{−1} ≡ −bqp^{−1} (mod |q^{2} − pq − p^{2}|).

Now, we have

G(p/q) = \frac{(b − a)(\frac{p}{q}) + a}{1 − \frac{p}{q} − \frac{p^{2}}{q^{2}}} = \frac{q((b − a)p + aq)}{q^{2} − pq − p^{2}}.  (2)

Since the numerator and denominator are integers (and since having (p, q) ≠ (0, 0) implies that q^{2} − pq − p^{2} ≠ 0), the final fraction is an integer if and only if we have

q((b − a)p + aq) ≡ 0 (mod |q^{2} − pq − p^{2}|).

Since gcd(q, q^{2} − pq − p^{2}) = 1, the number G(p/q) is an integer if and only if

(b − a)p + aq ≡ 0 (mod |q^{2} − pq − p^{2}|).

A little algebra shows that this is equivalent to having

a ≡ −bp(q − p)^{−1} (mod |q^{2} − pq − p^{2}|).  (3)

This completes the proof of the lemma.

Now that we have Lemma 6, we can give the proof of Theorem 1. Suppose that p and q are relatively prime integers, and that G(p/q) is an integer. By Lemma 6, we know that a ≡ −bp(q − p)^{−1} ≡ −bqp^{−1} (mod |q^{2} − pq − p^{2}|). To show that G((q − p)/p) is an integer when p ≠ 0, we have

G((q − p)/p) = \frac{p((b − a)(q − p) + ap)}{p^{2} − (q − p)p − (q − p)^{2}} = \frac{p(b(q − p) − a(q − p) + ap)}{−(q^{2} − pq − p^{2})}.

The negative sign in the denominator does not matter for determining whether this expression is an integer, so we have G((q − p)/p) ∈ ℤ if and only if

p(b(q − p) − a(q − p) + ap) ≡ 0 (mod |q^{2} − pq − p^{2}|).

However, if we replace the first occurrence of a by −bp(q−p)^{−1} and the second by −bqp^{−1}, we can see that the expression on the left-hand side is in fact congruent to zero. This completes the proof that G((q − p)/p) ∈ ℤ. The proof that G(q/(p + q)) ∈ ℤ when p + q ≠ 0 is similar, and will be omitted. This completes the proof of Theorem 1.

By Theorem 1, we can see that if we have a good x-value x = p/q (in lowest terms), then if we form a sequence H_{n} by setting H_{0} = p, H_{1} = q, and H_{n} = H_{n−1} + H_{n−2} for all n ∈ ℤ, then all of the values x = H_{n}/H_{n+1} are good for (a, b), provided only that we have H_{n} ≠ 0 for all n. However, if we define our sequence this way, then since gcd(p, q) = 1, we have gcd(H_{n}, H_{n+1}) = 1 for all n. Therefore, the only way that we could have H_{n} = 0 is if we have either (H_{n−2}, H_{n−1}) = (1, −1) or (H_{n−2}, H_{n−1}) = (−1, 1). But both of these possibilities occur in the Fibonacci sequence (extended to negative subscripts). Hence, if we have a good x-value x = p/q such that p and q are not consecutive elements of the Fibonacci sequence, then no element of the sequence H_{n} is equal to 0.

Given these observations, we can prove Corollary 2 without much difficulty. First we deal with the quotients of Fibonacci numbers.

Lemma 7. If (a, b) ∈ ℤ^{2}, then the values x = F_{n}/F_{n+1} with n ≠ −1 are all good for (a, b).

Proof. The value n = −1 is excluded because F_{0} = 0 may not be the denominator. For the rest of the values, by Theorem 1 it suffices to prove that both x = F_{0}/F_{1} = 0 and x = F_{−2}/F_{−1} = −1 are good. But it is trivial to see that G(0) = a and G(−1) = 2a − b are both integers. This completes the proof.

Now that we have shown that the x-values coming from the Fibonacci sequence are good for all (a, b), we will often assume throughout the rest of this article that the family of xvalues that we are dealing with does not come from the Fibonacci sequence. This allows us to simplify our proofs a bit, since as mentioned above, for other families of x-values we do not need to worry about the possibility that the recursion formula gives us a denominator of zero. We now begin the proof of the second half of Corollary 2.

Lemma 8. For a choice of the parameter (a, b), define a sequence H_{n} by setting H_{0} = −b, H_{1} = a, and H_{n} = H_{n−1} + H_{n−2} for all n ∈ ℤ. Then the values x = H_{n}/H_{n+1} are good for (a, b) whenever H_{n+1} ≠ 0.

Proof. If −b and a are consecutive Fibonacci numbers, or if they are consecutive Fibonacci numbers multiplied by the same nonzero integer, then we are done by Lemma 7. Otherwise, we have H_{n} ≠ 0 for all n, and it suffices to check that x = H_{0}/H_{1} = −b/a is good for (a, b). But we can see that G(−b/a) = a, completing the proof.

Our next lemma completes the proof of Corollary 2.

Lemma 9. The values of x obtained in Lemma 8 are exactly the values x = −G_{n+1}/G_{n}, where n ∈ ℤ.

Proof. We begin by showing that for all n, we have

H_{n} = (−1)^{n+1}G_{1−n}.  (4)

This is true for n = 0 and n = 1. Suppose that it is true for all nonnegative n up to n = k−1. Then we have

H_{k} = H_{k−1} + H_{k−2}
= (−1)^{k}G_{2−k} + (−1)^{k−1}G_{3−k}
= (−1)^{k−1}(−G_{2−k} + G_{3−k})
= (−1)^{k−1}G_{1−k}
= (−1)^{k+1}G_{1−k},

as desired. The proof that the formula holds for all negative n is similar.

Finally, using the relation (4), we have

H_{n}/H_{n+1} = −G_{−n+1}/G_{−n} and − G_{n+1}/G_{n} = H_{−n}/H_{−n+1}

for each integer n. This shows that the values of −G_{n+1}/G_{n} are exactly the ratios of successive terms of the H sequence, completing the proof.

We now prove Theorem 3, in which we study the problem from the other point of view. That is, we assume that we are given a sequence H_{n} satisfying the Fibonacci recurrence and ask for which (a, b) the values x = H_{n}/H_{n+1} are good. The proof essentially just combines Lemma 6 and Theorem 1. Theorem 3 is clearly true when H_{n} is the Fibonacci sequence, so suppose that this is not the case. Then no term of the sequence H_{n} is zero. Theorem 1 then implies that the all the values x = H_{n}/H_{n+1} are good for (a, b) if and only if x = H_{0}/H_{1} = p/q is good for (a, b). But Lemma 6 says that this happens if and only if a ≡ −bp(q − p)^{−1} ≡ −bqp^{−1} (mod |q^{2} − pq − p^{2}|). Finally, to show that there are infinitely many pairs (a, b) for which the family is good, we simply note that we can choose any integer we like for b, and then there are infinitely many integers a such that a ≡ −bqp^{−1} (mod |q^{2} − pq − p^{2}|).

Example 10. Let L_{n} be the Lucas sequence, so that p = L_{0} = 2 and q = L_{1} = 1. Then Theorem 3 shows that the ratios L_{n}/L_{n+1} all produce integer values of G(x) = G^{(a,b)}(x) if and only if a ≡ 2b (mod 5). Thus, for each b, there are infinitely many a such that the ratios of successive Lucas numbers are good for (a, b).

3 Finding all good x-values for (a, b)

In this section, we will prove Theorem 4. That is, given the pair (a, b), we will see how to find all rational x such that G(x) = G^{(a,b)}(x) is an integer. Following Pongsriiam’s [7] ideas, suppose that k ∈ ℤ with k ≠ 0 and that G(x) = k. Solving this equation for x, we find that

x = \frac{a − b − k ± \sqrt{5k^{2} + (2b − 6a)k + (a − b)^{2}}}{2k} .  (5)

In order for x to be rational, we need the expression under the square root to be a perfect square. For a particular value x = p/q, we will write the square root term as M(a, b, p, q), where we take M to be positive or negative as needed so that we can write

x = \frac{p}{q} = \frac{a − b − k + M(a, b, p, q)}{2k}.  (6)

Solving this for M(a, b, p, q) and using the fact that

k = G(\frac{p}{q}) = \frac{q((b − a)p + aq)}{q^{2} − pq − p^{2}},

we find that

M(a, b, p, q) = \frac{(2p + q)((b − a)p + aq)}{q^{2} − pq − p^{2}} − a + b.  (7)

We now give some facts about the expression M(a, b, p, q) which are useful. Note that since we are no longer considering x-values coming from the Fibonacci sequence, the conditions that q ≠ 0 and p + q ≠ 0 and p + 2q ≠ 0 are automatically satisfied.

Lemma 11. Suppose that (a, b) ∈ ℤ^{2} and that p, q ∈ ℤ with q ≠ 0 and p + q ≠ 0 and p + 2q ≠ 0. Then we have

M(a, b, p + q, p + 2q) = −3M(a, b, q, p + q) − M(a, b, p, q)  (8)

and

M(a, b, p, q)^{2} + 3M(a, b, p, q)M(a, b, q, p + q) + M(a, b, q, p + q)^{2} = a^{2} + ab − b^{2}. (9)

Proof. We use the computer algebra system Maple to do the algebra necessary to verify these identities. If we define M(a, b, p, q) as in (7), then the command

simplify(M(a, b, p + q, p + 2*q) + 3*M(a, b, q, p + q) +
                    M(a, b, p, q));

produces the output 0 and the command

simplify(M(a, b, p, q)^2 + 3*M(a, b, p, q)*M(a, b, q, p + q) +
                    M(a, b, q, p + q)^2);

produces the output a^{2} + ab − b^{2}. This completes the proof.

We can use (8) and (9) to reduce the problem of finding all families of good x-values to a finite computation. To do this, suppose that x is good for (a, b) and consider the M-values coming from the family of good values containing x. We will show that at least one of these M-values is small in a sense that we make precise in the next two lemmas. The results of these lemmas depend on the sign of a^{2} + ab − b^{2}, so we note that since (a, b) ≠ (0, 0), this expression cannot equal 0.

Lemma 12. Suppose that a^{2} + ab − b^{2} < 0 and that x is good for (a, b). Then the set of M-values corresponding to the family of good numbers including x contains an element M_{0} with |M_{0}| ≤ \sqrt{|a^{2} + ab − b^{2}|}.

Proof. Choose M_{0} = M(a, b, p, q) such that |M_{0}| is minimal among the M-values under consideration, and define M_{1} = M(a, b, q, p + q) and M_{−1} = M(a, b, q − p, p). Note that M_{0} = 0 is impossible by (9). Also, since a^{2} + ab − b^{2} < 0, we see by (9) that both M_{1} and M_{−1} have the opposite sign from M_{0}.

Suppose first that M_{0} > 0. Then M_{1}, M_{−1} < 0. Since |M_{0}| is minimal, we in fact have M_{1}, M_{−1} ≤ −M_{0}. Using (8), we see that

M_{1} = −3M_{0} − M_{−1} ≤ −M_{0},

which gives M_{−1} ≥ −2M_{0}. Therefore, there is a real number t, with −2 ≤ t ≤ −1, such that M_{−1} = tM_{0}. An essentially identical argument shows that we can also find such a t when M_{0} < 0. From (9), we have

M_{−1}^{2} + 3M_{−1}M_{0} + M_{0}^{2} = a^{2} + ab − b^{2},

whence

M_{0}^{2} = \frac{a^{2} + ab − b^{2}}{t^{2} + 3t + 1} = \frac{|a^{2} + ab − b^{2}|}{|t^{2} + 3t + 1|}.

Since −2 ≤ t ≤ −1, we have −1.25 ≤ t^{2} + 3t + 1 ≤ −1, and therefore |t^{2} + 3t + 1| ≥ 1. This gives us

M_{0}^{2} ≤ |a^{2} + ab − b^{2}|,

which obviously implies |M_{0}| ≤ \sqrt{|a^{2} + ab − b^{2}|}.

Lemma 13. Suppose that a^{2} + ab − b^{2} > 0, and that x is good for (a, b). Then the set of M-values corresponding to the family of good numbers including x contains an element M_{0} with |M_{0}| ≤ \sqrt{\frac{1}{5}(a^{2} + ab − b^{2})}.

Proof. Define M_{−1}, M_{0}, and M_{1} as in the proof of Lemma 12. If it happens that M_{0} = 0, then we are done, so suppose that M_{0} ≠ 0. We first show that either the pair M_{−1}, M_{0} or the pair M_{0}, M_{1} have the same sign. Assume that this is false, and that M_{−1} and M_{1} both have the opposite sign from M_{0}. Then we may proceed as in the proof of Lemma 12 to show that

M_{0}^{2} = \frac{a^{2} + ab − b^{2}}{t^{2} + 3t + 1} ,  (10)

where −2 ≤ t ≤ −1. However, the right-hand side of (10) is negative, providing a contradiction.

Now, set N to be either M_{−1} or M_{1}, whichever value has the same sign as M_{0}. Then by (9), we have

a^{2} + ab − b^{2} = M_{0}^{2} + 3M_{0}N + N^{2}
= |M_{0}|^{2} + 3|M_{0}||N| + |N|^{2}
≥ 5|M_{0}|^{2},

where the inequality follows from the minimality of |M_{0}|. This immediately leads to the bound |M_{0}| ≤ \sqrt{\frac{1}{5}(a^{2} + ab − b^{2})}.

We can now reduce the problem of finding all the good x-values for (a, b) to a finite computation. Suppose that (a, b) is given. We know that the family coming from the Fibonacci sequence is good for (a, b). Next, if possible, we solve the equation G(x) = 0, obtaining the good value x = −a/(b−a). This also yields a family of good x-values. Finally, we find all the remaining families. Define

C = \begin{cases}\sqrt{|a^{2} + ab − b^{2}|}, & if a^{2} + ab − b^{2} < 0; \\ \sqrt{\frac{1}{5}(a^{2} + ab − b^{2})}, & if a^{2} + ab − b^{2} > 0. \end{cases}

First, we find all values of M with 0 ≤ M ≤ C such that the equation

M^{2} + 3MN + N^{2} = a^{2} + ab − b^{2}  (11)

has an integer solution N. These values, along with their negatives, are all the possible M-values with |M| ≤ C. For each M-value, we may use the relation

M^{2} = 5k^{2} + (2b − 6a)k + (a − b)^{2}  (12)

to find all the possible k associated with this value of M. Then the equation (6) gives a good x-value, which generates a family of good x-values. Since every family of good x-values yields at least one M-value in our range, all families of good x-values are found in this way. This completes the proof of Theorem 4.

Example 14. As a first example, we will take (a, b) = (14, 1) and find all families of good x-values. First, we know that all values in the family coming from the Fibonacci sequence are good for (14, 1). Solving the equation G(x) = 0 gives x = 14/13, which leads to the family

…, \frac{−16}{15}, \frac{15}{−1}, \frac{−1}{14}, \frac{14}{13}, \frac{13}{27}, \frac{27}{40}, \frac{40}{67}, …

of good x-values, which is the family given in Lemma 8. To find other families, the equation (11) becomes

M^{2} + 3MN + N^{2} = 209,

and we need to find all M with |M| ≤ \sqrt{209/5} ≈ 6.46 such that (11) has an integer solution N. If we test all the integers M with 0 ≤ M ≤ 6, then we find that M = 1 and M = 5 have the property we need. Hence the values with |M| ≤ 6 having the property are M = −5, −1, 1, 5. For M = −5, the relation (12) becomes

25 = 5k^{2} − 82k + 169.

This leads to the possible k-values of 2 and 72/5. We discard the latter as 72/5 is not an integer, and we see that (a, b, k, M) = (14, 1, 2, −5) leads by (6) to x = 3/2. Thus every element of the family

…, \frac{−5}{4}, \frac{4}{−1}, \frac{−1}{3}, \frac{3}{2}, \frac{2}{5}, \frac{5}{7}, \frac{7}{12}, …

is a good x-value for (a, b) = (14, 1). Similarly, the value M = −1 leads to x = −1/14, which yields (again) the family given in Lemma 8, and the value M = 1 leads to x = 0, which yields (again) the family of ratios of Fibonacci numbers given in Lemma 7. Finally, the value M = 5 leads to the family

…, \frac{−10}{7}, \frac{7}{−3}, \frac{−3}{4}, \frac{4}{1}, \frac{1}{5}, \frac{5}{6}, \frac{6}{11}, …,

which is the last family of good x-values for (14, 1).

Example 15. Let a = 1 and b = 11, so that a^{2} + ab − b^{2} = −109. As above, we know that the family coming from the Fibonacci sequence is good for (1, 11). Solving the equation G(x) = 0 gives x = −1/10, which leads to the family

…, \frac{23}{−12}, \frac{−12}{11}, \frac{11}{−1}, \frac{−1}{10}, \frac{10}{9}, \frac{9}{19}, \frac{19}{28}, …

of good values, which is the family from Lemma 8. Searching for other families, the equation (11) becomes M^{2} + 3MN + N^{2} = −109, and we need to find integers M with |M| ≤ \sqrt{| − 109|} ≈ 10.4 such that at least one corresponding N is an integer. The only such values are M = 10 and M = −10. However, when we use (12) to find the corresponding value of k, we see that both of these M-values yield k = 0. Thus we do not obtain additional families of good x-values.

Remark 16. Note that in Example 15, we did not obtain the family coming from the Fibonacci sequence when solving the equation (9) and using the M-values. This is because the smallest M-value in this family is M(a, b, p, q) = M(1, 11, 1, 0) = −10. However, (p, q) = (1, 0) corresponds to the “fraction” 1/0, which is undefined. It is for this reason that we treat this family in separately in our method. Similarly, we treat the family coming from the solution of G(x) = 0 separately because having k = 0 leads to a zero in the denominator of (5). No other family can lead to any of our equations having zeros in the denominator, so only these two families need to be treated separately.

Remark 17. After this example, it seems natural to ask about pairs (a, b) for which the only good families of x-values are those given in Lemma 7 and Lemma 8. If we study pairs of the form (a, 1), a computer search shows that there are 311 values of a with 3 ≤ a ≤ 1000 such that the pair (a, 1) has only these two families of good x-values. We conjecture that infinitely many such pairs exist. Note in the opposite direction that Theorem 4 shows that there are infinitely many (a, b) that have more families of good x-values than the two given by these lemmas.

4 Acknowledgments

The author would like to thank Professor Paulo H. A. Rodrigues (Universidade Federal de Goiás) and Professor Bruno de Paula Miranda (Instituto Federal de Goiás) for some very helpful conversations about this problem. Those conversations led to a proof that there are infinitely many values of a such that the pair (a, 1) has more good x-values than the ones given in Lemma 7 and Lemma 8, although that proof was much different than the one given here. The author would also like to thank the anonymous referee and the editor for their helpful comments.

References

[1] A. Bulawa and W. K. Lee, Integer values of generating functions for the Fibonacci and related sequences, Fibonacci Quart. 55 (2017), 74–81.

[2] D. A. Englund and M. Bicknell-Johnson, Maximal subscripts within generalized Fibonacci sequences, Fibonacci Quart. 38 (2000), 104–113.

[3] D. S. Hong, When is the generating function of the Fibonacci numbers an integer?, College Math. J. 46 (2015), 110–112.

[4] A. F. Horadam, A generalized Fibonacci sequence, Amer. Math. Monthly 68 (1961), 455–459.

[5] T. Koshy, Fibonacci and Lucas Numbers with Applications, Wiley-Interscience, 2001.

[6] A. Pethő, The Pell sequence contains only trivial perfect powers. In Sets, Graphs and Numbers (Budapest, 1991), Vol. 60 of Colloq. Math. Soc. János Bolyai, pp. 561–568. North-Holland, 1992.

[7] P. Pongsriiam, Integral values of the generating functions of Fibonacci and Lucas numbers, College Math. J. 48(2) (2017), 97–101.

[8] A. Tagiuri, Di alcune successioni ricorrenti a termini interi e positivi, Periodico di Matematica 16 (1901), 1–12.

2020 Mathematics Subject Classification: Primary 11B39. Keywords: generating function, Fibonacci recurrence.

(Concerned with sequences \underline{A000032}, \underline{A000045}, and \underline{A104449}.)

Received June 8 2023; revised version received February 14 2024. Published in Journal of Integer Sequences, February 21 2024.

Return to Journal of Integer Sequences home page.