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

22 James P. Jones and Péter Kiss The first few values of R are given by R( 1) = 1, R(

2) = 2, R(

3) = 3, R(

4) = 3, R{

5) = 4, i?(6) = 3, i2(7) = 4, i2(8) = 5, R(

9) = 4, £(10) = 4, Ä(ll) = 5. R(12) = 4 and £(13) = 6. Note that the function R is not increasing. That is, TV < M does not imply R(N) < R(M). Since R(N) is well defined, Cohn's problem becomes one of giving an algorithm to compute R(N). In this paper we shall give a simple algorithm which solves this problem. We shall also show that this algorithm is polynomial time, that is the time to find R(N) is less than a polynomial in In(N). We also prove some theorems about the number of N such that R(N) = r and about the number of pairs (a,b) such that H

r(a

:b

) = N

. First we need some lemmas. 1. Representation of N in the form N = H

r(a,b

) with r maximal We use [xj to denote the floor of x, (integer part of x). [x] denotes the ceiling of x, [x] = -["^J- F

n denotes the n

t

h Fibonacci number, where F

0 = 0, Fi = 1 and F;

+

2 = F\

: + Fi+1- L

n denotes the n

t

h Lucas number, defined by L

0 = 2, — 1 and = L

l + Z

t

+1- We define //_

n(a,6) by Hn(a,b) — ( —l)

n+

1//

n( —a, 6 — a). Below we shall use many elementary identities and inequalities such as L

n

+1 = 2

F

n + F

n

+1, L

n + 1 < F

n

+

2 for 1 < n and F

n+

1 < L

n, for 2 < n. We shall also need the following well known identity due to HORADAM [3]. Lemma 1.1. For a

11 integers n,a and b, H

n(a. b

) = aF

n-1 + bF

n. Proof. By induction on n using F,+

2 = F{ -f . The result can also be seen to hold for negative n since Hn(a,b) = (-1 )

n(aF

n+

1 — bF

n). Lemma 1.2. H

n(a, 6) = H

n(a -f F

n, b — F

n_i

) and H

n(a, b) = i^nía — F

n, 6 + F

n_i). Lemma 1.3. For all integers n, k

, a and 6, we have (0 ffnM) = + («) H

n(a,b)= H

n_

k(H

k(a,b),H

k+

l(a,b)), (iii) II

n(a,b) = /f

n

+i(6 - a, a). (ii>) &) = b), Bik(a, b)). Proof. They follow from the definitions. Lemma 1.4. If N = H

r(a,b), 1 < a, 1 < b and R(N) = r, then b < a. Proof. Suppose R(n

) = r and N = H

r(a, b). If a < b, then by Lemma 1.3 we would have N = H

r(a,b) = //

r+

1 (6 - a, a) so that r + 1 < R(N

), contradicting r = R(N).