Az Eszterházy Károly Tanárképző Főiskola Tudományos Közleményei. 1998. Sectio Mathematicae. (Acta Academiae Paedagogicae Agriensis : Nova series ; Tom. 25)

JONES, J. P. and Kiss, P., Representation of integers as terms of a linear recurrence with maximal index

24 James P. Jones and Péter Kiss Proof. AF

n

+i = A(F

n..i + F

n) = AF

n.

x + AF

n = H

n(A, A) implies n < R(AF

n

+1). For (i) suppose A < F

n and n + 1 < R(AF

n+i). By the Intermediate Value Lemma there exist c > 1 and d > 1 such that AF

n+i = cF

n + dF

n

+1. Then F

n+

1 | cF

n and (F

n,F

n+

1) = 1 imply F

n+

1 | c. Hence F

n

+i < c so that cf = 0. Hence R(AF

n

+1) = n. For (ii) suppose F

n < A. Then there exist b and t such that A = tF

n + 6, 1 < b and 1 < t. Let a = tF

n

+1. Then ifn+i = (*F

n+i)F

n + bF

n+

1 = iT

n+

1 (iF

n+

16) = iT

n

+i(a,6), 1 < a and 1 < b. Hence n + 1 < R(AF

n+i) so that n < R(AF

n

+1). Corollary 1.10. For all n > 0, fí(F

nF

n

+i) = n. Lemma 1.11. If F

nF

n+\ < N, then n < R(N). Proof. Suppose F

nF

n

+i < N

. We shall show that n + 1 < R(N) by finding a and b such that N = 7/

n+

1(a,6) = aF

n + 6F

n+

1, 1 < a and 1 < 6. Let b be the least positive solution to the congruence N = bF

n+\ (mod F

n), (taking b = F

n, if F

n | N

, so that b > 1). We claim (1.12) bF

n+

l + F

n < N. This inequality (1.12) will be proved by considering two cases: Case 1. N = 0 (mod F

n). Then b = F

n. Since F

n | N and F

nF

n+

1 < N, we have F

n(F

n

+i + 1) < N. So we have F

n+

16 + F

n = F

n+

i F

n + F

n = F

n(F

n

+i + 1) < iV, and so (1.12) holds. Case 2. ÍV ^ 0 (mod F

n). Then 1 < 6 < F

n, so b < F

n - 1. Therefore ^^n+i + F

n < (F

n — l)F

n+

1 -f F

n = F

nF

n

+i + (F

n - F

n

+i) < F

nF

n+1 < A

r and so again (112) holds. Now that (1.12) is established, let a = (N — 6F

n+i)/F

n. Then a is an integer, N = aF

n + bF

n+i — H

n+i(a,b

) and (1.12), implies 1 < a. Corollary 1.13. If 1 < n and F

2

n < N, then n < R(N). Proof. By Lemma 1.11. If 1 < n, then F

n+

i < L

n and F

nF

n

+i < F

nL

n = F

2

n < N

. Lemma 1.14. If 1 < N, then R{N) < ([1 + 2.128 • ln(JV))J

. Proof. Let r = R(N). The inequahty holds for N = 1, since R{ 1) = 1. Suppose N > 2. Then 2 < r. Let k = r -f 1. Then 3 < k so that we can use the inequality (1.15) (8/5)*~

2 < F

k (3 < Ä). (This inequahty, which is well known, is easy to prove by induction on k > 3, using the fact that if x = 8/5, then x

2 < x + 1). Using the inequality