5 4

FIBONACCI NUMBERS AND SOME PRIME RECIPROCALS
R. S. BUCKNELL
Chiangmai, Thailand
The s e r i e s of Fibonacci n u m b e r s h a s been shown to b e a r s o m e i n t e r e s t ing r e l a t i o n s h i p s to the r e c i p r o c a l s of c e r t a i n p r i m e n u m b e r s .
F o r instance,
Maxey Brooke and C. R. Wall set up as P r o b l e m s B-14 (Fibonacci Q u a r t e r l y ,

Vol. 1 (1963), No. 2, p . 86) to show
00
Z F 1 0 " n = 10/89
n=i
(1)
00
X) ( - D n + 1 F 1 0 " n n=l
(2)
10/109 ,
where F
F 0u = 0, Fi1 = 1.
L = F , + F ,
n+2
n+l
n
The r e l a t i o n s h i p (1) is but a s p e c i a l c a s e of the g e n e r a l p r o p e r t y
oo
(3)
E V- n - i
n=i
x4 - x - 1
w h e r e x, an i n t e g e r >2 9 i s the r a d i x in t e r m s of which the n u m b e r (x2 - x - 1)

and the Fibonacci n u m b e r s a r e e x p r e s s e d .
Equation (3) is r e a d i l y proved by
considering
00
(x* - x - 1) F x" 1 1 - 1 =
^
n
n=l
00
00
00
F x- 1 1 - 1 - x F x- 1 1 - 1 - F x" 1 1 " 1
, n
^ n
., n
n=i
n=i
n=i
X2
00
00
00
n
11 1
n+1
F x --n+l
- v^
T,
F x ~" n - v^
-r.
F x-- n
n
n
~l
i
n=i
E F ^ x H - F ^ F ^ l - r E F ^ x . F ^ l
11=1
J
Ln=i
J
295

r
00
-i
LF X
- ,
L
[Oct.
1"
n=1
since
Fi = F2 = 1
and
tL^ Fn+2
_ x-11"1 - ^f) Fn+i x-11-1 - t FnX-11"1 = 0 .
n=i
n=i
n=i
Note that x 2 - x - 1 m a y be c o m p o s i t e (e. g. , for x = 8, 13),
but that x 2 - x
- 1 and x a r e r e l a t i v e l y p r i m e .
Another i n t e r e s t i n g r e l a t i o n s h i p that h a s been d i s c o v e r e d to exist between
t h e s e r i e s of Fibonacci n u m b e r s and the n u m b e r
emplified by the s p e c i a l c a s e w h e r e
N = 109.
1/N = l / ( x 2 - x - 1) i s e x It is found that the 108-digit
p e r i o d of 1/109 i s
009174311926605504587155963302752293577981651376146788990925688073394495412844036697247706422018348623853211 .
A g e n e r a l i z a t i o n is p o s s i b l e for the n u m b e r N - x
i n t e g e r >2,
y = x - 1) when 1/N
shown that if the p e r i o d of 1/N
- x - l - y
+y - l
(x an
i s expanded in t e r m s of r a d i x y. It will be
i s the (N - 1)-digit n u m b e r
N-l
F
then the n u m b e r
N-l
Fny
n=i
1967]
h a s as i t s l a s t N - 1 digits the n u m b e r
Let the r e s i d u e , R,
P.
be defined by
N-l
(4)
n-l
= n=l
E V
R =
The e x p r e s s i o n
N-l
n-l
E V
n=i
will b e s u m m e d using
,n
- b
a - b
where
1 + V5
,
1 - V5
a =
, b = x
Then
N-l
Z
n=l
-n n - l
F Jy
n
N-l [7 n
,n\
o
a - b 1
n=i
N-l
1
n-l
Cay)n - (by)n]/(a - b)y
n=i
N_
^ N-l-,-,
n
yJ F A T - + Jy
FAT - 1
N-l
N
y2 + y - i
..
N-l
AT
r + y -1
-N-l
y
-DFN-I
.,
- 1
+ F
-x]
296
297
[Oct.
Now consider the term
urn
_z
y2 + y - i
Clearly no factor of y will divide y2 + y - 1,

are relatively prime,
hence y ~
and y2 + y - 1
and since R is an integer, y ~ divides R. Thus
R is a number ending in N - 1 zeros when expressed in terms of radix y,

Since P contains not more than N - 1 digits, it follows that the number
N-l
V F y11"1 = P + R
L^
nJ
n=i
has as its last (N - 1) digits the number P.
*
NOTICE TO ALL SUBSCRIBERS!!!

Please notify the Managing Editor AT ONCE of any address change. The Post
Office Department, rather than forwarding magazines mailed third class, sends
them directly to the dead-letter office.
Unless the addressee specifically r e -
quests the Fibonacci Quarterly to be forwarded at first class rates to the new
address, he will not receive i t (This will usually cost about 30 cents for firstclass postage,) If possible, please notify us AT LEAST THREE WEEKS PRIOR
to publication dates: February 15, April 15, October 15, and December 15.

All subscription correspondence should be addressed to Brother A. Brousseau f

St. Mary ? s College, Calif. All checks ($4.00 per year) should be made out to
the Fibonacci Association or the Fibonacci Quarterly,
Manuscripts intended
for publication in the Quarterly should be sent to Verner E. Hoggatt, Jr. ,

Mathematics Department, San Jose State College, San Jose, Calif. All manuscripts should be typed, double-spaced. Drawings should be made the same size
as they will appear in the Quarterly, and should be done in India ink on either
vellum or bond paper. Authors should keep a copy of the manuscripts sent to
the editors.
* *
RESIDUES OF FIBONACCI-LIKE SEQUENCES

LAURENCE TAYLOR
Oak Ridge, Tennessee
In the February, 1964, issue of the Fibonacci Quarterly, Brother U.

Alfred [ l ] advanced the conjecture (later proved by J. H. Halton p i ) that,
when any Fibonacci number is divided by another Fibonacci number, one or the
other of the least positive and negative residues is again a Fibonacci number.
The object of this paper is to prove that the only Fibonacci-like sequence for
which this is true is the Fibonacci sequence. If zero is excluded as a remainder, then the Lucas sequence has the above property.
The proof falls naturally into two parts.
The first part will be to show
that every Fibonacci-like sequence, modulo any member of the sequence, is

congruent to a sequence made up of a subsequence of the original sequence and
the negatives of these values. The second part will be to show that these subsequences are actually remainders of the divisor for only the Fibonacci and
Lucas sequences.
Obviously, a sequence has the property described above if and only if any
non-zero integral multiple of it does.
Since any divisor of two neighboring
members of Fibonacci-like sequences divides every member of the sequence,

we will consider only sequences with neighboring terms relatively prime.
what follows,
H. will denote the i
sequence defined by H.
In
member of a general Fibonacci-like
= H. + H. , where H0 and Hj are arbitrary. The
set of integers will be denoted by I, the set of non-negative integers by P,

and the set of natural numbers by N.
PART I
Since it is easily established by induction that
H _Ll = F. H
+ F. ^ H
m+k
k m-i
k+l m
for all integers m and k, the following two lemmas readily follow.
Lemma 1: H , . = F.H J (mod H ) for all integers i.
to
m+i
1 m-i
m .
i+1
Lemma 2: H . = F .H
= (-l) H ,. (mod H ) for all integers i.
&
m-i
-i m-i
m+i
m
298
I967
299
It is known that any n u m b e r m u s t eventually divide one of the Fibonacci

n u m b e r s , and that F ^ _ l = F n _ 2 F
+ ( - l ) n for all i n t e g e r s n.
Applying t h e s e
r e s u l t s and L e m m a 1, it i s not difficult to p r o v e L e m m a s 3 and 4.

L e m m a 3: Let n be any i n t e g e r such that F
= 0 (mod H
).
Then
H ^
= 0 (mod H ) .
mn
m
L e m m a 4: F o r the n of L e m m a 3,
F2
= (-1)
(mod H
L e m m a 5: F o r the n of L e m m a 3, and for all i n t e g e r s

F
Proof:
For
i = 1,
i = k - 2,
) .
m
'
i,
H
. = (-l)n+i+1H
. (modH ) .
n-i m-i
m - n +M i
m
The proof i s by induction on

apply L e m m a 1.
i.
F o r i = 0,
apply L e m m a 3=
A s s u m e that L e m m a 5 holds for i = k - 1 and
o r that
F
H
= (-l)n+kH
^n a (mod H ) ,
n - i m - (nk - la)
m-n+(k-l)
m
H
ov = ( - l ) n + k ~ 1 H
v (mod H ) .
Mn
n - i m - (/fk - 2 )
m-n+(k-g)
m
Subtracting the f i r s t formula from the second yields the expected r e s u l t for
= k.
Hence, the formula i s c o r r e c t for all i E P .
L e m m a 2 can b e used to
extend the r e s u l t to include negative i n t e g e r s .

L e m m a 6; Let t = nq + r .
H
Proof:
Then, if q G N and F_ = 0 (mod H
),
_,. = F F ^ H
(mod H ) .
m-n+t
r n - i m - i4
m
T h e proof i s once again by induction on q.
When q = 1,
the
e x p r e s s i o n above b e c o m e s identical to L e m m a 1. A s s u m e that L e m m a 6 holds

for q = k - 1,
o r that
_,, = F. v F k ^H
m-n+t
t-(k-i)n n-i m - i
(mod H )
m
300
Oct.
But,
F , ,. * = F, , F
+ F, ,
F = F, . F
(mod H ), since H
t-(k-i)n
t-kn n - i
t-kn+i n
t-kn n - i
m
m
divides F by hypothesis. Substituting back into the formula above,
H
- = F. . Fk_1H
m-n+t
t-kn n-i m - i
(mod H
).
m
Hence, L e m m a 6 is t r u e for all q E N.

T h e o r e m 1:
F o r e v e r y i E I,
there exists a k E I ,
m - n ^ k 4 m,
such that
H. = H, (mod H ),
I
k
m
w h e r e n is the s m a l l e s t n a t u r a l n u m b e r such that F
= 0 (mod H
n
Proof: Let i = m - n + t,
k = m - n + r,
and t = nq + r ,
T h e c a s e q = 0 is t r i v i a l , since then t = p and i = k.

equivalent to t < 0.
H
^ =
m-n+t
Since - t > 0,
).
m
0 L r L n.
The c a s e q ^ 0 is
But, by L e m m a 2 and p r o p e r t i e s of c o n g r u e n c e s ,
(-l)t+1H
,A(modH
) = (-l)t+1H
. .. (mod H ) .
m-n+(-t)
m-n
m-n+(-t)
m
we need c o n s i d e r only the c a s e t > 0 o r q E N. By L e m m a 6,

H
_,_. = F F q _ 1 H
m-n+t
r n-i m-i
(mod H
).
m
By L e m m a 1,
F H
= (-l)r+1H
( m o d H ).
r m-i
m-r
m
Substituting,
H
^ = (-l)r+1Fq~*H
(mod H ) .
m-n+t
n-i m - r
m
By L e m m a 4,
F2
= (-l)n
n-i
We m u s t now distinguish two c a s e s .
(mod H
) .
nr
1967
301
C a s e I : If q is odd,
Fq-i
(_1)n(q-i)/2
leading to H
,, = H
(mod H ),
m-n+t
m-r
m
C a s e 2: If q i s even,
to
Fq-i
w h e r e m - n 4 m - r - m.
-
(_1)n(q-2)/2F
n-l
^ ^
(mQd
(mod H
n-i
}<
By L e m m a 5,
F
= (-l)n+r+1H
n-i m - r
^ (mod H ).
m-n+r
m
Substituting t h e s e two r e s u l t s l e a d s to
H
where
0 4 r 4 n,
^ = (-l)nq/2H
( m o d H ).
M
m-n+t
m-n+
r
m
s o m - n 4 m - n + r 4 m .
In T h e o r e m 1, if H
divides H., we can take k = m or k = m - n.

m
I
While every H. divides s o m e o t h e r m e m b e r of the sequence (see L e m m a 3),
it is n e c e s s a r y to notice that z e r o cannot a p p e a r as a m e m b e r of the subsequence
of T h e o r e m 1 u n l e s s our F i b o n a c c i - l i k e sequence is the Fibonacci sequence i t self.
Since z e r o can o c c u r a s a r e m a i n d e r in any F i b o n a c c i - l i k e sequence and
since T h e o r e m 1, applied to Fibonacci n u m b e r s , l e a d s to the t h e o r e m proved

by Halton in [2"|, the only F i b o n a c c i - l i k e sequence which s t r i c t l y fulfills the
r e q u i r e m e n t s of B r o t h e r Alfred 1 s conjecture i s the Fibonacci sequence.
In P a r t II, we will investigate F i b o n a c c i - l i k e s e q u e n c e s to d e t e r m i n e if
any o t h e r sequence l e a v e s r e s i d u e s which, in all c a s e s ,
are either zero or
equal in absolute value to m e m b e r s of the original sequence.

PART n
Now, if our sequence i s to have the d e s i r e d p r o p e r t y , t h e r e m u s t be a
set of e l e m e n t s of the sequence whose absolute v a l u e s a r e l e s s than that of
H
The f i r s t o b s e r v a t i o n to b e m a d e about F i b o n a c c i - l i k e s e q u e n c e s i s that

^
302
RESIDUES OF FIBONACCI-LIKE TSEQUENCES
far to the right and to the left,
Oct.
the absolute v a l u e s i n c r e a s e without l i m i t .
Hence, we need only e x a m i n e a s m a l l section of the whole sequence to d e t e r m i n e if it h a s the d e s i r e d p r o p e r t y .

T h e r e m u s t be at l e a s t one H. with a m i n i m a l absolute v a l u e , and, b e 1
'
c a u s e of t h e d i v e r g e n c e of the sequence in both d i r e c t i o n s , t h e r e can be only a

finite n u m b e r of such m i n i m a .
L e m m a 7:
If H0 i s a m i n i m u m ,
|H0( > 2,
then, if H$ > 0,
the
only
p o s s i b l e r e m a i n d e r equal in absolute value to a m e m b e r of the original sequence

upon division by H_
i s H 0 ,
and if B1 < 0,
the only such r e m a i n d e r for H2
i s H 0 .
Proof: If H0 i s negative, we will obtain the negative of the sequence for
H0 p o s i t i v e .
Hence, c o n s i d e r only H0 > 2.
be a m i n i m a , since each of
If Hi > 0,
None of Hj, H 2 , H_i, H_ 2
can
H.j = H0 > 2, i = 1 , 2, l e a d s to a contradiction.
to avoid |Hj| < H0 for s o m e i,
for the t e r m s n e a r H0
we
can have only the following:

H^ 3
3H0 + 2a =
H i + a
H^ 2 = -(H 0 + a)
H_i =
2H 0 + a
H0 - H 0
Hi =
3H0 + a
H2 = 4H 0 + a
H. = L.^Hn + F.a ,
i
where L
and F
If Hi < 0,
l+i
a > 1 ,
a r e r e s p e c t i v e l y the n
L u c a s and Fibonacci n u m b e r s .
with the conditions above we obtain
H. -
( - l ^ L . ^ H o + Fxx)
o r a new s e q u e n c e which, except for changes in sign, i s the sequence for H^ >
0 reflected about H 0 .
hi p a r t i c u l a r ,
H2 = - ( H 0 + a ) .
Notice that the sequence d i v e r g e s for I i | > 2. F r o m the sequence above,

it i s easy to s e e that the only r e m a i n d e r in the sequence for H_
when H | > 0,
and when Hj < 0,
the only r e m a i n d e r for
will b e H 0
H2 will b e H 0 .
1967

L e m m a 8:
If
H0 i s a m i n i m u m ,
jH0[ ^ 1 ,
f 303
and n e i t h e r H2 n o r H~2
i s a m i n i m u m , then the only r e m a i n d e r equal in absolute value to a m e m b e r of

the original sequence upon d iv isionby H_ 2 i s H 0 when Hj > 0, and the only
such r e m a i n d e r for H2 i s H 0 when B1 < 0.
Proof:
Avoiding
|H2| = jH^j
and
|H_ 2 | = |H0| as well as
|H.| < jH0|
l e a d s to the f o r m u l a e of L e m m a 7.
L e m m a 9: If H0 i s a m i n i m u m ,
|H 0 | ^ 2,
then t h e r e exist n u m b e r s
H. which l e a v e r e m a i n d e r s which a r e n e i t h e r z e r o n o r equal in absolute value

to a m e m b e r of the original sequence.
Proof: If any n u m b e r H. i s divided by H 0 , the r e m a i n d e r m u s t be l e s s
in absolute value than H 0 , the m i n i m u m of the sequence*
T h u s , if
|H0| ^ 2,
all r e m a i n d e r s cannot be z e r o b e c a u s e any two adjacent t e r m s a r e r e l a t i v e l y

p r i m e , and any n o n - z e r o r e m a i n d e r i s a n u m b e r not equal in absolute value to
a m e m b e r of the original sequence,.
So H0 is a n u m b e r H. for the l e m m a .
Suppose we exclude division by H 0 .

minimum.
Since (H0, H^ = 1,
E i t h e r Hi i s positive o r Hi i s negative.
Hi i s not a
Without l o s s of g e n e r -
ality (see proof of L e m m a 7), we a s s u m e that Hi i s negative. By T h e o r e m 1,

if n 2 i s the l e a s t n a t u r a l n u m b e r such that F n
r,
0 < r < n2,
for q an odd number?

H
Now,
= 0 (mod H 2 ), and if t' = qn 2 +
2-n 2 +t = ^ H g . r
H 2 _ r = H 0 if and only if r = 2.
(mod H2 ) .
If
|H0| > 2,
4,
and at l e a s t 0 L r < 4.
1.
Substituting, we have H 5 = H_i (mod H 2 ) ,
Set t = qn 2 + 3 for an odd n u m b e r q,
inspecting the proof of L e m m a 7.

L e m m a 10; If
|H0| = 1
|H2| > 3 = F 4 ,
SO n 2 A
say q -
and H_i ^ H0 (mod H 2 ) by
T h u s , w e can take i = 2.
is a minimum,
and n e i t h e r H2 n o r H_ 2 i s a
m i n i m u m , then t h e r e exist n u m b e r s H. which leave r e m a i n d e r s which a r e

n e i t h e r z e r o n o r equal in absolute value to a n u m b e r in the original sequence.
Proof: Without l o s s of generality, we a s s u m e that Hi < 0. If
so that n 2 ^ 4,
by L e m m a 8 we c a n u s e the s a m e proof a s for L e m m a 9.
Since H2 i s not a m i n i m u m ,
i s when
|H2| > 3,
H 2 f 1 and H2 f - 1 . The only r e m a i n i n g c a s e
|H2| = 2, which l e a d s only to the following sequence,
" , - 2 3 , 14, - 9 , 5, - 4 , 1, - 3 , - 2 , - 5 , - 7 , - 1 2 , - 1 9 , - 3 1 , - 5 0 , ,
304
'
where 31 = 8 (mod -23) while neither 8 nor 15 is in the original sequence.

Theorem 2: The only sequences which possess the property that, upon
division by a (non-zero) member of that sequence, the members of the sequence
leave least positive or negative residues which are either zero or equal in absolute value to a member of the original sequence are the Fibonacci and Lucas
sequences.
Proof: By Lemmas 9 and 10, for a sequence to possess the above property, its minimum must be either H0 = 0 or |H0| = 1 with one of H2 and
H_2 also a minimum.
If H0 = 0, we can have only the Fibonacci sequence.
Considering the cases
|H0| = 1 and |H2j = 1; |H0| = 1 and |H_2| = 1,
leads to the Lucas sequence and the negative of the Lucas sequence.
It can be shown that, since when Theorem is applied to Lucas numbers,
for each L,k , IL,k |I < |Lm|I or L,k = 0 (mod Lm ), that the Lucas numbers do
indeed have the property of Theorem 2D The Fibonacci numbers a r e known to
also have this property, as proved by Halton in [ 2 ] .
We have used a minimum value greater than 2 as a criterion to determine
if there exist numbers H. which leave remainders which do not satisfy Theorem 2. Another criterion is that such numbers H. exist if and only if |H.I f
i
I J!
JH .1 for any j , where the sequence has been renumbered so that either HQ
is the minimum or HQ is between the two minima H* and H_i. This second
criterion requires a longer proof, but not a difficult one, done by examining all
cases.
Examining several sequences to aid in the formulation of the proofs given
here led to an interesting question. If Brother Alfred T s conjecture is not true
for a whole sequence, can it be true for some elements of the sequence, and if
so, which ones?
REFERENCES
1. Brother U. Alfred,
Exploring Fibonacci Residues, M Fibonacci Quarterly,
Vol. 2, No. 1, F e b . , 1964, p. 42.

2. J. H. Halton, "On Fibonacci Residues, " Fibonacci Quarterly, Vol. 2, No.
3, Oct. , 1964, pp. 217-218.
* * *
ON m-TIC RESIDUES MODULO n

J O H N H.'E. C O H N
London, N . W . , England
1.
INTRODUCTION
T h e object of this p a p e r i s to investigate the v a l u e s of the r e s i d u e s m o d m

ulo n of x , w h e r e 0 ^ x ^ (n - 1), and in p a r t i c u l a r for the c a s e n = m.
We shall define
S(n;m) = { x m (mod n)|
0 ^ x ^ (n - 1)}
and
$(n;m) = {x
(mod n) I 1 ^ x ^ (n - 1), (n,x) = l }
C l e a r l y $(n;m) i s a subset of 2 ( n ; m ) . We shall u s e the symbol $(n;m) to d e note the n u m b e r of distinct e l e m e n t s of $ ( n ; m ) . Also w h e n e v e r t h e r e i s no r i s k
of confusion we shall omit the symbol
(mod n).
We shall p r o v e c e r t a i n t h e o -
r e m s which will enable the w o r k of computing S(n;m) to be r e d u c e d c o n s i d e r ably, and conclude with a table of S(n;n).
2.
T h e o r e m 1.
Proof.
P R O P E R T I E S OF $(n ; m)
H(n;m) = {xy
Suppose z E 2(n;m) a
[ x E $(n;m),
Then z = d
y|n}
m
(mod n). Now let y = (n,d).

m
m
Then d = cy, (n,c) = 1, y n. Hence s = xy , w h e r e x = c E # ( n ; m ) .
This concludes the proof of the t h e o r e m . In view of it, and the fact that for
s e v e r a l r e a s o n s $(n;m) i s r a t h e r e a s i e r to deal with, we shall f i r s t
consider
the p r o p e r t i e s of cj>(n;m)
In the f i r s t p l a c e , we shall define the i n t e g e r
r
n = p ,
(if
if
(ii)
if n = 2 r ,
(iii)
if
l(n) for n > 2,
as follows
r1
where
is an odd p r i m e and
r > 1,
then
l(n) = p
(p - 1)
then l(n) = 2 r ~ 1 if r = 1,2
305
(Received
Jan*51965)
and l(n). = 2 r ~ 2 if r > 3.
306
ON m - T I C RESIDUES MODULO n
N
[ Nov.
r<
n = II P, * ,
i=i
then
l(n) = l . c . m . { l ( P i r i ) } s
t =
1,2,-,N,
Then we have
T h e o r e m 2.
If
k = (m, l(n)),
then if k f l(n),
$(n;m) = $(n;k) ,
w h e r e a s if k = l(n),
then $(n;m) = {1}
Proof.
#(n;l) = {x|(n,x) = 1}
i s a multiplicative Abelian Group whose s t r u c t u r e is known
*(n;l)
C
C
l(Pi
ri
r i
l(Pl )
X C
l(P
C
r 2
r
X ,
l(p2 2) '"
X C
l(Pn
XC
l(pn
r n
ri1
"
C 2 if
^
8|n
Now
l(n) = l . c . m . { l ( p i r i ) }
and so
$(n;l(n)) = {1} ,
and c l e a r l y l(n) i s the l e a s t i n t e g e r for which this i s t r u e .
x
= 1 (mod n)
if
(n, x) = 1 .
Now if
k = l(n) = (m,l(n)),
then
l(n)|m ,
T h u s we have
1967]
x m = 1 (mod n),
and so w h e n e v e r (.n,x) = 1,
i. e. ,
307
$(n;m) = { l } .
Secondly, if (m, (n)) = k w h e r e 0 < k < l(n), then t h e r e exist i n t e g e r s

a, b , c such that
m = ak
and
k = bm - cl(n) .
Hence if (n,x) = 1 we have

m
x
ak
= x
, axk
= (x )
,
, .
(mod n)
and so
$(n;m) C $(n;k)
Also,
k
x
bm-cl(n)
= x
bm ,
, *
= x
(mod n)
= (x^)x m , (mod n)
Thus
$(n;k) C #(n;m) ,
and so by our p r e v i o u s r e s u l t
#(n;k) = <i>(n;m) .
Hence in c o n s i d e r i n g $(n;m) we need only c o n s i d e r v a l u e s of m which a r e
d i v i s o r s of l(n),
38
T h e o r e m 3
P R O P E R T I E S OF S(n;m)
if
x = y (mod n)
and a)n,
then
x
Proof,
= y
(mod an)
Let
x = y + en ,
Then
x
(y + en)
= y
y
a ,
a-i
+ acny
+.,<,+
+ a ( c n ) a _ 1 y + (cn) a
(mod an) s i n c e al n
308
[Nov,
T h i s concludes the proof,, A s i m p l e induction a r g u m e n t now shows that for any

r,
if x = y (mod n) and a|n
then
ar
= yar
(mod arn)
and this gives i m m e d i a t e l y

T h e o r e m 4.
2(a r n; a r m )
= { x a r ( m o d a r n ) | x E 2(n;m)}
w h e r e a is any factor of n.
T h e o r e m 5. If n is s q u a r e - f r e e , and if $(n;m) = <3?(n;l), then
2(n;m)
= 2(n;l)* for by T h e o r e m 1,
S(n;m) = { x y m | x E *(n;m),
y) n}
= { x y m | (nx)
yl n l
Now c o n s i d e r any p r i m e factor p of n
Since n is s q u a r e f r e e
( p m , n) = p
and so t h e r e exist i n t e g e r s a, b such that

p = ap
= ap
Now if
n) 0
+ bn
(mod n) and so (n, a) = 1 o r p
(n, a) = p then let af = a + n / p . Then (n, aT) = 1 and p = a'p
Hence p E 2(n;m),
and so e v e r y p r i m e factor belongs to 2(n;m) 0
(mod
Hence
if m is any n u m b e r between 1 and (n - 1)

N
z = c n p.
i
'
where
s-
(c, n) = 1 and the p^ a r e p r i m e f a c t o r s of n.
T h i s concludes the proof, since c l e a r l y 0 E 2(n;m)

T h e o r e m 6,
If k = (m, l(n)) then if

N
n = n Piri
i=i
Hence z = a
(mod n).
1967]
1(
Piri)
-
(k,l(Pi i))
o rr
l(p.ri)
^
l^
(k,l(v. i))
For,
8 n and m is odd
/Jj
</)(n;m) = \
unless
309
ln
an
is
dd .
(n;m) = </>(n;k) and the r e s u l t follows from the s t r u c t u r e of
since when s n , k
$(n;l),
is odd if and only if m i s odd,

4.
P R O P E R T I E S OF
2(n;n)
T h e o r e m 7. S(n;n) = {0, 1, 2, , (n - 1)} if and only if ( n, l(n)) = 1.

Proof.
(i) If 2(n;n) = {0, 1, 2, , (n - 1)} then $(n;n) = $ ( n ; l )
and
so by T h e o r e m 6 ( n, l(n)) = 1.
(ii) If ( n, l(n) ) = 1 then by T h e o r e m 2 3>(n;n) = $(n;l)
by T h e o r e m 5,
2(n;n) = 2 ( n ; l )
and so
s i n c e n m u s t be s q u a r e - f r e e to m a k e
( n, l(n) ) = 1.
T h e o r e m 8 If l(n)|n, then 2(n;n) = {x |x|n} 6 T h i s follows i m m e d i a t e l y
f r o m T h e o r e m s 1 and 2,
T h e o r e m 9,
(i) if n = 2 r 5
then S(n;n) = { 0 , 1 }
(ii) if n = 3 , then 2(n;n) = { 0 , l , n - 1}

r
mee then 2(n;n)
(iii) if n = p , w h e r e p i s; an odd pprriim
.t
r ,
xlt
c o n s i s t s of the p different e l e m e n t s 0, 1, 2 , , {l(p - 1)}
where
r-i
t = P
Proof,
(i) if n = 2 , then s i n c e 2(2;2) = { 0 , l } ,
by T h e o r e m 4.
(ii) if n = 3 ,
the r e s u l t follows
then s i n c e 2 (3; 3) = { 0 , 1 , 2 } o r equivalently
{ 0 , 1 , - 1 } it follows by T h e o r e m 4 that 2(n;n) = {0, 1, n - l } .

r
(iii) if n = p , then s i n c e l(p) = p - 1, (p, l(p)) = 1 and so by
T h e o r e m 7,
2 (p - 1)}.
2(p;p) = {0, 1, 2, , (p - 1)} o r equivalently,
{0, 1 , 2, ,
Hence by T h e o r e m 4,
S(n;n) = { 0 , l > 2 t , - - - , { | ( p - l ) } t }
t = p27"1
r
It m e r e l y r e m a i n s to show that all t h e s e p e l e m e n t s a r e distinct., Now n = p ,
ri
rl
l(n) = p
(p - 1), k = (n, l(n)) = p
. Hence by T h e o r e m 6, 0(n;n) = p - 1.
310
ON m - T I C
RESIDUES MODULO n
Hence the e l e m e n t s 1, 2 , , ^(p - 1)

a r e all distinct from
[Nov.
a r e all distinct, and c l e a r l y they
This concludes the proof.
T h e o r e m 10. If n = 2p, p an odd p r i m e , then

S(n;n) = { 0 , p , q, q + p| (q|p) = +1}
Proof. l(n) = p - 1,
and so k = (n, l(n)) = 2.
Hence
$(n;n) = <>(n;2) = {x 2 |(z,x) = 1} ,

by T h e o r e m 2.
Hence b y T h e o r e m 1,
2(n;n) - ( a y n | s E *(n;2),
Now y = 0 gives only the e l e m e n t 0,

p gives only the e l e m e n t p.
y = 0,1, 2,p}
and s i n c e
Also,
2 P = 2 (mod 2)
and
2P = 2 (modp)
hence
2 P = 2 (mod n)
hence
2 n = 4 (mod n)
Thus
2(n;n) = { 0 , p , z, 4 z | z E i>(n;2)}
m u s t always be odd,
y =
1967]
311
Now
Z
X2
where
(n,x) = (p,x) = 1
and
4z = (2x)2 = y2
(mod n)
where
(yfn) = (2xs2p) = 2 .
Hence
2(h;h) = {0 9 p/x 2 |(x,p) = 1}
For each element of the form x2 there are now two possibilities,,
(i) 0 < x2 (mod n) < p Then x2 = q where 0 < q < p, (q|p) = +1
(ii) p < x2 (mod n) < 2pe
Then
(x + p)2 = x2 + 2px + p 2
= x2 - p
(mod n)
Hence
x2 = p + q (mod n)
where
0 < q < p and (q|p) = +1
This concludes the proof.
Theorem ll fl
If n = 2p
where p i s an odd prime* then
S(n;n) = {O.p^q^p 1 * + q* | t = p1*"1, 0 < q < p, (q[p) = +l}

Proofp For each p5 we shall prove the result by induction on r0 By the
previous theorem, the result is true for r = 1. Now suppose that it is true
for r = R,
Thus
2(2p ;2p ) = {0,p , q , q + p
Hence by Theorem 4,
} where t = p
312

S(2p
R+1
;2PR+1) =
[Nov.
{XP|xGS(2pR;2pR)}
Now x = 0 gives x^ = 0 and x = p
gives
xP - p p R
= P ^ V 1 1 " 1 1 ' 1 -1)
= p
t .
x = q gives
(mod n)
T
ft>
JP
+ P R+1
xr = q
1.
= q
4-
T3
R+1
where R = pt = p
t ^ R .
x = q + p gives
if
= (q
= q
+ p
, t(p-i) R+l ^ tfp-2)

2R+1
+ q ^ ;p
+ q w 'p
, t R(p-i)+i ^
\
+ . + q p ^ '
+ p P
= q
5 q
(mod p
T , R+l
+p
, A
R+i x
(mod p
)
p
T ^ R+l
x^ = q + p
Also
(
\
,
-.
(mod ox
2)
for if x is even, q is odd and vice-versa,

Hence
p
x^ = q
T ,
+ p
R+i
(mod n) .
This concludes the proof, and gives, for example,

2(2 - 3 r ; 2 - 3 r ) = { 0 , l , 3 r , 3 r + 1}
2(2 5 r ; 2 5 r ) = {0, 1, 5 r - 1, 5 r , 5 r + 1, 2 5 r - 1}
Theorem 12, If n = 4p, where p is an odd prime, then
(i) if p = 3 (mod 4), 2(n;n) - {x2 j x = 0 , l , 2 , , p }
1967]
ON m - T I C
RESIDUES MODULO n
313
(ii) if p = 1 (mod 4),

2(n;n) = {x 2 | x = 0, p 5 q w h e r e 0 < q < p s (qjp) = + l }
Proof.
By T h e o r e m 4S
2(n;n) = {x 2 | x E 2 ( 2 p ; 2 p ) } ,
and so by T h e o r e m 10,
2(n;n) = {x 2 1 x = 0S p 5 q9 q + p
where
0 ^
q ^ p and (qlp) = +1}
(i) if p = 3 (mod 4) then (-1 j p) = - 1 and so q t a k e s exactly half

the v a l u e s
1, 2, , (p - 1) and the o t h e r half a r e of the f o r m p - q0
of
Now
(q + p) 2 - (p - q) 2 = 4pq = 0 (mod n)
Hence in this c a s e
S(n;n) = {x 2 | x =
0sl,25oco5p}
(ii) if p = 1 (mod 4) then (-lip) = +1 and so q t a k e s half the v a l u e s

e
1, 2S , (p - 1),
t h e s e s a m e v a l u e s being of the f o r m
(p - q) and again
(q + p) 2 = (p - q) 2 (mod n)
Hence
2(n;n) = {x2
x = 0spsq,
where 0 ^ q ^ p
and (qjp) = + l }
T h i s concludes the proof,

T h e o r e m 13B If l ( n ) | n and if n = r s w h e r e (r, s) = 1 and if R = r
n
(mod n) and S = s
(mod n) a r e e l e m e n t s of 2(n;n) then R + S = 1 (mod n).
Proof,
Since l(n)|n,
it follows from T h e o r e m 2 that <f>(n;n) = { l } .
314
ON m.-TIC RESIDUES MODULO n
Since n = r s and (r, s) = 1,
[Nov.
(n, r + s) = 1 and so
(r + s ) n = 1
(modn)
Now each of r and s i s a factor of (r + s)
- r
- s
and so s i n c e r and
have no factor in c o m m o n and n = r s ,

(r + s)
= r
+ s
= R + s
(mod n)
(mod n)
Hence by the above r e m a r k ,

R + S = 1
5.
(mod n) .
T A B L E S O F 2(n;n)
Our t h e o r e m s enable u s to compute t a b l e s of 2(n;n)
fairly e a s i l y ,
l e a s t in the c a s e s that n can be f a c t o r i z e d into fairly s m a l l f a c t o r s .
at
By T h e o -
r e m 7, 2(n;n) c o n s i s t s of all the r e s i d u e s when n i s a p r i m e , and so t h e r e i s

no need to c a l c u l a t e the r e s i d u e s in this case 0 Also it i s c l e a r that the e l e m e n t s
0 and 1 always belong to 2(n;n) 0 We give a table; giving 2(n;n) for all v a l u e s
o t h e r than p r i m e s up to n = 100 and a l s o for a few e a s i l y calculable v a l u e s
between 100 and 1000.
n
2(n;n)
contains 0, 1,
no o t h e r s
3,4
_J3
9
no o t h e r s
8
10
4, 5, 6, 9
12
4, 9
14
2, 4, 7, 8, 9, 11
15
all r e s i d u e s
16
no o t h e r s
and
1967
ON m - T I C
RESIDUES MODULO n
18
9,10
20
5, 16
21
6, 7, 8, 13, 14, 15, 20
22
3, 4 5 5, 9, 1 1 , 12, 14, 15, 16, 20
24
9, 16
25
7, 18, 24
26
3, 4, 9, 10, 12, 13, 14, 16, 17, 22, 23, 25
27
26
.28
4, 8, 9, 16, 2 1 , 25
30
4, 6, 9, 10, 15, 16, 19, 2 1 , 24, 25
32
no o t h e r s
33
all r e s i d u e s
315
34
2, 4, 8, 9, 13, 15, 16, 17, 18, 19, 2 1 , 2 5 , 2 6 , 3 0 , 3 2 , 3 3
35
all r e s i d u e s
36
9, 28
38
4, 5, 6, 7, 9 , 1 1 , 1 6 , 1 7 , 1 9 , 20, 23, 24, 25, 26, 28, 30 # 35, 36
39
5, 8 , 1 2 , 1 3 , 1 4 , 1 8 , 2 1 , 25, 26, 27, 3 1 , 34, 38
40
16, 25
42
7, 15, 2 1 , 22, 28, 36
44
4, 5, 9, 12, 16, 25, 33, 36, 37
45
8, 9, 10, 17, 18, 19, 26, 27, 28, 35, 37, 37, 44
46
2, 3, 4, 6, 8, 9 , 1 2 , 1 3 , 1 6 , 1 8 , 23, 24, 25, 26, 27, 29, 3 1 , 32, 35,

36,39,41
48
16, 33
49
18, 19, 30, 3 1 , 48
50
24, 25, 26, 49
51
all r e s i d u e s
52
9, 13, 16, 29, 40, 48
54
27, 28
55
10, 1 1 , 12, 2 1 , 22, 23, 32, 33, 34, 4 3 , 44, 45, 54
|>6
8, 9, 16, 25, 32, 49
57
7, 8 , 1 1 , 1 2 , 1 8 , 1 9 , 20, 26, 27, 30, 3 1 , 37, 38, 39, 45, 46, 49, 50,
56
58
4, 5, 6, 7, 9 , 1 3 , 1 6 , 20, 22, 23, 24, 25, 28, 29, 30, 3 3 , 34, 35, 36,
38, 42, 45, 49, 5 1 , 52, 53, 54, 57
60
16, 2 1 , 25, 36, 40, 45
31b
|" NoVo
62
2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28, 31, 32, 33, 35, 36, 38, 39, 40, 4 1 , 45,
47,49,50,51,56,59
63
8, 27, 28, 35, 36, 55, 62
64
no o t h e r s
65
all r e s i d u e s
66
3, 4, 9, 12, 15, 16, 22, 25, 27, 3 1 , 33, 34, 36, 37, 42, 45, 48, 49, 55, 58, 60, 64
68
4, 13, 16, 17, 2 1 , 33, 52, 64
69
all r e s i d u e s
70
4, 9, 11, 14, 15, 16, 2 1 , 25, 29, 30, 35, 36, 39, 44, 46, 49, 50, 51, 56, 60, 64, 65
72
9, 64
74
3, 4, 7, 9, 10, 11, 12, 16, 2 1 , 25, 26, 27, 28, 30, 33, 34, 36, 37, 38, 40, 4 1 , 44, 46
47, 48, 49, 53, 58, 62, 63, 64, 65, 67, 705 71, 73
75
7, 18, 24, 25, 26, 32, 4 3 , 49, 50, 51, 68, 74
76
4, 5, 9, 16, 17, 20, 24, 25, 28, 36, 44, 45, 49, 57, 6 1 , 64, 68, 73
77
all r e s i d u e s
78
12, 13, 25, 27, 39, 40, 51, 52, 64, 66
80
16, 65
81
80
82
2, 4, 5, 8, 10, 16, 18, 20, 2 1 , 23, 25, 31, 32, 33, 36, 37, 39, 40, 4 1 , 42, 43, 45, 46,
49, 50, 51, 57, 59, 6 1 , 62, 64, 66, 72, 73, 74, 77, 78, 80, 81
84
21,28,36,49,57,64
85
all r e s i d u e s
86
4, 6, 9, 10, 11, 13, 14, 15, 16, 17, 2 1 , 23, 24, 25, 31, 35, 36, 38, 40, 4 1 , 43, 44, 47,
49, 52, 53, 54, 56, 57, 58, 59, 60, 64, 66, 67, 68, 74, 78, 79, 81, 83, 84
87
all r e s i d u e s
88
9, 16, 25, 33, 48, 49, 56, 64, 80, 81
90
9, 10, 19, 36, 45, 46, 54, 55, 64, 81
91
all r e s i d u e s
92
4, 8, 9 , 1 2 , 13, 16, 24, 25, 29, 32, 36, 4 1 , 48, 49, 52, 64, 69, 72, 73, 77, 81, 85
93
2, 4, 8, 15, 16, 23, 27, 29, 30, 31, 32, 33, 35, 39, 46, 47, 54, 58, 60, 6 1 , 62, 63, 64
6 6 , 7 0 , 7 7 , 7 8 , 85, 8 9 , 9 1 , 9 2
94
2, 3, 4, 6, 7, 8, 9 , 1 2 , 1 4 , 1 6 , 1 7 , 1 8 , 2 1 , 24, 25, 27, 28, 32=, 34, 36, 37, 4 2 , 4 8 , 49,

50, 51, 53, 54, 55, 56, 59, 6 1 , 63, 64, 65, 68, 71, 72, 74, 75, 79, 81, 83, 84, 89
95
all r e s i d u e s
96
33, 64
98
32,44,49,67,79,86
1967]
99
317
8, 9, 10, 17, 18, 19, 26, 27, 28, 35, 36, 37, 44, 45, 53, 54, 55, 62, 63, 64, 71,
72, 73, 80, 81, 82, 89, 90, 91, 98
100
25, 76
108
28, 81
120
16, 25, 40, 81, 96, 105
125
57, 68, 124
128
no o t h e r s
136
16, 17, 33, 120
144
64, 81
150
24, 25, 49, 5 1 , 75, 76, 99, 100, 124, 126
160
65, 96
162
81, 82
192
64, 129
200
25, 176
216
8 1 , 136
240
16, 81, 96, 145, 160, 225
243
242
250
124, 125, 126, 249
256
no o t h e r s
272
17, 256
288
64, 225
300
25, 76, 100, 201, 225, 276
320
65, 256
324
8 1 , 244
360
81, 136, 145, 216, 225, 280
384
129, 256
400
176, 225
432
81, 352
480
96, 160, 225, 256, 321, 385
486
243, 244
500
125, 376
318
512
no o t h e r s
544
256, 289
576
64 9 513
600
25, 2 0 1 , 225, 376, 400, 576
625
182, 443, 624
640
256, 385
648
81, 568
720
81, 145, 225, 496, 576, 640
729
728
768
256, 513
800
225, 576
864
352, 513
900
100, 225, 325, 576, 676, 801
960
256, 321, 385 3 576ls 640, 705
972
244, 729
1000
376, 625
Nov. 1967
The author wishes to thank the referee most sincerely for some valuable
suggestions.

The Fibonacci Association invites Educational Institutions to apply for Academic

Membership in the Association. The minimum subscription fee is $25 annually,
(Academic Members will receive two copies of each issue and will have their
names listed in the JournaL )
*****
The Fibonacci Bibliographical Research Center desires that any reader finding
a Fibonacci reference send a card giving the reference and a brief description
of the contents. Please forward all such information to:
Fibonacci Bibliographical Research Center,
Mathematics Department,
San Jose State College,
San Jose, California.
* *
CERTAIN LUCAS-LIKE SEQUENCES.

AND THEIR GENERATION BY PARTITIONS OF NUMBERS
DANIEL C . FIELDER
Georgia Institute of Technology, Atlanta, Georgia
1.
INTRODUCTION
An interesting paper by S0 L0 Basin in the April, 1964, issue of this

th
journal [1] develops the k
Lucas number L, = S, where S, is the sum
th
of the k
powers of the roots of
f(x) = a0x2 + ajx + a2 ,
(1)
in which a0 = 1,
aj = a2 = - 1 . Although Basin ? s S,
originated from a
demonstration of a property of Waring 1 s formula, it is obvious, as Basin

implies, that the same results could be obtained using Newton1 s formulas for
S, in terms of elementary symmetric functions,
In a previous paper [ 2 ] , the author tabulated S, from Newton1 s formulas for
(2)
f(x) = a 0 x n + ajx11
+ - + a
The values of S, for k = 1(1)11 applicable for 1 < n ^ 11 are reproduced

as Table 1* of this paper.
It is proposed to examine the special case of (2),
(3)
*/ v
n
n-i
n-2
f(x) = x - x
-x
- ... - i ,
for n > 2 and to use Table 1 as a guide in extending the true Lucas sequence
found from (1) to Lucas-like sequence s0 Also, a method by which partitions
of numbers can generate terms of the Lucas-like sequences is presented.
*This table is reproduced with all rights reserved, Reprinted by permission

from the American Mathematical Society from Mathematics of Computation,
Vol. 12, No. 63, pp. 194-198* Actually, it is S^ which is tabulated in [ 2]
but is presented herein as S^. to be consistent with this paper.
319
320
CERTAIN LUC AS-LIKE SEQUENCE SAND THEIR GENE RATION
[Nov 0
Table 1
Sk
Si
for k =
1(1)11
di/do,
= ai 2 /ao 2 2at/a$,
= ai 3 /a 0 3 -f 3aifl 2 /ao 2 3a 3 /ao,
0i 4 /0o 4 4ai2<z2/a03 4 (40i0 3 4- 20 2 2 )/0 O 2 4a 4 /a 0 ,
= 0i 5 /0o 6 4 5ai 3 a 2 /ao 4 (5ai 2 a 3 -f 5aiO 2 2 )/a 0 3 4 (50i0 4 + Saâ^)/a^ 5a&/a&,
= ai6/ao 6a 1 4 a 2 /ao 6 +(6ai 3 a 3 H-9ai 2 a 2 2 )/ao 4 (6ai 2 a 4 -f 120^^3-}- 2a 2 3 )/ao 3
-f- (60105 4 60<204 4- 3 0 3 2 ) / 0 Q 2 6a/ao,
57 = - aiVao 7 4 7ai 6 a 2 /a 0 6 - ( 7 a / a 3 4 14ai 3 a 2 2 )/a 0 6
4- (7ai3a4 4 2 1 a i 2 a 2 a 3 4 7 a i a 2 3 ) / a o 4 (7fl 2 ia 5 4l4aia2^447a 2 23 47oia 2 3)/ao 3
4 (7aia 6 4 70*15 4 7a 3 0 4 )/0o 2 7a 7 /ao,
5 8 = 0i 8 /0o 8 8oi 6 a 2 /0o 7 4 (8ai 5 a 3 4 20ai 4 a 2 2 )/a 0 6
(80^04 4 32di30203 4 160i 2 0 3 2 )/0 O 5
4 (8oi 3 a 6 4 24fli2a204 4 12ai 2 0 3 2 4 240i0 2 2 0 3 4 2a 2 4 )/a 0 4
(8ai 2 0 6 4 160105505 4 I6010304 4 802204 4 80 2 0 3 2 )/0o 3
4 (80107 4 80 2 0 6 4 80305 4 40 4 2 )/0o 2 80 8 /0 O ,
S* = - 0i 9 /0o 9 4 90! 7 0 2 /0 O 8 - (90! 6 0 3 4 270i 6 0 2 2 )/0o 7
4 (90i 5 0 4 4 45a ^ 0 ^ 3 4 3O0i 3 0 2 3 )/0 O 6
(90i 4 0 5 4 36ai 3 0 2 04 4 180i 3 0 3 2 4- 540i 2 0 2 2 0 3 4 9ai0 2 4 )/a o 5
4 (90i 3 0 6 4 27fli20206 4 270i20304 4 27ala22ai
4 270i0 2 0 3 2 + 90 2 3 0 3 )/0 O 4
2
2
(90i 0 7 4 180105506 4 18010305 4 90104 4 90 2 2 0 6 4 180550304 4 30 3 3 )/0o 3
4 (9010s 4 90207 4 90 3 0 6 4 90 4 0 B )/0o 2 90 9 /0 O ,
5 l 0 = a ^ / 0 0 1 0 - IQ01W0O 9 4 (lO0i 7 0 3 4 350i 6 0 2 2 )/0o 8
52
53
Si
5s
Si
( 1 O 0 I 6 0 4 4 6O0i 5 0 2 0 3 4 5O0i 4 0 2 3 )/0 O 7 4
5n
(1O0I505 4
5O0i40204
4 250i 4 0 3 2 4 lOO0i302203 4 250i 2 0 2 4 )/0o 6 - (1O0I 4 0 6 4- 4O0i30205

4 4O0i30304 4 6O0i202204 4 6O0i203202 4 4O023030i 4 20 2 6 )/0 O 6
4 (lO0i 3 0 7 4 3O0i20206 4 3O0i20305 4 150i2042 4 3O0i02205
4 60010^304 4 1O02304 4 15022032 4 1O0I0 3 3 )/0O 4
(lO0i 2 0 8 4 2O0i0207 4 20010306 4 20010405 4- 200550305
4 1O02042 4 lOa 2 2 0 6 4 lO03204)/0o3 -4 (10aio 9 4 1O0208
4 100307 4 100406 4 50B2)/0O2 1O0IO/0O,
= - ain/a0u
4 II01W0O 1 0 - ( l l 0 i 8 0 3 4 44a 1 7 0 2 2 )/0 O 9
4 ( l l 0 i 7 0 4 4 770i60203 4 770 1 6 0 2 3 )/0o 8 - ( l l 0 i 6 0 5 4- 6601*0204
4 330i6023 4 1650i 4 0 2 2 0 3 4 550i 3 0 2 4 )/0 O 7 4 ( l l 0 i 5 0 6 4 550i40205
4 550i40304 4 llO0i 2 0 2 3 0 3 4 HO01W04 4- HOoi^j^s 2 4- Il0i0 2 5 )/0o 8
(Il0i 4 0 7 4 44-0i30206 4 440i30306 4 220i 3 0 4 2 4 660i202206
4 1320i 2 0 2 0 3 0 4 4 440i0 2 3 0 4 4 660i0 2 2 0 3 2 4 I I 0 / 0 3 4- 22ai2a/)/a0b
4 ( l l 0 i 3 0 8 4 330i 2 0 2 0 7 4- 330i20308 4 330i20405 4 330i0 2 2 0 6
4 66010J50305 4- 330102042 4 330i03204 4 ll0 2 3 06 4 330220304 4 ll0a 8 02)/0o 4
(Il0i 2 0 9 4 22010*08 4- 22010307 4 220i0 4 0 6 4 11010s2 4- ll02 2 07
4 220 2 0 3 0 6 4 22020405 4 ll0 3 #4 2 4 ll0 3 2 05)/0o 3 4 (II0101O 4 H0209
4
ll0308 4
H 0 4 0 7 -4 110606)/0Q 2 ~ 1 l01l/0O.
1967]
BY PARTITIONING OF NUMBERS
321
f!
The liberty of calling the sequence Lucas-like" appears justified since

(1) (as used by Basin) is a special case of (3) and, moreover, the sequences
do indeed share characteristics with the true Lucas sequences
20 OBSERVED BEHAVIOR
To identify terms of a sequence and at the same time to retain a Lucas
flavor, the terminology L | ' is used to specify the k
term of a Lucas(n)
For convenience, S^ ; =
like sequence obtained from (3) for a given n > 20

(2)
th
v
L^(n)
It is noted that L;_ is the true k"Ai Lucas number, L, . For any
"k 0 ^ ^ *
^k
given k < 11 and 2 < n < 11, it is a simple matter to enter Table 1, reject
all coefficients of a terms having subscripts greater than n and add the
th
numerical coefficients of the remaining a terms to obtain a k
Lucas-like
number a
The choice of signs in (3) automatically makes the signs of the num-
erical coefficients positive,,

(2)
(4)
For examples
1 + 4 + (0 + 2) + 0 = 7
The first seven terms of several Lucas-like sequences obtained in this manner
are recorded in Table 2e For later use, a zig-zag line divides the table into
two parts.
For n = 2,
it is seen that the difference between the first two

n-i
terms (those above the zig-zag line) is 2 (i. ea , 2
for n = 2), and that the
sum of two consecutive terms determines the next term. For n = 3, the difn~2
ference between the two first terms Is 2 , and the difference between the
n-l
second and third terms Is 2 . There are three terms above the zig-zag
line0
For n = 3, the sum of three consecutive terms determines the next
term.
Table 2
VALUES OF L(n)
N n
1
2
3
4
5
6
7
1
1
1
1
1
1
1
1
3
4
7
11
18
29
1
3
7
11
21
39
71
4
1
3
7
15
26
51
99
1
1
3
3
7
7
15
15
31
31
57
63
113 ,120|
322
CERTAIN LUCAS-LIKE SEQUENCE SAND THEIR GENERATION [Nov
The obvious pattern is repeated for n = 4, 5, etc.

One immediate conclusion is that each Lucas-like sequence i s , in reality,
the blend of two sequences,,
The first sequence is 1,3,7, , 2 - 1 having
n terms and governed within its range by the recursion formula

(5)
ift
= Lf
2k,
(L<n> = 1) .
The second sequence starts with the sum of the n terms of the first sequence.
The first term is
(6)
\ /
L<?
= 2n+1 - n
- 2 .
n+1
Succeeding terms are
(7)
- e\+^
i&
(8)
L<
=
T
(4
LW>
--
2) - 1 ,
( 2 n + 1 - n - 2) - (1
(n)
3) ,
+ T (n)
n+i
+ ...
In general, the second sequence follows the recursion formula

l i n ) = li n > + L ? > + . . + L[ n )
(10)
v
'
k-i
k-2
k-n
(k > n + 1)
'
It is interesting to note from (7), (8), and (9) that at least one term of the
first sequence appears directly in the summation for L ) ' for n ^ k ^ 2n
After k > 2n, the influence of the first sequence is reduced.
3.
PARTITION CALCULATION OF SEQUENCE TERMS

fn)
Several methods are available for finding a particular L) ; . One method
is the direct use of recursion formulas.
Another is to solve the n
order
difference equation for the second sequence subject to the n conditions (or
their equivalents) imposed by the first sequence. A. third method, discussed
herein, is to assume that desired partitions of n are available and to use them
as a combinatorial means of finding the L ) .
1967]
f
In Chrystal s [3] notation,
323
P ( k p p q ) is the number of p-part parti-
tions of k, no member of which exceeds qe If the original value of q exceeds k + 1 - p,
it can be replaced by q = k + 1 - p since there are the
same number of partitions for q = k + 1 - p as for q ^ k + 1 - p However,

for
q < k + 1 - p it is obvious that less than P(k|p|<k + 1 - p)
exist.
partitions
Suppose, now, that desired partitions can be called up at will and are
available from this point on. The actual set of such partitions which have the
same limitations as the enumeration counterpart is given the terminology
PV(k|p|<q).
If any S, of Table 1 is stripped of all terms except subscripts and superscripts (exponents) of the numerator
a ? s,
representation of all the partitions of ka
there remains the conventional

The partition representation for
k = 6 is exemplified in Table 3. It is seen that, in general, p ranges from

k to 1. The quantity k (p - 1)! divided by the product of the factorials of
the exponents of a particular combination yields (neglecting sign) the numerical
part of the contribution of that combination to S, . To illustrate, if k = 6,
p = 3, the numerical coefficient associated with the partition 23 = 2,2, 2, is
(6 x 2! )/3l
= 2, This well-known result employs much the same reasoning as
finding a coefficient of a multinomial expansion.

for k = 6, n = 6,
and the total 63 = iA '
The numerical coefficients

are given in Table 3.
once the exponents are found from the available partitions,
Thus,
iA ' follows.
Table 3
Partition
Representation
Numerical
Coefficient
I6
1,1,1,1,1,1
PV(k|p|<q)
(6 x 5! ) / 6 !
= 1
1,1,1,1,2
PV(6|5|<2)
(6 x 41 ) / 4 !
= 6
I , 2
'
PV(k[p|<q)
1 ,2 "
2
14
1,1,2,2
1,2,3
1,2,3
2,2,2
1,5
1,5
24
2,4
3
6
PV(6|4j<3)
1,1,4
23
(6 x 3! ) / 3 ! = 6
1,1,1,3
I ,3
3,3
6
PV(6|3J<4)
PV(6|2|<5)
(6 x 3 ! ) / ( 2 ! x 2!)' = 9
(6 x 2! )/2.T
= 6
(6 x 2! ) / l
= 12
(6 x 2] ) / 3 j
= 2
(6 x l j ) / l
= 6
(6 x l ! ) / l
= 6
f
PV(6ll|<6)
(6 x 1! )/2. = 3
(6 x O ! ) / l
= 6
Total = 63
324
CERTAIN LUCAS-LIKE SEQUENCES AND THEIR GENERATE ON

As long as k ^ n, the sum of numerical coefficients obtained from the
PV(k p ^ k + 1 - p) ! s is the desired
iS '.
When k > n,
the a terms with
subscripts greater than n are zero. Since the corresponding products with
numerical coefficients are zero, these numerical coefficients are not used.
The elimination of these numerical coefficients is accomplished by limiting q
to 1 < q < n and using only those partitions which result.
Table 4 gives an
example of this situation k = 6, n = 20

Table 4
PV(k|p|q)
Numerical
Coefficient
1,1,1,1,1,1
PV(6|6|1)
1,1,1,1,2
1,1,2,2
PV(6|5|2)
PV(6|4|2)
9
2
None
PV(6|3|2)
PV(6|2|2)
None
PV(6|1|2)
Partition
Representation
l6
4
1 ,2
2
1 ,2
2
2,2,2
Total = 1 8
The above methods have been successfully applied to digital computation of
electrical network problems [4] in which the a coefficients had values other
than 1 and in which it was necessary to consider the signs of the resultant
numerical coefficients,
REFERENCES
1. S. L. Basin,
A Note on Waring's Formula for Sums of Like Powers of
Roots,' The Fibonacci Quarterly, Vol. 2, No. 2, April, 1964, pp. 119-122.
2. D. C. Fielder,
A Note on Summation Formulas of Powers of Roots, n
MTAC (now Mathematics of Computation), Vol. XII, No. 63, July, 1958,
pp. 194-19 80
3. G. Chrystal, Textbook of Algebra, Vol. 2, Chelsea Publishing Co. , New
York, 1952, p. 558.
40 D. C. Fielder, T'A Combinato rial-Digital Computation of a Network P a r a m eter, " IRE Transactions on Circuit Theory, Vol. CT-9, No. 3, Sept , 1961,
PP- 202-209.
*****
REMARKS ON TWO RELATED SEQUENCES OF NUMBERS

DANIEL C 0 FIELDER
Georgia Institute of Technology, Atlanta, Georgia
1.
INTRODUCTION
The expansion of (x + y)
(1)
(x + y)
usually takes the form

n+i
=, L C(n,k)x
k=i
where C(n,k) are the well-known binomial coefficients and are sequences of
integers generated by the expansion (1). Another device for obtaining the C(n,k)
is, of course, Pascal ? s triangle.
Different sequences of numbers can be obtained from the coefficients
resulting from the expansion of (x + y) in terms of (x + y )(xy)
. Furn
n
ther, a sort of inverse can be obtained by expressing (x + y ) in terms of
(x + y) (xy)
. In both cases the coefficients share characteristics with c e r -
tain binomial coefficients and terms from sums of powers of roots of selected
polynomials.
In the inverse sequences, except for appropriate changes in
sign, the numerical coefficients are those observed in a recently proposed

approach to the generation of Lucas numbers from partitions of numbers [ l ] ,
The relationship between partitions of numbers and both sequence is outlined
briefly.
2.
SEQUENCE OF THE FIRST KIND
For brevity, let (x + y) = u = ut (interchangeably), let (x + y ) = u, ,

and let (xy) = v. The numerical coefficients of the resultant direct expansion
shown below are called coefficients of the first kind.
u ul
u2 = u 2 + 2v2
u3 =
^
2
3 + 3UiV
u 4 = u 4 + 4u 2 v 2 + 6v 4
u 5 + 5u 3 v 2 + lOu-tV4
u 6 + 6u 4 v 2 + 15u 2 v 4 + 20 v 6
325
326
[Nov,
As might be suspected, the coefficients are binomial coefficients without the

symmetrically repeated coefficients of the expansion (1).
The coefficients of
(2) form the half-Pascal triangle enclosed by solid lines below0
3.
SEQUENCE OF THE SECOND KIND
A rearrangement of (2) yields

Uj_ =
u2 - u2 - 2v2
u3 = u 3 - 3uv2
(3)
u4 - u4 - 4u2v2 + 2v4
u5 - u 5 - 5 u V + Suv4
u6 - u6 - 6u4v2 + 9 u V - 2v
If the minus signs are temporarily neglected in (3), the diagram below illustrates one of the simple additive methods by which the coefficients can be
obtained.
1 +
(4)
If signs are neglected, it is interesting to note that the sum of the coefficients
for any given index is identically the Lucas number of that index.
comments on this will be made later.
Additional
1967] REMARKS ON TWO RELATED SEQUENCES OF NUMBERS

4e
327
INTERRELATIONS
In [ 1 ] , the sums of the powers of roots of

-P/
f (x) = x
n - 1
/C\
(5)
-x
"
-x
_ ...
_ i
were obtained from a previously developed tabulation of Newton1 s formulas for

powers of roots. The first few entries of that tabulation are given below without literal coefficients and without negative signs,
S = 1,
Si = 1 + 2,
S 3 = 1 + 3 + 3,
(6)
S4 -
1 + 4 + (4 + 2) + 4,
5 5 = 1 + 5 + (5 + 5) + (5 + 5) + 5,
56 -
1 + 6 + (6 + 9) + (6 + 12 + 2) (6 + 6 + 3) + 6,
57 = 1 + 7 + (7 + 14) + (7 + 21 + 7) + (7 + 14 + 7 + 7) + (7 + 7 + 7)+7,
Except for a missing final 1, the numbers as grouped in (6) are complete
sets of binomial coefficients; hence, by selecting the appropriate numbers from
(6), the coefficients for the first kind of sequence are readily obtained.
The extraction of the coefficients for the sequence of the second kind is
more interesting.
The same sets of numbers as those for the first kind of co-
efficients are considered. If in (6) a number is not parenthesized, it is one of

the second kind coefficients as well as one of the first kind coefficients. However, it can be observed that whereas a first kind coefficient is equal to the sum
of numbers within parentheses, the corresponding second kind coefficient is
equal to the last number only of the numbers included within parentheses.
Without repeating the details covered in [ 1 ] , it can be stated that the
second kind coefficients be used to obtain the powers of roots of (5) for the case
n = 2. ' Proper choice of sign leads to the ultimate identification.
In the previous paper [ 1 ] , it was shown that the k
Lucas number can
be generated from the two-part partitions of k The sum of the terms resultth
ing from operations on the partitions is equal to the k
Lucas number. The
same operation on partitions can be used for finding the second kind coefficients.
328
However, here the individual terms, not the sum, are used.
Proper choice
of sign must be made since the partition method generates only positive numbers. It may be added that this latter method is of advantage only if a rapid
and convenient means for obtaining partitions is available.
REFERENCES
1. D. C. Fielder, "Certain Lucas-Like Sequences and their Generation by
Partitions of Numbers/' Fibonacci Quarterly, Vol. 5 , No. 4 , pp. 319-324,
* * * *
RECURRING SEQUENCES
Review of Book by Dov Jarden
By Brother Alfred Brousseau
For some time the volume, Recurring Sequences, by DovJardenhas been
unavailable, but now a printing has been made of a revised version.
The new
book contains articles published by the author on Fibonacci numbers and r e lated matters in Riveon Lematematika and other publications,
A number of
these articles were originally in Hebrew and hence unavailable to the general
reading public. This volume now enables the reader to become acquainted with
this extensive material (some thirty articles) in convenient form,
In addition, there is a list of Fibonacci and Lucas numbers as well as
their known factorizations up to the 385th number in each case. Many new r e sults in this section are the work of John Brillhart of the University of San
Francisco and the University of California,
There is likewise, a Fibonacci bibliography which has been extended to
include articles to the year 1962,
This valuable reference for Fibonacci fanciers is now available through
the Fibonacci Association for the price of $6,00, All requests for the volume
should be sent to Brother Alfred Brousseau,
College, Calif. ,94575.
Managing Editor, St. Mary ! s
^^^^^
The Fibonacci Association invites Educational Institutions to apply for Academic

Membership in the Association. The minimum subscription fee is $25 annually.
(Academic Members will receive two copies of each issue and will have their
names listed in the Journal,)
BASES FOR INFINITE INTERVALS OF INTEGERS

D. E. D A Y K I N and A . J . W. HILTON
University of Malaya, Kuala Lumpur, Malaya
and The U n i v e r s i t y , R e a d i n g
1. INTRODUCTION
In this paper we discuss the problem of representing uniquely each member of an arbitrary infinite interval of integers.
The integers of the interval*
and no others, are to be expressed as sums of terms of a sequence (b ) of

integers.
We also discuss the problem of representing uniquely each positive
integer, and no other integer, as the linear combination of terms of a sequence

(b ) of integers, where the coefficients in the linear combination are prescribed
and have the value +1 or - 1 . In each problem, roughly speaking, we choose
an integer k 1 and require that any two terms of (b ) whose suffixes differ by less than k shall not both be used in the representation of any given
integer.
The precise definitions and results are in the next section, where we
also show the way in which earlier work [l] by one of us (D. E..D.) is related
to our definition of an (h,k) base.
In a later paper we will discuss an analogous problem of representing
uniquely each real number in the interval ( 0 , c ] , where c is any positive
real number.
Finally, we would like to thank Professor R0 Rado for his help-
ful suggestions in the preparation of this paper*

2.
STATEMENT OF RESULTS
Throughout this paper, h, k and m are integers such that

h+l > k > h ^ 0 ,
k ^ l a n d m ^ l .
Also, unless we state otherwise for a particular sequence, the subscript of the
first term of a finite or infinite sequence is the number 1, e. g. ,
(a n ) = (aâg,---)
We denote by (v ) the (h,k)
th
Fibonacci sequence defined by

329
330

v
(2.1)
n
n
for
= n
= v
n-i
+ v
[Nov.
1 ^ n ^ k,
, + N(k -- h) for n > k .

n-k
An equivalent definition of this sequence was given (for h > 1) in [1] (p. 144).
We denote by (u ) the (k,k)
Fibonacci sequence and by (f ) the
(2.2)
Fibonacci sequence, which is clearly the original Fibonacci sequence (1, 2, 3,

5, 8,13, 21, e ). Further, we write [a,b] for the interval of integers x,
< x < b, with the obvious interpretation when a = ~ or b = +.

Suppose (a ), (k ) is a pair of sequences of positive integers with the
following property P.
P.
Each integer N E [1,] has a unique representation

N = a.
where a = a(N) and i , - i

x
'
v+i
+ a.
^ k
+ . . . + a.
for 1 ^ v < a.
It is shown in [1] (Theorem D) that if (a ) is increasing and the pair

(a ), (k ) have the property P then kj ^ k2 kj + 1, k2 = k for v ^ 2,
n
n
V
th
~
and (a ) is the (k l9 k 2 )
Fibonacci sequence. This result leads us to make
the following definition.
Definition 1. A finite or infinite sequence (b ) of integers is an (h,k)
base for an interval [ a , b ]
if each integer
N {0} U [a,b]
has a unique
representation
(2.2)
N = b. + b. + + b.
where
a = a(N), i 2 ^ it + h if a > l,
and iy
^ i y + k for 1 <v < a
and further, if N is an integer which can be expressed in the form (2.2) then
N E {0} U [ a , b ] .
Notice that the representation of 0 in the form (2.2) is the empty sum.
Theorem 1 is a statement in this notation of another result proved for
h > 1 in the earlier paper ([1 ], Theorem C). This result can easily be shown
to be true for h = 0 also,
Theorem 1. The first
n terms
(v1? v2, , v ) of the (h,k)
Fib-
onacci sequence (v ) form an (h,k) base for [ l , v . - 1], and (v ) forms

an (h,k) base for [ 1, "|.
1967]
331
Our first new results, Theorems 2-6, are concerned with the existence
of (h, k) bases for the infinite interval
[m, 00] with m ^ 1, and for the infin-
00
ite intervals [m5oo] and [- ,00]. We conjecture that there is no (h,k) base
for [ m, 00 ] when m ^ 3, but have only been able to prove the following theorem,
Theorem 2. If m > 1 and (b ) is an increasing sequence of integers,
b
^ (2,3,4, , 2
ever,
,)>
(b ) = (2, 3,4, , 2
tnen
(b ) is not an (h,k). base for [m,oo]# How-
s#
, ) is an (h,k) base for [m,o] if and only
if h = k = 1, and m = 28 By the statement that (b ) is an increasing s e quence, we mean that bA ^ b 2 .

It is easier to deal with the intervals
[-m, <*>] and [-o,o], provided that
h = k. However, we have been unable to settle the question of the existence of

(h,k) bases for these intervals when h ^ k.
Theorem 30 If -m is a negative integer then there exists a (k,k) base
for [-m,o].
For the set of all integers,
[-00,00], there are infinitely many (k,k)
bases, and in fact we can choose the sign which each term of a (k,k) base is
to have, subject to the condition that the signs change infinitely often0
Theorem 4 Let (s ) be a sequence such that
E {-1,1} for n ^ 1 ,
n
and
s _ = -1 for infinitely many n > 1 .
Then there is a (k,k) base
(b ) for
[ -00,00 ] with s b
>0
for n ^ 1.
For k = 2, we give an explicit example of a (k,k) base for [ -m,oo ] in

terms of the Fibonacci sequence (f ). We first represent m in the form
(2.4)
1
m = f.
11
+ f.
+ + f.
i2
ia
where
i v+1
^ > i v + 2 for 1 ^ v
The existence and uniqueness of this representation is proved by Theorem 1.
let (s ) be the sequence defined in terms of the suffixes i of (2.4)
Next we le
as follows
332

s.
(2.5)
= - 1 for
1 < v <
[Nov.
vî
s
= 1 otherwise.
Then an explicit f o r m u l a for a (2,2) b a s e for
[-m,*>]
is given i n : t h e follow-
ing theorem*
T h e o r e m 5, Let - m
be a negative i n t e g e r , let the sequence (s ) b e d e -
fined as in (2.5), and let

sf
i f s ' s
1)
Then
n n
n 1
,
.- n
~
, for
S f , if S S J = - 1
n n-i
n
n-i
(b ) i s a (2,2) b a s e for [ -m,oo]
S i m i l a r l y , we have an explicit f o r m u l a for a

t e r m s of the F i b o n a c c i sequence
(f ).
n > l
(2,2) b a s e for [-oojooj, in
We p r e s c r i b e the sign of each t e r m of
the b a s e , subject to the condition that the signs change infinitely often.
T h e o r e m 6.
If the sequence
(s ) s a t i s f i e s (2.3) and the sequence (b )
is d e t e r m i n e d in t e r m s of (s ) by the r e l a t i o n s
b a s e for
r-<xy]
L
J with s b
n
(2*6),
then
(b ) i s a (2,2)
> 0 for n > 1,
So far we have been c o n c e r n e d with unique r e p r e s e n t a t i o n s of i n t e g e r s a s

s u m s of t e r m s of a b a s e .
It is i n t e r e s t i n g to c o n s i d e r the p r o b l e m of uniquely
r e p r e s e n t i n g i n t e g e r s as l i n e a r combinations of t e r m s of a sequence
(b ) of
i n t e g e r s , w h e r e the coefficients in the l i n e a r combination a r e p r e s c r i b e d and

have the value +1 o r - 1 . We f i r s t m a k e the following definition.
Definition 2.
be given.
Let a sequence S = (s ), w h e r e s
A sequence
(b ) of i n t e g e r s is an ( h + l , k ; S )
each i n t e g e r N G [ 0,oo] h a s a unique r e p r e s e n t a t i o n

(2.7)
N = s b . + s ,b. + + Sib.
l
a it
a-l i 2
ia
where
a = a(N),
and
E { - l l } for n ^ 1,
i 2 - ii + h + 1 if a
i y + 1 ^ i y + k for 2 ^ v <
> 1,
a
b a s e for [0,o]
if
1967]
333
and further, if N is an integer which can be expressed in the form (2.7) then
NE- [0,oo] .
th
Theorem 1 shows that the (h,k)
Fibonacci sequence (v ) is an (h,k)
base for [l,o].
It follows that (v ) is an (h,k) base for the set of all non-
negative integers, [0,oo], and we have been able to determine the conditions
under which (v ) is an (h + 1, k;S) base for this same set of integers.
Theorem 7. The (h,k)
for [0,oo] if and only if s
Fibonacci sequence (v ) is an (h + l,k;S) base

n+l
= (-1)
for n 1.
In our last theorem we give an explicit formula for the terms of (v ), the
n
th
(h,k)
Fibonacci sequence. It is well known that the terms of the Fibonacci
sequence (f ) are sums of the elements in the diagonals of Pascal's triangle,
and Theorem 8 extends this result.
Theorem 8.
(2.8)
E
/n-h+<k-l><2-i>)
i=k-h V
i
/
for
* i .
Here, as usual, (, J denotes the binomial coefficient a! /(a - b)! (b!).

3.
PROOF OF THEOREM 2
We assume that the sequence (b ) is increasing and is an^(h,k)
base
for [m,oo], and in each of the first three cases we deduce a contradiction of
definition! of an (h,k) base by finding a number which has two representations
in the form (2.2).
Lemma 1. b = n + m - 1 for 1 n m + h.
n
Proof. As the sequence (b ) is increasing, it is strictly increasing, so
that bi = m and
(3.1)
x
b ^ m + n - 1 for n ^ 1 .
n
The smallest number of the form (2.2) with a

bj_ + bi+h 2m + h. Hence b
<
>
1 is b* + bj+k, and, by (3.1),
= m + n - 1 for all n 1 such that m + n - 1
2m + h; i. e. , n m + h. This proves Lemma 1.

We consider now the various cases.
334

Case [1].
m ^ 3.
k>i
[Nov*
Then by L e m m a 1,
bh+s = m + (m + h + 3 - 1) = (m + 1)
+ (m + h + 2 - 1) = b 2 + bh+2
C a s e [ 2 ] . 1x1 = 29 k > 1. By L e m m a 1,
and so bi + bi+ n = 4 + h,
ht + b 2 +h = 5 + h,
= n + 1 for
1 < n < h + 2,
and b 2 + b2+h = 6 + h.
Clearly,
6 + h i s the l a r g e s t n u m b e r which can be r e p r e s e n t e d in the f o r m (2.2) with

i
2 + h and a = 2.
However,
the s m a l l e s t n u m b e r which can b e r e p r e -
sented with a = 3 i s
bl + b-t+h + b 1 + h+k Therefore
b 3 +h = 7 + h.
4 + h + b3+fr > 4
But ht + b 3 +h = 2 + (7 + h) = 9 + h,
h a s no r e p r e s e n t a t i o n with i^ ^ 3 + h.
b
+ b
Case [ 3].
= 3.
+ h + 6 + h > 1 0
h .
so that 8 + h
Hence b 4 +| 1 = 8 + h. But then we have
4+h = 2 + (8 + h) = 3 + (7 + h) = b 2 + b3+h .
m = 2,
k = 1,
h = 0.
Then by L e m m a 1,
bi = 2 and b 2
T h e r e f o r e the r e p r e s e n t a t i o n s of 4, 5, 6 and 7 a r e bi + b l 3 bi + b 2 ,
+ b 2 and bj + bi + b 2 r e s p e c t i v e l y .
b2
The n u m b e r 8 cannot be r e p r e s e n t e d in the
f o r m (2.2)-with ifl, ^ 2. Hence b 3 = 8. S i m i l a r l y the n u m b e r 9 cannot be r e p r e s e n t e d with i^ ^ 3.
Hence b 4 = 9.
But then ht + b 4 = 2 + 9 = 3 + 8 = b 2
+ b3.
We have now only to deal with the c a s e s when m = 2,
k = 1,
h = 1.
It follows, t h e r e f o r e , from the c o n t r a d i c t i o n s obtained in the f i r s t 3 c a s e s that

if (b n ) is an (h,k) b a s e for
Case [ 4 ] .
In this c a s e
h = k = 1,
[m,oo]5
then h = k = 1 and m = 2.
ni
b 2 = 3 and b n = 2
for n > 3.
m = fy = 2,
(b n ) i s a (1,1) b a s e for [2,00].
F o r let N 2 b e an i n t e g e r .
If N is even, then i t s r e p r e s e n t a t i o n in
the f o r m (2.2) is the binary r e p r e s e n t a t i o n , which i s unique. If N is odd, then

N - 3 i s even, and so the r e p r e s e n t a t i o n of N i s the b i n a r y r e p r e s e n t a t i o n of
N - 3 together with b 2 ; hence this r e p r e s e n t a t i o n i s also unique,,
1967]
335
P_1
Notice that, for p ^ 3, each of the n u m b e r s 2, 3, , 2

- 2,
2P_1
p-1
2 F + 1, and no o t h e r s , can be r e p r e s e n t e d in the form (2.2) using (bj,
-1,
b 2 , # , b _ ).
T h i s fact i s used in the proof of the next c a s e .
C a s e \5].
h = k = 1,
m = 2,
(2, 3, 4, 8, - , 2n~\
(b n f
).
we a s s u m e that (b n ) i s i n c r e a s i n g and i s an (h,k) b a s e for [m,oo],

by L e m m a 1,
P
bp f 2 ~ ,
bj = 2 and b 2 = 3.
Let p > 3 be an integer.
Again
so that,
Suppose that
also suppose that b 3 = 4, b 4 = 8, / b p _ 1 = 2 P ~ 2 .
and, if p > 3,
Then, by the r e m a r k at the end of the l a s t c a s e ,
bp > 2
+ 1. But then 2
h a s no r e p r e s e n t a t i o n in the f o r m (2.2), which c o n t r a d i c t s definition 1 of an

(h,k) b a s e .
T h i s c o m p l e t e s the proof of T h e o r e m 2.
4.
PROOFS OF THEOREMS 3, 4, 5 and 6
Throughout this section, n a m e l y L e m m a s 2-8 and the p r o o f s of T h e o r e m s 3-6, the s e q u e n c e s
( t n ) , ( a n ) , (d n ) and ( e n ) a r e as defined i m m e d i a t e l y
below. We let ( t n ) be a sequence such that t

sequences
(an),
(d n )
and ( e n )
E { - 1 , l } for n > 1. T h e t h r e e
a r e s i m u l t a n e o u s l y defined by induction
in
t e r m s of the sequence (t^). F i r s t we put a* = tj and d n = e n = 0 for n < 0

If n > 1 and we have defined the t e r m s
a
1 < v < n - 1,
for
v < n - 2, and the t e r m s
, e _ and a a s follows.
n-i
n-i
n
i); d
i s the l a r g&e s t , and e , i s the s m a l l e s t of the n u m b e r 0 and
n-l
n-i
the n u m b e r s r e p r e s e n t a b l e in the form
v
for
d , e
then we define d
(4.1)
a.
11
+ a.
19
+ + a.
Xl
a
where
i <
a
1 A ON
(4.2)
n - 1
an
and
i ,, . > i + k
v+i
v
for
d
- e
. +1
= < n-i
n-k
lNe
- d . - 1
n-i
n-k
if
1 <v < a
t =+1
n
t = -1
n
if
T h e r e l a t i o n (4.2) i s c l e a r l y t r u e for n = 1 also.

_L e m m a 2.___ (i) F o r all n, 0 < dn_i J < dn
(ii)
F o r n > 1,? t a > 0*
v
n n
and en < en _ 1J < 0o
336

Proof,
[Nov.
(i) Follows immediately from the definitions of (d^) and (e n ).

(ii) For n ^ 1, if t^ = +1, then, by (4.2) and part (i),
a
n
The proof when t

Lemma 3
= d
- e , + 1 ^ 1 .
n-i
n-k
= -1 is similar and completes the proof of Lemma 2.
= +1, then d = d , + a and e =

n
n-k
n
n
e , and if t = - 1 , then e = e , + a and d = d
n-r
n
n
n-k
n
n
n-l
Proof, (i) We assume that t = +1 and show that e = e . Since
For n ^ 1,
if t
n-i
= +1, by Lemma 2(ii), a > 0. The number e J i s , by definition, the

x /J
n
' J
n
n-l
' J
'
smallest of the number 0 and the numbers representable in the form (4.1),
and since a > 0, no smaller number can be formed by
Hence
J adding
& a .
n
n
e = e . Similar reasoning
= d
if t = - 1 .
& shows that d
n
n-i
n
n-l
n
= +1 and show that d = d , + a .
x(ii) We assume that t
'
n
n
n-k
n
From the definition of (cL), d ^ d . + a We suppose that d > d . +
v
n"
n
n-k
n
^
n
n-k
a , so that d = d
, +a
for some r > 0. Hence d
. + a
>
n
n
n-r-k
n-r
n-r-k
n-r
d , + a . However by Lemma 2(i), d
< d , , so that a
a .
J
v
n-k
n
"
n-r-k
n-k'
n-r
n>
Since t = +1 it follows from Lemma 2(ii)
that a > 0. Therefore a
v
n
'
n
n-r
0 and so t _ = +1. Therefore, by (4.2),
(4.3)
v
d
-a
, + l ^ d - e j + l .
n-r-i
n-r-k
n-i
n-k
However, by Lemma 2(i), d

^ d
and -e , -e
, , which con
3 J
WJ
n-l
n-r-i
n-k
n-r-k
tradicts (4.3) and so proves that d = d , + a . The proof that if t = -1
v
'
*
n
n-k
n
^
n
then e = e , + a is similar. This completes the proof of Lemma 3.
n
n-k
n
^
^
Lemma 4. For all n, the finite sequence (a ls a2, , a n ) is a (k,k)
base for Lfe , d 1.
n nJ
Proof. We use induction upon n. When n < 1, (alf a2, , a n ) = <p9
the emptyJ set. Since e = d = 0 , the lemma is true in this case.
*
n
n
Let m ^ 1, and suppose the lemma is true for n < m. Then
(al9 a2,
' , am - k, ; ) is a v (k,k)
' ' base for Lfem-k,s , dm-k,J 1. From \ (4.2)
/ and Lemma 2(i),
\ /
if t = +l then a + e , > d , , and if t
= -1 then a + d , <
m
m
m-k
m-k
m
m
m-k
e , . Therefore v(a*,
, , a ) is a (k,k) base for
1$ SL
l9 9, , a
m-k
m-k m 7 o v ' }
fe
L
, , d , 1 M fe , + a , d , + a J] .
m-k m-k J ^ L m-k
m m-k
m
1967]

Also by the induction hypothesis,
m - lJJthen e
( 4 2/sh i f
- 1 = a
m-i
m
+d
= +1
,0
m-k
Te
L
then
(ala a2, , a
337
) is abase for [e
_,
, , s and if t m = -1
m-i+ 1 = a m+ e m-k
Since also, from Lemma 2(i),
WJ
'
D L[e m-k*
, f d m-k, 1J
m - r. d m - i J1
it follows that (a
, , am/
is a v(k.k)
m)
\ 1si>a 2t>
/ base for LTem - k, ', d m-k, + a m J1 if tm
= + 1 , or for fe , + a , d
] if t = - 1 . Hence, by Lemma 3, (a*, a*.
L
9
x v
i9
m-k
ms m - i J
m
* J
BO
J
s a m 7) is a (k.k)
\ / base for Lfe m , d m 1.
Lemma 4 now follows by induction*
Proof of Theorem 4. Suppose t
rf
= s
for n ^ 1,
where
(s ) is the
\
sequence defined in (2.3). Then (t ) has the additional property that t t

= -1 for infinitely many n ^ 1. It is then clear from Lemmas 2(ii) and 3 that
d ~*-oo and e
-* -oo as n -* , so that, by Lemma 4 (a ) is a (k,k) base
for [-00,00], We have already shown (Lemma 2(ii)) that a t
>
0 for n ^ 1,
so that Theorem 4 is proved,

Only part (i) of the following lemma is needed in this section. Part (ii) is
used in Section 5e We let N (Jt) be the number of finite sequences (i ls i 2 , 8 ,
ia)
of positive integers such that
(4.4) 1 < i^ < n, i 2 > it + i
if a > 1, and i
^ i + k for 2 ^ v < a ;
and are only interested in the values I = h and = h + 1.

Lemma 5. (i) For n ^ 1, N (h) = v ,4 ,
(ii) For n > 1, N n ( h + 1} =
Proof,
Vn
+ 1.
(i) By Theorem 1, for n ^ 1, there is a 1:1 correspondence b e -
tween sums of the form v. + v. + + v.
with condition (4.4) applied with
ft = h, and the integers in fO, v ,4 - l ] e Hence N (h) = v . .

L
J
n+i
n
n"r"i
(ii) If each finite sequence (i1? i 2 , ia) of positive integers,
with condition (4.4) applied with ft = h, is transformed by putting it = ]1 and
i + 1 = j
for 2 ^ v ^ ce , then we obtain all but one of the finite sequences
of
(3i J2* *3a)

a ^ 1 and j
is
positive integers, where

> j + k for 2 ^v < a
1 < j ^ < n + 1, j 2 ^
j 4 + h + 1 if
The finite sequence we do not obtain
(Ji) 9 when j x = n + 1. Therefore, by part (i),
(h + 1) = v
+1
for
n > 1. Hence N (h + 1) = v + 1 for n > 2. As part (ii) is clearly true when

n = 1, the proof of Lemma 5 is completed
338
[Nov.
L e m m a 6.
u
for n k
M j
n-k+i
(d - d
) - (e - e
) ={ 1
for 1 < n < k
n
n-i
n
n-l
J
for n < 1 .
T h e sequence
(u ) i s the (k,k)
F i b o n a c c i sequence.
Proof. By L e m m a 5(i), N (k) = u , for n > 1. T h e r e f o r e it follows

J
n
n+i
from L e m m a 4 that d - e = u ,, - 1. Hence for n > 2,
n
n
n+i
(d
- d
, ) - (e - e J
n-l
n
n-i
= (d - e ) - (d
- e
J
n
n
n-i
n-i
= (u __
, - 1) - (u - 1)
n+i
n
u , , for n > k ,
n-k+l
for 2 < n < k .
! 1
T h e r e s u l t i s e a s i l y seen to b e t r u e for n = 1 and i s t r i v i a l l y t r u e for n < 1.

T h i s p r o v e s L e m m a 6.
L e m m a 7e If k = 2,
t f
if t t
= 1 ,
n n
n
n-l
t f
if t t
= -1 .
n n-l
n
n-l
a
n
T h e sequence
Proof.
then aj = tj and for n > 1,
(f ) i s the (2,2)
Fibonacci sequence
(1, 2, 3, 5, 8, * ) .
By definition aA = ti.
Let n ^ 2 and t
, = 1. By
J L e m m a 3, if ti
l = +1 then
n-i
d
and e = e a
, and if t = - 1 then a = e - e ^
n-2
n
n-l
n-2
n
n
n
n-2
d , = d
. Also, by
L
e
m
m
a 2(i), 0 < d
< d and e < e ^ <
J
n-l
n-2
n-2
n
n
n-2
n
= e
a = d n
n
and d =
n
0. Hence
= L{ t (d - d ) - (e - e
J}
n
n
n-2
n
n-2 J
= t L{(d - d
) - (e - e J + (d
- d J - (e H - e
)}
n
n
n-i
n
n-l
n-i
n-2'
n-l
n-2 J
( t (f
+ fn_ ) if n > 3 |
=
k{ nVx n"- i ^ I1)"" if n= 2 JI ^ y L ^ a 6 ,
t f .
n n
Now let t
= - 1 . Then s i m i l a r l y by L e m m a s 2(i) and 3,
1967]
- d
n
e n
= t LX
{(d
n
n
= t f j9
n n-i
, if t
3 39
= +1 ,
?
n-i
n
e , if t = - 1 ,
n-i
n
- d
) - (e - e .)}
n-i
n
n-i J
byJ L e m m a 6 .
T h i s p r o v e s L e m m a 7
Proof of T h e o r e m 6.
We take
k = 2.
We suppose that t = s
for
^
n
n
n > 1, w h e r e (s ) i s the sequence defined in (2.3). Then, by T h e o r e m 4,
(a ) i s a (2,2) b a s e for T
1 with a s > 0 for n ^ 1. But bv L e m L
J
J
n
n n
m a 7, &i - Sj and
I s f
if s n sn__i = 1 I
a = \
r
.o
- / for n ^ 1.
n
Jsf
, i f s
s , = -11
f n n-l
n
n-i
/
T h e r e f o r e the sequence
(a ) i s the s a m e as the sequence
(b ) defined in the
s t a t e m e n t of T h e o r e m 6.
Hence (br,) i s a (2,2) b a s e for [-00,001 with a b

11
L
J
n n
> 0 for n > 1. T h i s p r o v e s T h e o r e m 6.
L e m m a 8. F o r n ^ 1, if x i s an i n t e g e r such that - u , + 1 < x ^ 0
_____-
'
then t h e r e e x i s t s a choice of (t1? t 2 , , t^)

Proof.
We u s e induction upon n
n+i
for which e
= x.
If ' tj = +1 then ei = 0,
while if
tj
= - 1 then ei = - 1 ; s i n c e -u 2 + 1 = - 1 , the L e m m a i s t r u e in the c a s e when

n = 1.
Let m > 2 be an i n t e g e r and s u p p o s e that the L e m m a i s t r u e for
<
Then if
-u
which we denote by
+ 1 < x < 0 t h e r e e x i s t s a choice of (t1? t 2 , j t ^ ^ ) ,

(t\, t ' , , t m _ i ) ,
^
c h o o s e (t l 9 1 2 , 8 s , t m )
for which
to be (tj, t j , - " , Vm_i, +1),
However, suppose that

(4.5)
1 < n
-u
, < x < -u
m+i
m
Then
(4.6)
x + u
m
T h e r e f o r e , by (4.5) and (4.6),
= x.
Hence, if we
m1
then by L e m m a 3, e
= x.
340

-u
(4.7)
[Nov.
. + 1 + u ,, , ^ x + u ,, , < 0 if m ^ k ,
m+i
m+l-k
m+i-k
and
- u _ + l + l ^ x + 1 ^ 0 .
m+i
But, from (2.1),
-u
,, + 1 + u . .
i f m ^ k ,
m+i
m+l-k
-u
+ l = I - u
^ + 1 + 1
if 2 < m < k .
m
J
m+i
(4.8)
T h e r e f o r e , by (4.7) and (4.8),

I (-u
(4.9)
+ 1) ^ x + u
,, , <
1-k
I (-u
+ l ) 2 = x + 1 ^ 0
\
m
0 if m > k,
and
if 2 < m < k .
T h e r e f o r e , by the induction hypothesis and (4.9), t h e r e e x i s t s a choice of

(tl912, , t m _ i ) ,
which w e denote by (t?1? t^, , t ^ ^ ) ,

1/
(4.10)
x + 1
If we choose (t1? t 2 , ' " ' , t m )

m
= d
m - i4
, , if m ^ k ;
m+l-k
m-l
x + u
for which
if 2 < m < k ,
to b e (t^, t, * , t m - 1 , - 1 ) ,
then by L e m m a 3,
and so byJ L e m m a 6,
I e
, - u
, .
I m-l
m+l-k
(4,11)
J e
- 1
i f m ^ k ,
if 2 < m < k .
m-l
Hence, by (4.10) and (4.11),
= x.
L e m m a 8 now follows by induction.

Proof of T h e o r e m 3.
If p i s an i n t e g e r such that - u
by L e m m a s 4 and 8, t h e r e e x i s t s a choice of (t1? t 2 , , t p ) ,

by (tT, V, , t' ),
such that (a 1? a 2 , , ap) i s a
(k,k)
+ 1 < - m then,
which w e denote
b a s e for
[-m, dp].
1967]
Then, if t
= t^ for 1 < n < p and t
341
= +1 for n > p, by Lemmas 3 and
4, (a1? a2, , a n ) is a (k,k) base for [ - m , d ] for n > p. By Lemmas 2 (ii)

and 3, d oo as n-ôo, Hence (a ) is a (k,k) base for [-m,oo] 8
Proof
5. We take k = 2. We suppose
that t n = s n for
of Theorem ,
fr
n > 1, where (s ) is the sequence defined in (2.5). By (2.4), i
> iv+ 2
for 1 < v < a,
and so, by (2.5) and Lemma 2(ii), for n > i + 1,
(4.12)
= a. ^ + a. _^ + + a. ^
However, by Lemma 7, aj = Sj and
s f
nn
if s s , = +1 I
n
n-i
/
for n > 2
s n ffn-l, iff s n sn-i = -1 I

Hence the sequence (a ) is the same as the sequence (b n ) defined in (2.6).
But by (4.13) and (2.5), a j v + 1 = Sj +1j[
(4.12) and (2.4), e
as n-*oo,
= -fj
for 1 < v < a.
Hence,
by
= -m for n > ia + 1. From Lemmas 2(ii) and 3, d -* oo.
and so, by Lemma 4,
(b n ) is a (2,2) base for [-m,oo],
5. PROOF OF THEOREM 7
Let S = (s n ) be a sequence such that s E {-1> 1} for n > 1, let m
be a positive integer, and let (i1? i 2 , e " , i#) be a finite sequence of positive
integers such that
(5.1)
i 2 > ii + h + 1 if
a > 1
and
> i v + k for 2 < v < a .
Lemma 9. If (i1? i 2 , , i^,) = <f>, the empty set, then

S V
ih
+ S2V
ia-i
' ''
S v
^ ii
Lemma 10. If si = +1 then s^yi + S2VJT

Proof.
+ e + s^v^ ^ 0.
Let sj = 1. If a = 1, then s.v,- + SpV-,-
> 1. If or > 1 then
+ + s^v-.v = v*
342

s
i%
*%-i
*'
^vii "
"
ia "
%-i
% .
( v
+ 1
"
1)s
' ' '
[Nov,
+
ii}
b y T h e o r e m 15
T h i s , together with L e m m a 9, p r o v e s L e m m a 10.

Proof of Sufficiency.
i
n+i
= (-1)
f o r n 1,
Suppose that s
and that
^ m . Since ( v n ) i s a s t r i c t l y i n c r e a s i n g sequence, it follows that if a ^ 1
then SiVjL + s2Vi
+ + s^Vj ^ v^ v .
Hence,
and in view of L e m -
m a s 9 and 10,
(5.2)
0 ^ s lViQf + S 2 V 1 Q / _ 1 + -
+ s 0 ? v i l = v m
We show now that any two distinct finite s e q u e n c e s

satisfy (5.1) yield distinct v a l u e s of s-^v-;
+ s2v.;
(il5i2!t,o,i^)
+ s v-
which
Suppose
t h e r e f o r e that two such distinct finite s e q u e n c e s a r e (ji, j 2 , , ]p ) and (g1?

g2'" V Sy)
We suppose without l o s s of g e n e r a l i t y that v ^ . v
, and c o n -
sider three cases.

Case [ l ] .
|8 = 1. Then
SlVj^ + S . V j ^ + . . .
Case [ 2 ] ,
>
3)3-1
j8 = 2.
+ S
+ SpVh
= VJ^ 2> V
i3V3r = v3/3 -
3,3-i
3/3 " v 3/3-h-l
^Vj^ " V
Then
^ SlVgy + S 2 V g y _ 1 + ^
Then
"
C a s e J 3 ] . jS = 2.
g y
k=
^r1,
lf k = h
+SyVgi9
1967]

>V
"
J^ -
^ -
J/3-l
J/3-k
343
- v j ) 3 _ k - (k - 1h)
- 1, by (2.1) ,
= V
J/3
>
"vgy
SlVgy + S2Vgy
-i
+... +s
By L e m m a 5(ii), t h e n u m b e r of d i s t i n c t finite s e q u e n c e s
with ia < m which satisfy (5.11) i s v
y Si
(i l 9 i 2 , - , i # )
+ 1. T h e r e f o r e , since any two such
distinct finite s e q u e n c e s yield distinct v a l u e s of s^v; + S2VJ;
+ + s^Vj ,
and in view of (5.2), it follows that (v1? v 2 , , v m ) i s an (h + 1, k;S) b a s e

n+i
for [ 0 , v m ] when s = (-1)
f o r n > 1. T h e sufficiency of t h e condition
follows.
Proof of N e c e s s i t y .
o]e We show that s
Suppose that
( v n ) i s an (h + l,k ;S)
b a s e for [ 0,
f o r n ^ 1* C l e a r l y s$ = + 1 , for o t h e r w i s e
n+i
s
lVi = - 1 , a contradiction,, We s u p p o s e that s = (-1)
for 1 ^ n ^ m
and that s
= (-1)
, and deduce a c o n t r a d i c t i o n in e v e r y c a s e .
Case [ 1 ] .
a = 1 and
= (-1)
m = 1.
ia > h + 2
Then st = s 2 = + 1 . We w r i t e
then
SJVJL + s2v-;
+ + s Vj
M = v h + 2 - v l e If
= v ^ > M,
whereas
if a = 1 and ia < h + 1 then

M - vh+2 =
Vl
Vl
+ V
+ v
h+2-k
v
(k
if
h = k
h)
" ^
{ZA)
**
= | h+i
2 ~ i>
'
( v u + 1 + Vi + 1 - v 1? if h + 1 = k,
h+l
ia
On t h e o t h e r hand if a > 1 then i > h + 2,
s v
i ia
2%-i
"
*vii - %
-
ta-i
+ v
i^+
and s o
i*-i "
V
(v
**-l "
^ - 2 + %-3
(
%-2+1 "
by T h e o r e m 1,
> v,>
+ 1
v, ^ > M .
h+2
1)J
'* '
344
[Nov,
M f
(i l s i2,
Hence
>!#)
Sf^
for any finite sequence
satisfying (5.1), which c o n t r a d i c t s our a s s u m p t i o n that
(h + l,k;S) b a s e for
Case [ 2 ] .
(5.3)
v
'
+ s2v-i + + S^VJ,
(v n ) i s an
[0,oo].
m > 1.
We w r i t e
N = Siv 7
v, ,
+ SoV/
x, ,
+ + s v,
+ s
Vi .
1
2
(m-i)k+h+2
(m-2)k+h+2
m h+2
m+i *
It follows from L e m m a 10 that N ^ 0.
v
û
, - i2 ^
h+2
ik+h+2
,u ,
V/(m-i)k+h+2
v. ,, , , while if m
'^v(m-2)k+h+2
(m-i)k+h+2
If m = 2 then
>
%, then
N = v. ,,
k+h-2
( m - s ) k+h+2
/(m-i)k+h+2
HMÛ,
- (v/(m-2)k+h+i
v, u , + (k - h)) + 1,
byJ (2.1)
< v
(m-l) k+h+2 "
Hence
"
"
(m-l)k+h+2
Now N i s the only n u m b e r of the f o r m S{Vi + s 2 v;

a = m + 1 and i a (m - l ) k + h + 2.
{n: n = S j v ^ + s ^ ^
U{N-2sm+lVl}
+ + s ^
+ + s VJJ with
Hence, by the proof of the sufficiency,
iff<
(m-l)k + h + 2
anda<m}
= {0, 1, 2, v ( m _ l ) k + h + 2 } .
T h e r e f o r e , by (5.4),
N can b e put in the f o r m
with a < m.
Hence, and by (5.3) N h a s two r e p r e s e n t a t i o n s in the f o r m N =
s-tV;
+ + s VJ_ , which c o n t r a d i c t s our a s s u m p t i o n that ( v n )
+ s2v^
an ( h + l , k ; S )
b a s e for
[0,oo].
We conclude t h e r e f o r e that
the proof of T h e o r e m 7.
is
= (-1)
n+l
for n > 1.
This completes
1967]
BASES FOR INFINITE INTERVALS O F INTEGERS

6.
345
P R O O F O F THEOREM 8
We show t h a t if ( v n ) I s defined b y (2.8) then the defining r e l a t i o n s (2.1)

of the
(h5k)
Fibonacci sequence hold,
If a < b
then I , J = 0.
Hence the infinite s u m of (28) contains only a
finite n u m b e r of n o n - z e r o t e r m s .
In fact, for
1 ^ n ^ k,
the r e l a t i o n (2.8)
r e d u c e s to
T
if k = h,
holds.
rn + k - 2 >
--i
--ft
or v
= I
1 if k = h + 1,
On the o t h e r hand, if n
h + 1 = k,
o
>
k,
(7)
and so the f i r s t of the r e l a t i o n s (2.1)

by checking e a c h s t a g e with h = k and
and u s i n g the fact that
GMVM:::).
we have
v
n-i
+v
. + (k - h)
n-k
-
1)+
/ n - l - h + (k-l)(2-i)\
S 1
i=k-h x
i
'
o
/ n - k - h + ( k - 1)(2 - i) \
+ Z
i=k-h V
00
'
/ n - 1 - h + (k - 1)(2 - i ) \
/ n - l - h + (k-
) - T, (
(
i=i \
I
-
l / n - l - h
/
i=i+k-h *
+ (k-l)(2-i)\
(k-h) + E
i=i
' V
/ n - l - h + ( k +
i - i
1)(2 - i) \ /
^
i - 1
346
BASES FOR INFINITE INTERVALS O F INTEGERS

-
/ n - h + (k-l)(2-i)\
i=k-h \
= v
[Nov. 1967]
as required.
REFERENCES
1.
Dc E. Daykin, " R e p r e s e n t a t i o n of N a t u r a l N u m b e r s a s Sums of G e n e r a l i z e d

Fibonacci Numbers,
2.
J o u r . London Math, S o c , , 3 5 ( 1 9 6 0 ) , 143-60.
N. G. deBruijin, "On B a s e s for the Set of I n t e g e r s , " P u b l i c a t i o n s M a t h e m a t i c a e (Debrecen), 1 (1950), 232-242 0
3.
J . L. Brown, J r . ,
Note on Complete Sequences of I n t e g e r s ,
American
Math Monthly, 68(1961), 5 5 7 - 6 1 .

4.
R. L. G r a h a m , "On F i n i t e Sums of Unit F r a c t i o n s , " P r o c .
London Math.
Soca (3), 14 (1964), 193-207.

A NEW IMPORTANT FORMULA FOR LUCAS NUMBERS

Dov J a r den
Jerusalem, Israel
The formula
L
ion
(1)
( L ^ - 3) 2 + ( 5 F 2 n ) 2
2n
m a y b e e a s i l y verified putting L
= a
n
F
Since for n > 0,
+ jS ,
0n
= ^ - ^
*0 = - l -
V5
(1) gives a decomposition of L 1 0 n / L 2 n into a s u m of
2 s q u a r e s , and s i n c e any d i v i s o r of a s u m of 2 s q u a r e s i s - 1 (mod 4), it follows

that any p r i m i t i v e d i v i s o r of L^n*
n > 0,
*****
is - 1 (mod 4) .
SOME PROPERTIES ASSOCIATED WITH SQUARE FIBONACCI NUMBERS

J O H N H. HALTON
Brookhaven National Laboratory f Upton,, Long Island, New York
1.
INTRODUCTION
In 1963, both M o s e r and C a r l i t z [ 1 1 ] and Rollett [ 1 2 ] p o s e d a p r o b l e m .

Conjecture 1,
F 0 = 0,
The only s q u a r e Fibonacci n u m b e r s a r e

F_i = F i = F 2 = 1,
and
F l 2 = 144 .
Wunderlich [ 1 4 ] showed, by an ingenious computational method, that for

3 < m < 1000008, the only s q u a r e F
is F 1 2 ; and the c o n j e c t u r e w a s p r o v e d
analytic ally by Cohn [ 5 , 6, 7 ] , B u r r [ 2 ] , and Wyler [ 1 5 ] ; while a s i m i l a r r e sult for L u c a s n u m b e r s w a s obtained by Cohn [ 6 ] and B r o t h e r Alfred [1]
Closely a s s o c i a t e d with Conjecture 1 is
Conjecture 2.
When p is p r i m e , the s m a l l e s t F i b o n a c c i n u m b e r d i v i s -
ible by p is not divisible by p2

It is known (mostly from Wunderlich ? s computation) that Conjecture 2
holds for the f i r s t 3140 p r i m e s
514229*
(p < 28837) and for p = 135721, 141961, and
C l e a r l y , Conjecture 2, t o g e t h e r with C a r m i c h a e P s t h e o r e m (see [ 4 ] ,
T h e o r e m XXIII, and [ 9 ] , T h e o r e m 6), which a s s e r t s that, if m ^ 0, with the

exception of m = 1, 2, 6, and 12,
that F
m
for each F
there is a p r i m e p,
such
i s the s m a l l e s t Fibonacci n u m b e r divisible by p (whence F

i s not
J
^
m
divisible by p 2 and so cannot be a s q u a r e , if Conjecture 2 holds),

Conjecture 1; but not v i c e v e r s a ,
implies
If Conjecture 2 h o l d s , then the divisibility
s e q u e n c e t h e o r e m ( [ 9 ] , T h e o r e m 1) can b e s t r e n g t h e n e d to say that, if p

an odd p r i m e and n ^ 1,
(1)
<*(p,n) = p
or(p) .
In the notation of [ 9 ] , Conjecture 2 for a given p r i m e p s t a t e s

F , v i s not divisible by
*This work performed
Commission.
is
then
p2,
T h i s , by L e m m a 8 and T h e o r e m 1 of [ 9 ] ,
under the a u s p i c e s of the U.
S Atomic
that
is
Energy
The p r e s e n t p a p e r i s a r e v i s e d v e r s i o n of a r e p o r t w r i t t e n u n d e r
a u s p i c e s of t h e U. 3* AEC w h i l e t h e a u t h o r . w a s a t Brookhaven
N a t i o n a l L a b o r a t o r y , Upton 9 L . ' I . , N . Y. ( R e p o r t NeAMD/38^ BNL9300).
347
348
SOME P R O P E R T I E S ASSOCIATED
[Nov.
equivalent to
a(p2)
(2)
= pa(p)
Since v.(p) i s the highest power of p dividing F . ,,

(3)
v(p)
By L e m m a 11 of [ 9 ] ,
namely
F>^,
<*(p),
1.
p divides one and only one of F
where
T h u s , if p > 5,
this is equivalent to:
\(p) = p - (5/p)
and
(5/p)
s i n c e \(p) i s not d i v i s i b l e , b y p ,
F ,
and F
is the L e g e n d r e index,,
while it is divisible by
(2) is equivalent to
(4)
, v i s not divisible by p 2 ,
and inspection of the c a s e s p = 2, 3, and 5,
shows that the equivalence holds
for t h e s e p r i m e s a l s o .
Finally, (4) i s equivalent to:
F ,, i s not divisible by
p2
J
p - l p+l
*
(5)
T h i s p a p e r p r e s e n t s c e r t a i n r e s u l t s obtained in the c o u r s e of investigating

the two C o n j e c t u r e s , the l a t t e r of which i s s t i l l in doubt*
2.
A THEOREM OF M. WARD
We begin with a t h e o r e m posed as a p r o b l e m (published posthumously) by

Ward [ 13].
A different proof from that givenbelow w a s obtained independently
by C a r l i t z [ 3 ] .
T h e o r e m A
(6)
Let
<fc&) =
s=i
and
xS/s
1967]
WITH SQUARE FIBONACCI NUMBERS
349
k (x) = (xP" 1 - l ) / p ;
(7)
then, for any p r i m e n u m b e r p 5,
p 2 divides the s m a l l e s t Fibonacci n u m -
b e r divisible by p if and only if
(8)
c ^ )
Proof,
(|)
= 2 k p ( I ) (mod p) .
We shall show that (8) is t r u e if and only if (5) is false Q
We
shall u s e the congruence (see [ 1 0 ] , page 105) that, when 1 t p - 1,
K')
(9)
-If)
= (-Dt
(modp)
and F e r m a t T s t h e o r e m (see [ 1 0 ] , p a g e 63), that

(10)
if (a,p) -
1,
ap-1
= 1 (mod p )
T h e identities
(ID
.-ÎHTff )"!
=
(12)
<14>
Fî
= F^
F ^
+ (-l)n = F n _ i r n + 1
and
(15)
v
'
3F2 + 2 ( - l ) n = F2
+ F2
n
n-l
n+l
a r e well known (see [ 8 ] , equations (3), (5), (64), (65), (67), and (95) with
m = l)o
F r o m then it follows that (since
(1 V5) 2 = 2(3 V5) )
350
[Nov9
,T\"2Q
il6)
=F4n/F2n
= F f f i . i + F 2 n + 1 = 2F2 + F ^
= 5F^ + 2(-l)n = 5 F n _ 1 F n + 1 - 3(-l)n

Now, s i n c e
(7),
p > 5,
F ^
is odd and -(p - 1) i s an i n t e g e r .
the factor = 6 p [ | ( p - 1)] I
and k (3/2) into i n t e g e r s .
By (6)
is p r i m e to p and m a k e s both
T h u s , modulo p ,
fa.
and
v(5/9)
by (6), (9), (16), (7), and '(10),
-i|(t) P < 5 v.v. + 3 >- 2 }

= -5"1P[S(P " Ifl'V . V>
/P) +
' (^)P"' ' 2kf
' 2kp (l) - S < V V / P ) '

w h e r e f and g
a r e i n t e g e r s p r i m e to p ,
It follows that (8) is t r u e if and only if
(F
and
F
F
+1
/p
is an integer.
/p) = 0 (mod p),
and this
c o n t r a d i c t s (5), proving the theorem,,

3.
ANOTHER CONJECTURE
We end the p a p e r with an examination of a conjecture, which i m p l i e s the

f i r s t conjecture (known now to b e t r u e ) , in a r a t h e r different way from Conj e c t u r e 2.
T h e underlying r e s u l t i s
T h e o r e m Bo
i n t e g e r M,
Let p be a p r i m e , and suppose that t h e r e e x i s t s a p o s i t i v e
such that
(i) for no i n t e g e r n, p r i m e to p and g r e a t e r than M, is

o r p t i m e s a s q u a r e ; and
a square
1967]

(ii) if n i s p o s i t i v e and not g r e a t e r than N,
t i m e s a s q u a r e , then F,
Proof.
is a square or
Suppose that (i) and (ii) hold, and that F
D divides
Let m = p m i ,
* l
and A
is
M*
= AB C ,
Then, b y (i),
= BC 2 D,
1 or p.
t i m e s a s q u a r e , and divisible by F
and w r i t e F
>
is a square or p
In contradiction of the t h e o r e m , l e t m > M.
m i s divisible by p
such that k / n i s a power of p;
at all i s a s q u a r e o r p t i m e s a s q u a r e for m
times a square.
where
and F
i s n e i t h e r a s q u a r e n o r p t i m e s a s q u a r e , when k
is the l e a s t i n t e g e r g r e a t e r than M,
then no F
351
mj
This makes F
a square or p
Now, by the well-known identity (see
[8, equation (35)], o r [9]* equation (8)] )
(17)
F
m
mj
= y ( P ) F h " 1 F p " h F,
X*. I h i m i m i - l h
w e get that
B(A/D) = BC*D V (A
F h ' 2 F P ~ \ Fh + pF*5"1
A^ I h i
Also,
mi
mi-i
mi-l
^ mi-
(F
y
- 1, F
) = 1, so B m u s t divide p;? that i s , B i s 1 o r p;
mi
mi
^
^'
and again D i s 1 o r p . It follows that F
, too, i s a s q u a r e o r p t i m e s
J,
a square.
Arguing s i m i l a r l y , we s e e that, if
m = p m ,
then
is a
s q u a r e o r p t i m e s a square,,
T h i s will continue until (m ,p) = 1, and then,

S
t
< M. But then, b y (ii), if p m = m . i s the l e a s t such n u m -
by (i) 1 ^ m
S
"
b e r g r e a t e r than M,
square,,
s ^ t,
and F
S L
cannot be a s q u a r e o r p t i m e s a
T h i s c o n t r a d i c t i o n shows the c o r r e c t n e s s of t h e t h e o r e m .
Conjecture 3.
T h e r e is no odd i n t e g e r m > 12,
such that F
is a
s q u a r e o r twice a square,,
T h e o r e m C Conjecture 3 i m p l i e s Conjecture 1.
Proof.
M = 12.
Conjecture 3 s t a t e s condition (i) of T h e o r e m B, when p = 2 and
T h e only
squares are Fj = F2 = ls
c o r r e s p o n d i n g F,
with
1 < m < 12,
F 3 = 2,
a r e F i 6 = 3 747
is a s q u a r e o r twice a s q u a r e .
F 6 = 8,
which a r e s q u a r e s o r twice
and F 1 2 = 144.
5
However,
the
and F24 = 2 3 7 2 3 , and n e i t h e r
Thus (ii) holds also, whence the conclusion of
T h e o r e m B , which includes Conjecture 1, i s es tablished.
352
SOME PROBLEMS ASSOCIATED

4.
[Nov.
PYTHAGOREAN RELATIONS
We c l o s e this p a p e r by a r a t h e r c l o s e r examination of Conjecture 3,

using the identities (12) and (13), with the well-known r e s u l t , that the r e l a t i o n
x2 + y2 = z2
(18)
holds between i n t e g e r s if and only if t h e r e a r e i n t e g e r s

p r i m e and of different p a r i t i e s , and an i n t e g e r u,
x = (s 2 - t 2 ) u ,
(19)
y = 2stu,
s and t,
mutually
such that
z = (s 2 + t 2 )u .
and
Conjecture 3 l e a d s us to e x a m i n e the p r o p e r t i e s of F i b o n a c c i n u m b e r s
F
, which a r e s q u a r e s or twice s q u a r e s , for odd i n t e g e r s m.
We obtain
the following r a t h e r r e m a r k a b l e r e s u l t s .
T h e o r e m D,
i n t e g e r s r , s,
even,
If m i s odd,
and t,
(s, t) = 1,
(20)
i s a s q u a r e if and only if t h e r e
such that m = 12r 1 ,
s i s odd,
t is
and
F 6 r 1 = s 2 - t2 .
F 6 r = 2st,
Proof,
s > t ^ 0,
are
Since m is odd, put
m = 4n 1,
determining
uniquely.
Then, by (12),
(21)
Thus F
= F 4 n 1 = F^n + F2ni .
i s a s q u a r e if and only if F ^ ,
ean t r i p l e t .
2st,
Since ( F 2 n , F 2 n i) = 1 u = 1,
while F ^ i
) = 1,
^ d A/F~~ f o r m a P y t h a g o r -
and this p a i r is
2 2
= . ( s t ) T h i s gives that s and t
and of different p a r i t i e s , with s ^ t > 0.

(F , F
F2ni
and
a r e mutually p r i m e
By (12), F ^ i
= F2 + F2
Since
not both n u m b e r s a r e even, whence F 2 n : ti is e i t h e r odd o r
the s u m of two odd s q u a r e s , which m u s t be of the f o r m

divisible by 4, it follows that
(22)
(s 2 - t 2 )
F 2 n = 2st,
Fm1
= s 2 - t2 .
8k + 2.
Since 2st
is
1967]
A l s o , by (13),
353
2st - F ^ F ^ + F n + 1 ) = F ^ F ^ + F n ) .
Since this m u s t b e
divisible'by 4, and (F , 2 F n _ + F ) = ( F , 2 ) ,
= 3r
m u s t be even, so that n
(since F 3 = 2); whence m = 12r 1, a s s t a t e d in the t h e o r e m , and (22)
b e c o m e s (20).
s 2 - t2 = F 2 + F 2 _
Finally,
s u m of an odd and an even s q u a r e .
i s of the f o r m 4k + 1,
being the
T h u s s m u s t be odd and t even, a s was
asserted.
Since Conjecture 1 i s valid, i t follows f r o m T h e o r e m D that, if r ^ 2,
the equations (20) a r e not satisfied by any i n t e g e r s
T h e o r e m E
If m i s odd,
a r e i n t e g e r s r , s,
both odd,
and t,
(s, t) = 1,
r , s, and 6.
i s twice a s q u a r e if and only if t h e r e
such that m = 12r 3 ,
s ^ t
>
0 ,
s and t a r e
and
F 6 r = s 2 - t2, F 6 r 3 = 2 s t .
(23)
P r o of.
b y (21),
Fm
We p r o c e e d much a s for T h e o r e m De
Let m = 4n + l a
Then,
and F 2 n i m u s t both be odd (since they cannot both be even),
so that F 2 n i i s even (since one out of e v e r y consecutive t r i p l e t of Fibonacci

n u m b e r s , one i s even, and i t s index i s a multiple of 3). Thus 2n 1 = 6r 3 ,
whence m = 12r 3,
a s s t a t e d in the t h e o r e m .
s i n c e 2n = 6r 2 and 2n 1 = 6r 1,
(24)
6r+2
6r+l ~
6r+3
F 6 r _ 2 + F 6 r j; = F 6 r ,
It i s e a s i l y v e r i f i e d that,
and
6r+2 "
6r+i ~
6r
F 6 r 2 - Fg-p.j = - F 6 r _ 3
equation (21) yields that

2
F 1 2 r ^ 3 ~ (F 6r -t2
F6r:tl)
+ (F6r2 " F6r1)
25
( )
Thus F
i s twice a s q u a r e if and only if F 6 r ,
Pythagorean t r i p l e t
by 8,
Clearly,
+ F2
x
6r
6 r3
F2
F6ri3,
s i n c e F 3 = 2 and
and V 2 F 1 2 r i 3 f o r m a
F 6 = 8,
F 6 r i s divisible
but F 1 2 r ^ 3 and F 6 r 3 a r e divisible by 2, but not by 40

2
and F 6 r and F 6 r i . 3 a r e of the f o r m s 2(S - T ) and 4ST, w h e r e

(S, T) = 1,
and S and T a r e of opposite p a r i t i e s .
In fact,
Thus u = 2
S > T > 0,
354
[Nov.
F 6 r = 4ST and F 6 r 3 = 2(S 2 - T 2 )
(26)
s i n c e 4ST i s c l e a r l y divisible by 8.
holds, and c l e a r l y s ^ t ^ 0,
Put S + T = s and S - T = t;
(s,t) = 1,
and
and
then (23)
t a r e both odd,
as
s t a t e d in the t h e o r e m .
We finally note that Conjecture 3 holds if, for
a r e not satisfied by any i n t e g e r s
r,
s,
r ^ 2,
the equations (23)
and t.
REFERENCES
1.
B r o t h e r U. Alfred, "On Square Lucas N u m b e r s , " The Fibonacci Q u a r t e r l y ,

Vol. 2, (1964), pp. 11-12.
2.
S. A. B u r r , "On the O c c u r r e n c e of Squares in L u c a s Sequences, " A. M. S.

Notices (Abstract 63T-302) 10 (1963), p . 367.
3.
L. C a r l i t z , Solution to P r o b l e m H-24, T h e Fibonacci Q u a r t e r l y , Vol. 2,
4.
R. D. C a r m i c h a e l ,
(1964) pp. 205-207.

1
a
5.
"On the N u m e r i c a l F a c t o r s of t h e A r i t h m e t i c F o r m
fi , " Ann, Math. , Vol. 15 (1913-14), pp. 30-70.
J . H. E. Cohn,
"On Square F i b o n a c c i N u m b e r s , " P r o c . ,
1963 N u m b e r
T h e o r y Conf. (Boulder, 1963), pp. 51-53.

6.
J . H. E. Cohn, "Square Fibonacci N u m b e r s , E t c . , " T h e Fibonacci Q u a r t e r l y , Vol. 2, (1964), pp. 109-113.
7.
J . H. E. Cohn, "On Square Fibonacci N u n b e r s , " J o u r . Lond. Math. Soc. ,

Vol. 39, (1964), pp. 537-540.
8.
J . H. Halton, "On a G e n e r a l Fibonacci Identity," T h e Fibonacci Q u a r t e r l y ,

Vol. 3, (1965), pp. 3 1 - 4 3 .
9.
J . H. Halton, "On T h e Divisibility P r o p e r t i e s of F i b o n a c c i N u m b e r s , " The

Fibonacci Q u a r t e r l y , Vol. 4, (1966), O c t . , pp. 217-240.
10.
G. H. Hardy,
E. M. Wright, An Introduction to the T h e o r y of N u m b e r s ,
(Clarendon P r e s s , Oxford, 1962).

11.
L. M o s e r ,
L. C a r l i t z ,
P r o b l e m H - 2 , The F i b o n a c c i Q u a r t e r l y , Vol.
1,
No. 1, (Feb. 1963), p . 46.

12.
A. P . Rollett, P r o b l e m 5080, A m e r .
Math. Monthly, Vol.
70, (1963), p .
216.
13.
M. Ward, P r o b l e m H-24, The F i b o n a c c i Q u a r t e r l y , Vol. 1, No. 4, (Dec.

1963), p. 47.
1967]
.WITH SQUARE FIBONACCI NUMBERS
355
14. M. Wunderlich, "On the Non-Existence of Fibonacci Squares, " Math.

Comp. , Vol. 17 (1963), pp. 455-457.
15. O. Wyler, Solution to Problem 5080, Amer. Math. Monthly, Vol. 71,
(1964), pp. 220-222.
* *
The Fibonacci Bibliographical Research Center desires that any reader

finding a Fibonacci reference send a card giving the reference and a
description of the contents.
brief
Please forward all such information to:
Fibonacci Bibliographical Research Center,

Mathematics Department,
San Jose State College,
San Jose, California
P I C K I N G
AUAY
AT
1967
CHARLES U. TRIGG
San DiegOp California
1967 can be made from two 2's, three 3 f s, four 4 ! s, five 5 ! s,

six 6 f s ? or seven 7fs with the aid of eighteen toothpicks and
mixed Arabic and Roman number symbolism*
That is,
! 315*7 = \/1 v/ vi vi \/i v/ =

11
jj !!=!!! !',! ill =:viV.v,v
A GENERATING FUNCTION ASSOCIATED WITH THE GENERALIZED

STIRLING NUMBERS
ROBERT FRAY
Florida State University, Tallahaslee^Florida
1.
INTRODUCTION
E. T. Bell [2] has defined a set of generalized Stirling numbers of the

second kind S, (n,r); the numbers Sj(n,r) are the ordinary Stirling numbers
of the second kind,,
Letting X(n) denote the number of odd Si(n + 1, 2r + 1)
Carlitz [ 3] has shown that

00
n
n+i
X Mn)xn = n (1 + x2. + x2
) .
n=o
n=o
In Section 3, we shall determine the generating function for the number
of odd generalized Stirling numbers S 2 (n,r).
Indeed we shall prove the fol-
lowing theorem,
Theorem,
Let cu(n) denote the number of odd generalized Stirling num-
bers S2(n + r, 4r); then
o>(n)xn = n (1 + x 3 " 2
n=o
n=o
+ x2
) .
Later Carlitz [4] obtained the generating function for the number oi
Si(n, r) that are relatively prime to p for any given prime p.
It would be oi
interest to obtain such a generating function for the generalized Stirling numbers S, (n, r). At present the apparent difficulty with the method used herein
is that, except for the case k = 2 and p = 2, the basic recurrence (2.4) for
S, (n, r) with k > 1 is a recurrence of more than three terms, whereas for
the cases that have been solved we had a three-term recurrence,, In Section4,
we shall discuss this problem for the numbers S2(n, r) and the prime p = 3;
several congruences will also be obtained for this case,
*Supported in part by NSF grant GP-1593.
356
A
GENERATING FUNCTION ASSOCIATED
WITH THE GENERALIZED STIRLING NUMBERS
2. PRELIMINARIES
Nov 1967
357
The numbers S, (n, r) maybe defined by introducing an operator r which

transforms t into (e - 1) . Powers of r are defined recursively a s
follows:
(2.1)
r t
t ) ,
T(T
where u is a positive integer,. We shall also define Tt

ized Stirling numbers are then defined by
(2.2)
'-
= t . The general-
T V = r! 2]S k (n 3 r) L-
Hence Si(n, r) is the ordinary Stirling number of the second kind (see [ 5*
pp. 42-43]) and S0(n, r) = 8(ns r), the Kronecker delta.
From (2.1) and (2.2)
we can readily see [ 2, p 93] that
(2.3)
i+k ( n s r )
X^Si(n3i)Sk(i'r)
i = r *
Hence the numbers S, (n, r) can be derived from the ordinary Stirling numbers
of the second kind by repeated matrix multiplication (see [ 5, p. 34]).
Becker and Riordan [1] have studied some of the arithmetic properties
of these numbers; in particular, they obtained for S, (n, r) the period modulo
p,
a prime.
In the same paper they derived the following basic recurrence
modulo p (equation (5.4)):
(2.4)
Sk(n + p S ,r) , ^
j=o
E IS
i
+E
{ " *) s > ' i)S k i ( i +

]
/
(s
j=* I
/
+ k
1>T)
- \
- ! ~ j | S. (n, r - p J ) (mod p)
k- 1
358
A GENERATING FUNCTION ASSOCIATED

3C
[Nov.
PROOF OF THEOREM
F o r p = 2 we have from (2.4) that

S2(n + 4, r) = S2(n + 1, r) + S 2 (n, r - 4)
(mod 2)
Hence if we l e t
n
S n (x) = ] P s 2 ( n , r ) x r
(3.1)
r=o
it follows that
S n+4 {x) + S n + 1 (x) + x 4 S n (x) = 0 (mod 2) ..
(3.2)
Let ai, a2, a 3 ,
and a b e the r o o t s of the equation

y4 + y + x 4
in F [ y ] ,
where
F = GF(2,x) 5
the function field obtained by adjoining the
i n d e t e r m i n a t e x to t h e finite field GF(2).
Also let
(3.3)
</>n(x) = J V
3=1
Then from the definition of the a T s we s e e that

/
$0(x)
= <f>t(x) = <f>2(x) = $ 4 ( x )
0, < 3 (x) =
Moreover
(3-4)
hence
4> n+4 (x) = n + 1 ( x ) + x ^ n ( x )
J
I
1967]

<5(x) = 0,
359
</>6(x) = 1 .
Now put
(3.5)
S n (x) = (x3 + x + l ) 0 n ( x ) + x ^ n + i ( x ) + x 0 n + 2 ( x ) + 0 n + 3 ( x )
Then
S0(x) = 1
S2(x) = x
Si(x)' = x
S333(x) = x 3 + x + 2
R e f e r r i n g to the t a b l e at the end of the p a p e r we s e e that by (3.1)

S (x) = S (x)
n
n
for n = 0,'l, 2,
(mod 2)
and 36 T h e r e f o r e we s e e f r o m (3.2), (3.4), and (3.5) that
(3.6)
S n (x) = S n (x)
(mod 2)
for all non-negative i n t e g e r s n*

F r o m (3.3) we have with a l i t t l e calculation that
n=o
j=l
1 + t3 + x 4 t 4
k
J
3k+j+3=n
n=o
) x*fl .
therefore
(3.7)
* (x) = V
) x 4(n-3k-3)
\n-3k-3/
360
[Nov.
Combining (3.1), (3.5), (3.6) and (3.7) we have
r=o
'
x\Y(
X
\x4(n-3k-3) + Y I
(^^-3k-3J
\x^
^n-3k--ljx
k
k
x2 'Y(
\ x4(n"3k-2) +x*Yl
^ 4(n-3kX
M n - 3k-2iX
Y\n-3k-3/
x
(mod 2)
C o m p a r i n g coefficients we s e e that
S 2 (n,4j) = ( j !
(j = n - 3 r - 3)
S 2 (n, 4j + 1) = / r ]
(j = n - 3r - 3 o r n - 3r - 1)
S2(n,4j+2)
= [*")
(j = n - 3r - 2)
S 2 (n,4j + 3) = ( * )
(j = n - 3r - 3)
(3.8)
w h e r e the modulus 2 is understood in each congruence,

Let 0.(n) denote the n u m b e r of odd S 2 (n,k),
k = j (mod 4)
0 < k < n,
(j = 0 , 1 , 2 , 3 )
with
By the f i r s t congruence in (3.8) we s e e that

S2(n + 1, 4j + 4) = | r |
(mod 2) (j = n - 3r - 3) ,
and h e n c e
(3.9)
0ofo + D
Similarly since
S2(n + 29 4j + 4) = / A (mod 2) (j = n - 3r - 2)
1967]
WITH T H E GENERALIZED STIRLING NUMBERS
361
it follows that
(3.10)
0 o (n + 2) = 02(n) .
In a like m a n n e r we obtain
flito
= 03 fa) + 02(n + 1)
= 0 o (n + 1) + 0 o (n + 3) ;
the second equation follows from (3.9) and (3.10).
Since all
0.(n)
m a y be
e x p r e s s e d in t e r m s of 0Q(YL) it will suffice to d e t e r m i n e the g e n e r a t i n g function for
0o(n)
alone.
Now by (3.8)
S2(2n5 4j) = (
_r | (mod 2)
(j = 2n - 3r - 3) .
F r o m this it follows that

S 2 (2n, 4j) =
(mod 2)
unless
j = r + 1
(mod 2) .
Hence if we l e t
r = 2r ? + s 9
j - 1 = 2j ? + s (s = 0,1)
then
S2(2n3 4j) = j rf j
and t h e r e f o r e
(mod 2) (jf = n - 3r ? - 2s - 2) ,
362
(3.11)
00(2n)
= e2(n) + 0 3 (n - 1)
= 0 o (n + 2) +6>0(n) .
Similarlyj s i n c e
_r x J (mod 2) (j = 2n - 3r - 2) ,
S 2 (2n + 1), 4j) = /

we have
S 2 (2n + 1 ,4j) = 0
(mod 2)
unless
r = j = 1 (mod 2)
Letting
r = 2r T + 1,
j - = 2jT + 1
we get
S2(2n+l,4j)
|rfj
(mod 2)
(jT = n - 3r - 3) .
Therefore
(3.12)
0 o (2n + 1) - 0 3 (n) = 0o(n + 1) .
If we l e t
<o(n) = 0 o (n + 4)
w e obtain f r o m (3.11) and (3.12) that
o>(2n) = o>(n) + o>(n - 2)
[Nov,
1967]
363
and
o>'(2n + 1) = &)(n - 1) .
Since 0 O (D = 80(2)
= 0O(3) = 0,
we have o>(n) = 0 for
equations for co(n) a r e valid for all n = 0 , 1 , 2 ? 8 .
o>(n)xn = J2
n=o
and t h e s e
co(2n + i)x :2n+i
^(2n)x2n + ^
n=o
n < 0,
Hence we have
n =o
co(n)x 2n + J^
n=o
w(n
"
2)x2n
w(n - 1) x 2n+i
+ ^
n=o
n=o
oo
(1 + x 3 + x 4 ) V * co(n)x;2n
n=o
n a + x3*2 +x 2 n + 2 ) ,
n=o
and the t h e o r e m i s proved*
F r o m t h i s g e n e r a t i n g function we s e e that o>(n) a l s o denotes the n u m b e r
of p a r t i t i o n s
n = n 0 + ni 2 + n 2 . 2 2 + n 3 2 3 + 40
(n. = 0, 3,4)
THE CASE p = 3
We s h a l l now c o n s i d e r the above p r o b l e m for the p r i m e
p = 3e
Since
t h e w o r k i s s i m i l a r to that of Section 3, many of the d e t a i l s will b e omitted,,

F r o m (2.4) we have
(4.1)
S 2 (n + 9, j) = 2S 2 (n + 3 5 j) + 2S 2 (n + 1, j) + S2(n3 j - 9)
T h e r e f o r e letting
(mod 3) .
364
(4.2)
S n (x) -
n
s2(n,j)x3
j=0
[Nov.
w e have
S
(x) = 2S
<x) + 2S
(x) + x 9 S (x)
n+9
n+3
n+i
n
(4.3)
(mod 3)
Let ai, a2, , a 9 b e t h e r o o t s of t h e equation

y 9 + y 3 + y - X9 = 0
in F [ y ] ,
where F = GF(3,x).
Then if
<b (x) = \ ^ a .
we s e e that
(4.4)
<f>Q(x) - <^(x) = . . .
= </>7(x) -
0, 0 8 (x) = 1 .
Moreover
<*> ^ (x) = x9</> (x) - <f> MM
^n+9
^n
n+l
(4.5)
-< ^ ( x )
n+3
and h e n c e
(4.6)
<J>9{x) = <t>10(x) = . . .
= 4>13(x) = </>15(x) = 0, <j>u(x) = <16(x) = - 1 .
If we let
f0(x) = S0(x) + S2(x) + S8(x)
fi(x) (4.7)
f2(x)
Si(x) + S7(x)
= S0(x) + S6(x)
f.(x) = S 8 j(x)
J
(j = 3, 4, . . . , 8)
1967]
365
and
Sn(x) = f j < X ) V j ( x )
(4.8)
it is clear from (4.3), (4.4), , (4.8) that

(4.9)
Sn(x) = SQ(X) (mod 3) (n = 0,1, 2, ) .

As in Section 3 we see that
k
n=o
n=o 6k+8+r=n
\fi\f_-n h x h
2J+h=r * ' * '
and hence
,4.10,
* - <-D+t^)
(n.
e k
.,.
s j
)^*'t).
By expanding (4.8), comparing coefficients and combining terms we have,

for instance, from (4.2), (4.9), and (4.10) that
S2(n + 9, 9h + 9) = J ] (-l) n + k lk)[l)
(mod 3)
S2(n+8, 9h+8) = J ] (-l) n + k (^j(^)
(mod 3) ,
and
but
S 2 (n+8, 9h + 6)
(-Dn+kjQ(i) ^ j ' l ) ^
))
<d3> >

366
Nov 1967
where the summations are over all nonnegative integers j and k such that
h = n - 6k - 2j.
The numbers
S2(n, 9h + j) for j = 0,1,- , 5 are more
compile at ed.
At this point the method employed in Section 3 seems to fail.
As was
mentioned in Section 1, the apparent difficulty in this case is the fact that the
recurrence (4.1) is a four-term recurrence.
If we consider the generalized
Stirling number S3(n, r) and the prime p = 2 we again get a four-term recurrence; the development of the problem in this case is very similar to our work
in the present section.
TABLE
Generalized Stirling Numbers of the Second Kind S2(n, r)
4 -
n ^v
1
15
32
12
110
20
52
175
203
1012
945
280
30
877
6230
8092
3465
595
42
4140
40819
70756
40992
10010
1120
56
REFERENCES
1. H. W, Becker and John Riordan, ' f The Arithmetic of Bell and Stirling Numb e r s , M American Journal of Mathematics, VoL 70 (1948), pp. 385-394.
2. E. T. Bell, "Generalized Stirling Transforms of Sequences, M American
Journal of Mathematics,,, VoL 61 (1939), pp. 89-101.
3.
L Carlitz, "Single Variable Bell Polynomials, n Collectanea Mathematica,

VoL 14 (1962), pp. 13-25.
4.
L, Carlitz, "Some Partition Problems Related to the Stirling Numbers of

the Second Kind, " Acta Arithmetica, VoL 10 (1965), pp. 409-422.
5. J. Riordan, Combinatorial Analysis, John Wiley, New York, 1958.

IDENTITIES FOR PRODUCTS OF FIBONACCI AND LUCAS NUiBERS

D. E. D A Y K I N and L. A . G . DRESEL
University of Reading, Reading, England
The Fibonacci numbers F
and Lucas numbers L

n
(1)
= (cP- - Pn)/(a
may be defined by
n
-p)
and
= a11 + /3n
where n is any integer,
a =-(1 + V) and f}= -|(1 - Vo), so that
(2)
= V5
a -p
and
a@= -1 .
Recently Brother Alfred Brousseau asked for generalizations of the

identity
F2k% = F ^ - 4 _
proved by I. D. Ruggles in [ 1 ] , and as a result V. E. Hoggatt, -D. Lind,
C. R. Wall [ 2 ] , and Sheryl B. Tadlock [3] between them gave seven further
identities. In this note we point out that these eight identities belong to the
family of sixteen identities given in Theorem 1 below. Furthermore, we show
that this theorem can be proved by a very simple method which can be used to
generate identities for arbitrary products of Fibonacci and Lucas numbers.
Theorem 1. If i, j , ss
i - j = 2t,
(3)
and t are integers such that i + j = 2s
and
then
(5F.F. or L.L.) = (5F2 or L2 ) (5F2 or L 2 ) (0 or 4(-l) t ) .

i j
-^3
where either term may be chosen at will in the first three brackets; in addition
i$ j may be chosen as being either both even or both odd. The choice of term
in the last bracket and the sign preceding it depend on the combination of the
previously mentioned four choices, but the choice of the first + sign depends
only on the parity of i and on the term chosen from the first bracket
If we
fix the two choices to be made on the left side of the identity, then the four
367
368
IDENTITIES FOR PRODUCTS
[Nov0
i d e n t i t i e s obtained by v a r y i n g the c h o i c e s m a d e on the r i g h t side a r e deducible

f r o m each o t h e r by application of the well-known identity
5F2
L2
4(.1}n
x
'
T h i s fact w a s u s e d by Sheryl B. Tadlock in [ 3 ] ,

To obtain f u r t h e r i d e n t i t i e s such a s those of T h e o r e m 1, we c o n s i d e r an
a r b i t r a r y p r o d u c t of Fibonacci and L u c a s n u m b e r s .
m, n, i 0 , il3' , j l 3 j 2 , "
In o t h e r w o r d s we l e t
be any i n t e g e r s with m, n > 0 and put
(4)
P = 5 m F . F . F . L. L. L.
1
i h
hm h h
Jn
(5)
Q = 5 m F . F. F.
L. L. L.
1
o 1i
^m h h
3n
Notice that P contains an even and Q an odd n u m b e r of Fibonacci n u m b e r s

F..
i
F i r s t we d i s c u s s P
= (a - p)2m-!
By (2) we have 5
f r o m (1) in (4) and expanding we s e e that P

t h e r e f o r e a s u m of 2
2m+n
"
so substituting
i s s y m m e t r i c in a,/3
t e r m s of the f o r m
(or p* + crfi
and i s
) , But by (1),
(2) we have
ap0q + a V
(6)
= (a(3)q(ap-q
fi^)
= (-l)qLp_q
H e n c e P can be e x p r e s s e d a s the difference of two s u m s of L u c a s n u m b e r s .

Now suppose that the s u m of the s u b s c r i p t s o c c u r r i n g in (4) i s even,
so
that we have
(7)
ij + i 2 + - + i 2 m + J! + J2
for s o m e i n t e g e r
s.
'e
Jn
2s
Then for each of the t e r m s
sion of (4) we have p + q = 2 s ,
in the e x p a n -
and so p - q i s also even.
Putting p - q =
2t in (6) and noting that

aP-q
+ ^P-q
azt
+ 2t =
(Q{ t
i g t ) 2 - + 2(a^)t
= (a* + /31)2 - 2(a/3)t
= SF 2 + 2 ( - l ) t
= L* - 2 ( - l ) t ,
1967
OF FIBONACCI AND LUCAS NUMBERS
369
we s e e that o u r g e n e r a l t e r m i s of the f o r m
(apj8q + aq/3P) = (-l)qL2t = (-l)q[5F2 + 2 ( - l ) t ]
= (-l)q[L2 - 2 ( - l ) t ] 6
"
T h u s we have shown that the p r o d u c t P given by (4) can b e e x p r e s s e d , in a

l a r g e n u m b e r of w a y s , a s a ssum
u m of t e r m s (5F^ o r
1?)
and t e r m s 2.
As
an e x a m p l e we give the identity
5F2iF2JL2kL2h = 5F2+j+k+h
L ^ ^
5F2+j_k+h
^_
f c
-5F? ._,, . - 5F? . , , - L? . T , - L? . , , ,

1-3+k+h
l-j+k-h
i-j-k+h
1-3-k-h
The r i g h t - h a n d side of this identity i s of c o u r s e only one of the 2 8 p o s s i b l e
e x p r e s s i o n s of this form* though many of t h e s e would involve a further
4C,
term
w h e r e C i s an i n t e g e r in the r a n g e -4 < C < 4S

Finally we d i s c u s s the p r o d u c t Q given b y (5),
expanding we s e e that Q i s a s u m of 2
2m+n
(aV(f - aqpP)/(a
Substituting f r o m (1) and
t e r m s of the f o r m
= (-l) q F p _ q ,
-p)
so that Q can b e e x p r e s s e d in t e r m s of Fibonacci n u m b e r s
F .
T h e r e i s no
i m m e d i a t e analogue for Q to the r e s u l t s obtained by (7) for P 0

ffl e
e a c h of i 0s ii,
p - q = 3r
? 3i>-fe> '*
However s if
is divisible Joy 3 ? then in our g e n e r a l t e r m we have
and
p-q
{adT
" @3T)/{a
' &
In t h i s way one can obtain Q a s a s u m of t e r m s
f5Fr
(-1)rFr]
[ 5F 3 + 3 ( - l ) F ] ,
a m p l e (after s o m e r e - a r r a n g i n g of t e r m s ) we have
F3iL3jL3k = 5[F3+j+k
(-l)kFi?+j_k + (-DJF3_.+k - M ) V i + j + k ]
for e x -
370
IDENTITIES FOR PRODUCTS

OF FIBONACCI AND LUCAS NUMBERS
Nov1967
REFERENCES
le
I. D. Ruggles,
So me Fibonacci Results Using Fibonacci-Type Sequences, tT
The Fibonacci Quarterly, Vol0 1, No. 2 (1963), p. 77.

2. Solution to Problem B-22, "Lucas Analogues," The Fibonacci Quarterly,
Vol. 2, No 1 (1964), p0 78.
3.
Sheryl B Tadlock, "Products of Odds," The Fibonacci Quarterly, Vol. 3,

No. 1 (1965), pp. 54-56.
*****
*
All subscription correspondence should b e addressed t o Brother Alfred
Brousseau, St. Mary's College, Calif. All checks ($1.00 per year) should be
made out to the Fibonacci Association or the Fibonacci Quarterly. Manuscripts
intended for publication in the Quarterly should be sent to V. E. Hoggatt, J r . ,
Mathematics Department* San Jose State College, San Jose, Calif. All manuscripts should be typed, double-spaced. Drawings should be made the same size
as they will appear in the Quarterly, and should be done in India ink on either
vellum or bond paper.
Authors should keep a copy of the manuscript sent to
the editors.
* * * *
To t h e E d i t o r :
The lemma proven by M. Bieknell and V- E. Hoggatt,Jr.
in 'Fibonacci Matrices and Lambda Functionsf,The Fibonacci
Quarterly, Vol. 1 (April 1963),page *+9 was essentially
established in my note 'Theorem on Determinants1, Mathematics Magazine Vol. 3*+ (September 1961), page 328. Namely,
r
If the difference of each pair of corresponding elements
of any two columns (rows) of a determinant are equal, then

any quantity may be added
to each element of the determin-
ant without changing its value.l

Charles W. Trigg
FIBONACCI FUNCTIONS
MERRITT ELMORE
San Jose City College, San Jose, C a l i f .
1.
INTRODUCTION
T h e r e i s a sequence of continuous functions of one v a r i a b l e having many

of the p r o p e r t i e s of the Fibonacci sequence of n u m b e r s , with s o m e intriguing
variations.
D e r i v a t i v e s and i n t e g r a l s of t h e s e functions a r e easily found,
l e a d to m o r e r e l a t i o n s involving Fibonacci n u m b e r s .
and
Other topics of c a l c u l u s
can undoubtedly be applied to t h e s e functions with v e r y useful and i n t e r e s t i n g

results.
Let a n , a 1s a 9 , e - * be a sequence such that a
0?
l5
>
,, = a
m+i
+a
Then
m-i
the power s e r i e s
00
a.x
y =
i=o
s a t i s f i e s the differential equation
y n - yf - y = o
(i)
whose solution i s ctea
+ C 2 e^ , w h e r e a and /5 a r e the r o o t s of u 2 - u - 1
= 0,
OL
= 5
If the sequence { a
and a,t = 1,
and
p =
} i s the Fibonacci sequence { F
then
a0 = 0
so that we get the boundary conditions x = 0, y = 0, y f = l e
T h i s y i e l d s (see [ 1 ] )
(2)
},
y = -
ax. _ j3x
-
V5
m
and
371
= -
z^
V5
372
FIBONACCI FUNCTIONS
On the other hand, if the sequence
then a0 = 2 and a 1 = 1,
2,
yT = 1,
(3)
{a
[Oct.
} i s the L u c a s sequence
{L
},
so that we get the boundary conditions x = 0, y =
yielding
y = e
+ e^
and
= a
+B
The writing of (1) in the form y!T = y 1 + y i s v e r y s u g g e s t i v e : the s u m

of the function and i t s f i r s t d e r i v a t i v e is the second d e r i v a t i v e . And g e n e r a l l y ,
if y i s any solution of (1), we s e e that
,., v
(la)
(m+l)
(m)
(m-l)
;
yv
.= y v ' + y v
This s u g g e s t s that we u s e the notation
f0(x) = ^
and so forth.
(4)
ax __ /3x
^ ,
\/5
fj(x) = fj(x),
v ;
, v
f3(x) = fj 3 '(x),
Thus
,
(x) = f0K
giving us the sequence of functions

(5)
f2(x) = f(x),
,
'(x) =
{f
m ax
^m jSx
^ ^5
(x)} with the p r o p e r t y that
, (x) = f (x) + f
(x)
m+r '
nr '
m-r ;
We shall r e f e r to t h e s e functions a s Fibonacci functions.

Likewise if l 0 (x) = eaX + e ^ ,
/rtX
(6)
(7)
v ;
l t (x) - lj(x),
l 2 (x) = r o T (x), e t c . , we have
i / \
i(ni)/ v
m ax , nm Bx
l m ( x ) = 10V ; (x) = a e
+ p eH
1
(x) = 1 (x) + 1
(x)
m+r '
nr '
m-r '
and t h e s e functions will be c a l l e d Lucas functions h e r e .
1967]
FIBONACCI FUNCTIONS
Evidently,
F 0 = f0(O) = 0,
Ft = it(0)
= 1,
m
(8)
= f
373
F 2 = f2(0) = 1,
F 3 = f3(0)
m
&
(0) =
\I5
with s i m i l a r r e s u l t s for L u c a s n u m b e r s .
Let us define
-k ax
n-k Bx
-c / \
oi e
- B er
f,(x) =
--c
V5
/m
(9)
^
i n
i / \
-k a x
- k x
l_ (X) = a e
+ p eH
With the u n d e r s t a n d i n g that fj

(x) is the k
antiderivative of f 0 (x), and
(-k);
V
s i m i l a r l y for 10
( k ) , we can easily verify that all the p r e c e d i n g r e s u l t s (2)
through (8) hold for
m a negative i n t e g e r .
2.
GRAPHS
E l e m e n t a r y notions of calculus r e g a r d i n g i n t e r c e p t s , s l o p e ,
symmetry,
extent, c r i t i c a l p o i n t s , points of inflection, e t c . , may be used in plotting the

g r a p h s of t h e s e functions.
F i g u r e 1 shows the g r a p h s of s o m e of the
f (x).
m
Note f i r s t of all that the
Fibonacci
functions
y - i n t e r c e p t of the c u r v e y = f
(x) is F
O b s e r v e a l s o that the functions with even s u b s c r i p t s a r e monotonic i n c r e a s i n g , and extend from
-oo to +oo both horizontally and v e r t i c a l l y .
functions with odd s u b s c r i p t s , however, a r e n e v e r negative (since (3 < 0),
The
and
each h a s one r e l a t i v e m i n i m u m .
In fact,
f2k-i( x )'
x
the z e r o of f2k( )>
w h e r e k i s any i n t e g e r , h a s i t s r e l a t i v e m i n i m u m at
which i s also the x at which
f 2 k-2( x )
nas
its
P o m t f
inflection.
Let us t h e r e f o r e call t h e s e points x2k>
(10)
L e t the m i n i m a of f 2 k-i(x)
f 2 k( x 2k)
That i s ,
= 0
be called y2k
Thus
x 2 k i s such that
[Oct.
FIBONACCI FUNCTIONS
374
GRAPHS OF THE FUNCTIONS f (x)

y= =
,.m_ax_ jn Bx
Fig. 1
(ID
Y2k =
2k-i( x 2k)
Some manipulation and calculation result in

4k
1
x?k = l o g
(12)
V5
-0.86k
2k
(13)
Y2k = [-Z
k
*
k
(0.65) ,
where
x fe
| x
2 k
Thus the minima of fg^.^x) occur at points evenly spaced along the negative x-axis and have values in geometric progression, which approach 0 as
x->.
Because
v
y
2k
P2
e
2k
1967
FIBONACCI FUNCTIONS
375
at t h e s e m i n i m u m p o i n t s , they lie on the graph of y = ^ e
(see the dotted-line
c u r v e in Fig 8 1).
Since
2k+i(X2k)
2k<X2k) + f2k-l(X2k)
Y2k = y2k
and s i n c e
2k+2(x2k)
2k+l( x 2k) + f 2k( x 2k) = Y2k
Y2k
we s e e that the g r a p h s of
2k-i( x K
2k+i( x ) 3
and
2k+2( x )
all i n t e r s e c t at (x 2 k , y 2 k ) .
Likewise
2k+3(x2k)
2k+2(x2k)
2k+i( x 2k)
^2k >
etc. ; and induction l e a d s to
(14)
f 2 k + j (x 2k ) = F j y 2 k = Fje
, or f m ( x 2 k ) = F m _ 2 k y 2 k = F m _ 2 k e
which i s a s p e c i a l i z a t i o n of the m o r e g e n e r a l r e l a t i o n t o be d e r i v e d in the next

section.
30
AN IMPORTANT IDENTITY
That the identity

F
, = F
,F + F F ,
m+n
m-i n
m n+l
for Fibonacci n u m b e r s h a s a c o u n t e r p a r t for the Fibonacci functions c a n be

i n v e s t i g a t e d by substituting into i t s r i g h t s i d e :
376
f
m-r
FIBONACCI FUNCTIONS
[Oct.
(x)f x(x) + f (x)f (x) =

n '
m ' rr '
of
m - i ax
n m - i Bx
e
- /3
e^
n #x
_n fix m c*x n m fix: n+l ax
Ji+l /5x
g e
-;3 e r
a e
- /3 e^
cy e
- /3
er
#
V5
V5
Multiplying and simplifying using
V5
V5
a/3 = - 1 , the t e r m s in
ax~\~Bx
p
vanish,
giving us
m + n - i . . , l*>* lax , . m + n - L , n?x 2fix

(1 + a )e
+ [3
(1 + /3*)e M
5
whence
1 + a2 = a V 5 , 1 + j32 =
-(3\/5
l e a d to
f
m-i
(x)f x(x) + f (x)f

= f A x(2x);
v
H (x)
' n '
n r ; n+i
'
m+n
We s e e then that the f o r m u l a is the s a m e except for the i m p o r t a n t change

in the a r g u m e n t .
We g e n e r a l i z e this by r e p e a t i n g a l m o s t exactly the s a m e
s t e p s , and obtain
(15)
x
'
fu + v) = f
(u)f v(v) + f (u)f
iv)
m+n v
'
m~r
n '
m
n+i v '
4.
APPLICATION OF (15) TO GRAPHS
Using the identity (15) with m = 2k,
n = 0,
u = x2ks
and v = t,
obtain
2k<x2k
t) = f2k-i(x 2 k)f 0 ( t )
^kt^k)^)
y2kfo(t) +
x,
(16)
f 2 k (x 2 k + t) = e
f 0 (t)
i t
i( )
we
1967]
FIBONACCI FUNCTIONS
377
Similarly
(17)
2k+i( x 2k + t) = e
f^t)
Hence each of the graphs can be obtained from the graph of either y =
f0(x) or y = f-^x), according to whether m is even or odd, by expanding it
xk
by the factor e
and translating it -x 2 ^ units to the left.
Since f0(x) and fj(x) in turn can be written as
X
(18)
f0(x) = 2 i s i n h ^ f
l
V5
fi(x)
, 2e 2
cosh | - r x + cosh
all of the graphs are distortions of hyperbolic sine or cosine curves through
multiplication by V e
5. INTEGRALS
From the definition of f (x), the antiderivative of f (x) is f
(x).
This leads to a wealth of problems involving Fibonacci numbers, two of which

follow.
(See Fig. 2)
376
FIBONACCI FUNCTIONS
[oct.
Let A = the area under the curve f2k+1(x) between x = x 2 k and x = 0,

and above the x-axis. Then
o
A
J
x
2k+i<X)dx
2k(x) J = f2k() ~ f2k(X2k) = F 2 k - 0 = F 2 k

x
2k
2k
More generally,
x
x
r2n
t
/
f , (x)dx = F
- F , e n
ftTe
/f
ni+r '
m-2k
m-2n
x
(19)
v
2k
Use of (15) and formulas for differentiation and integration lead to many others.
6. IDENTITIES
Many of the familiar identities for Fibonacci and Lucas numbers, besides
(15), also have their counterparts for these Fibonacci and Lucas functions.
Obtaining them is often merely a matter of substitution of
m ax
f
(x)
= *
nm Bx
- P e , 1 (X) =
Vs
m ax
flme^
into one side of the identity, and the use of such relations as a + /3 = 1, a/3
- 1 , a2 + 1 = orV5, etc.
Thus, for example, one easily obtains
(20)
v
'
(x) = f2 (x) + ( - l ) m e X
K f
m - r ' m+r '
mx '
H(x)f
(21)
v
'
1 (x) = f
(x) + f
Ax)
m
m-r
m+iv
(22)
5f^(x) = l^(x) + (-'l) m " 1 4e X
(23)
f_m(x) =
(-l) m + 1 e X f m (-x)
1967]
FIBONACCI FUNCTIONS
i
(24)
(x) +V5f
m
(X;
nr ' i
km
379
(kx) + V 5 f k m ( k x )
Note that the c o r r e s p o n d i n g identities for the Fibonacci and L u c a s n u m b e r s e m e r g e i m m e d i a t e l y when x = 0o

F r o m the f o r m u l a (15) a l r e a d y t r e a t e d c o m e such
familiar-appearing
identities a s
(25)
f2m.i(2x)
= ^ ( x )
+ f*m(x)
(26)
f3m-i(3x)
= ^ ( x )
+ 3 f m m i ( x ) f ^ ( x ) + f3m(x)
f 3 m (3x)
and
f 2 m (2x)
= 3f^_ H (x)f_(x) + 3 f _ _ ( x ) f ^ ( x )
m-i
m
m-i
m
fm(x)lm(x)
,
and
+ 2f^(x)
while a g e n e r a l i z a t i o n by induction on k and p y i e l d s
(27)
km+p
*> - () w.4
i=o
By using (15) to w r i t e
f
(u)f (v) -
(-1) f
(u)f
M (v)
- f ^ ^ ( u + v)
and
^ W ^ M
= (-1*2
m + 2 < u ) W v ) - f m + n + 3< u
+ v
and adding, one obtains

f
(u)f (v) = (-1)} 2

nr ' n '
Wu>Wv) " W ^
+v
>
R e p e a t i n g the p r o c e s s , and the u s e of induction l e a d to
(28)
m<
) y v ) = (-D
, (u)f , (v) - F f , , v(u + v)

m+r ! n+rN '
r m+n+r
>
380
[Oct.
FIBONACCI FUNCTIONS
Multiplication of (28) by f (u) gives
ÔUyv)
= (-D r {f m + r (u)[f m (u)f n + r (v)j
- Fr[fm(u)fm+n+r(u
v)]}
while the use of (28) to expand the expressions in the square brackets here
yields
2
f
^ ^ N (u + v)' + Fr2 12m+n+2r
_>_ ^v (2u +'J v)l
(-D 2r f m +j r. \ W/ n +a.2 r x(v); - 2Fr fm+r^ N (u)f
' m+n+2r
whence induction leads to
(29)
f^WfJv)
= (-D k r S(?)(-l) 1 F i r tJr^f n 4 k r ^ m ( i u
m x ' nN
+ v
.1=0
These two formulas are counterparts of two given by Halton [2J,
In
exactly the same way as he did, (29) can be used to develop a host of identities
by choosing particular values of m, n, k, and r
It is interesting to note that
(30)
\ /
F f (v - u)e U = ( - l ) r
;
v
m mv
'
lrc.A--v\
I n 4_ T ,\ /
-p\ /
is a ''sibling" of (28), having been derived by substitution using (4), as a counterpart of the same formula
F
F
- F F
F = (-l)rrF
m n
m+r n+r
r m+n+r
One is intrigued by the conjecture that they are both special cases of a more
general formula in which no capital F*s appear.
7.
Suppose | a
FIBONACCI FUNCTIONS OF TWO VARIABLES

I is replaced by jf
(xU in the series
1967J
FIBONACCI FUNCTIONS
oo
381
1=0
to give a function of two variables $(x, y).
(31)
*(x,y) = f0(x) + f^xjy + f2(x) | J + fs(x) f j
Differentiating term-by-term, we obtain
^ | ^
= fl(x)
= 0
>
+ f 2(x) y
fl(x)
f3(x)
f2(x) | f
f ^ ) 1^
f3(x) f f
...
f4(x) 4 f
We see that
d<t>(x, y)
dx
d<ft(x, y)
by
and likewise it can be verified that all the second partial derivatives are the
same, all the third partial derivatives are the same, e t c
Let us therefore
adopt the notation
* 0 (x,y) = *(x,y), <Mx,y) = * %bx* > =

A
(x
vx
a2<fo(x,y)
-by
%^.
d2<fr(x,y)
dx2
axdy
a2<fr(x,y)
dy2
so that
(32)
0 (x>y)
v m \ J/
= a^fry) = y f
r
/ 1 = 0j m+iv
(x)
;
= Yi
i!
+.(y)
/ 1 =j0 m + r J / i! *
.m a
382
FIBONACCI FUNCTIONS
Oct. 1967
where r and s are positive integers such that r + s = m.

(33)
4> m (x,0) = f m ( x ) ,
<Am(0,y) = f m ( y ) ,
Note that
and * m ( 0 , 0 ) =
Fm
Expand <f> (x, y) into a power s e r i e s in two variables at (0,0):
</>m(x,y) = </>m(o,o)
= F
xF
_ +
m+i
(x+
+F
m
m+i
Jy F
y)
^^(0,0)
d* m (o,o)
s^2
+ 2xy
bx2
x2F
,
m+i4
2!
+ F
(*
l!
m+2
+y2
ay2
J"
+ 2xyF
_^ + Jy2Fm+2
, J1 +
J
m+2
m+2
yli +
"^^"y-
<2Lj i
2]
m+s
3]
Thus
ame(x+y)
(34)
$m
(x y)
'
(x
8.
le
V E9 Hoggatt, J r .
__ ^m e /3(x+y)
y)
REFERENCES
" F i b o n a c c i N u m b e r s f r o m a Differential
Equation, T T
Fibonacci Q u a r t e r l y , Vol. 2, No8 3 , October 1964, page 176,

2a
John H, Halton, , "On a G e n e r a l Fibonacci I d e n t i t y , " Fibonacci Quarterly,

. V o l . 3, No. 1, F e b r u a r y 1965, pp. 31-43.
* *
FIBONACCI NUMBERS AND GENERALIZED BINOMIAL COEFFICIENTS

V . E. HOGGATT, JR.
San Jose State College, San Jose, California
DEDICATED TO THE MEMORY OF MARK FEINBERG

1.
INTRODUCTION
The first time most students meet the binomial coefficients is in the
expansion
(x + y)n = h) x n -y . n * o ,
j=o W .
where
(l) ~ ("n1) + (ill) * ::0 <
m < n
Consistent with the above definition is
(9\
{ }
\ =
n(n - 1) 2 9 1
[ml
m(m - 1) 2 1 (n - m)(n - m - 1) 2 1
nl
ml (n - m)!
where
n! = n(n - 1) 2 - 1 and 01 = 1 .
Given the first lines of Pascal's arithmetic triangle one can extend the table to
the next line by using directly definition (2) or the recurrence relation (1).
(Received O c t . , 1965)
383
384
FIBONACCI NUMBERS AND
[Nov.
We now can see just how the ordinary binomial coefficients I I are
related to the sequence of integers 1, 2, 3, , ks . Let us generalize this
observation using the Fibonacci sequence.
IL THE FIBONOMIAL COEFFICIENTS

Let the Fibonomial coefficients (which are a special case of the generalized binomial coefficients) be defined as
F F
FoFi
L i
n n-i
, 0 < m ^ n ,
(F F
- FoFiMF
F
. FoFT)
d l
L l
m m-l
m-n m-n-1
m
and
= 1 ,
where F
is the n
Fibonacci number 3 defined by

J
n
F
= F
n-iH
+ F
n-2S
1L
= F 2 - 1 .
*
We next seek a convenient recurrence relation, like (1) for the ordinary binomial coefficients j to get the next line from the first few lines of the
Fibonomial triangle 3 the generalization of which will come shortly.
To find two such recurrence relations we recall,the Q-matrix,
for which it is easily established by mathematical induction that
1967]
GENERALIZED BINOMIAL COEFFICIENTS
/F ^
[C
n-i /
T h e Laws of Exponents hold for the Q - m a t r i x so that
Qn = Q m Q n " m
Thus
n+l
F
v n
n-i/
^
m+l
IF
n-m+i
n-m
\ n-m
n-m-i J
^ F
_ + F F
F ^HF
+ F F
m+l n - m + i
m n-m
m+l n - m
m n-m
F F
, + F F
F F
+ F F
, m n-m+i
m-i n-m
m n-m
m-i nF
yielding, upon equating c o r r e s p o n d i n g e l e m e n t s ,
(A)
= F
F
+ F F
,
m+l n - m
m n-m-i
(upper right) ,
b
^
= F
F
, + F
F
m n-m+i
m-i n-m
(lower left)
n
F
(B)
T h e s e two identities will be v e r y handy in what follows,,

Define
C so that
F F 4
F ?2F* 1
n n-i
(F F
F2Fi)(F
F
m m-i
* l
n-m n-m-l
With C defined above, then
"FP71 = Fn
386
[Nov.

n - 1
n - 1
= F
C and
m - 1
n-m
= F
R e t u r n i n g now to identity (A),
+ F
m+i n - m
F
m
n-rn-i
w e m a y w r i t e for C f 0
F C = F
(F
C) + F
(F C)
n
m+l n - m
n-m-i
m
but s i n c e
n- 1
n - 1
F
= F C ,
n
n-m
C ,
and
= F
m - 1
C ,
w e have d e r i v e d
(D)
"n - 1
m+l
n - 1
n-m-l
m - 1
S i m i l a r l y , u s i n g identity (B), one c a n e s t a b l i s h
n"
(E)
n - 1"
m-i
+ F
n - 1
n-m+i m - 1
It is thus now e a s y to e s t a b l i s h by m a t h e m a t i c a l induction that if the

n^
Fibonomial coefficients I " I a r e i n t e g e r s for an i n t e g e r n (m = 0 , 1 , , n),
then they a r e i n t e g e r s for an i n t e g e r n + 1 (m = 0 , 1 , 2, , n + 1).
Recalling
1967]

L
= F
_ +
m+i
387
, ,
m-l
then adding (D) and (E) yields
n - 1
n - 1
+ L
n-mJ m - l
(3)
where L
i s the m
Lucas n u m b e r , a r e s u l t given in p r o b l e m H - 5 , Fibonacci
Q u a r t e r l y J o u r n a l , Feb , 1963, page 47
F r o m (3) it i s h a r d e r to show that
is an i n t e g e r .
With a slight change in notation, l e t us r e t u r n to identities (A) and (B),
(A)
(B)
F o r k > 0,
nf
n?
F
+ F
F
m f +i n f - m f
mf n ? - m ? - l
= F
F
+ F
F
mT n ? - m f + i
m ? - i n T -m T
let nf = nk and m f = mk,
(A?)
v
(B')
nk
= F
F
mk+l k(n-m)
nk
m k k(n~m)+i
Let u
= F ,.
n
nk
(A ) and (B ), that if
f
= F
then
+ F F
mk k(n-m)-i
mk-i
k(n-m)
Then one can show, in a m a n n e r s i m i l a r to above, using
U
(U
n n-l
_,
m m-l
UpUi
L
U o U i ) (U
L
n-m n-m-i
* U o U i )
x
0 <m <n
388
[Nov.
and
1 .
then
n - 1
m -Ik
n - 1
+ Fk ( n - m ) - i
" km+i
m - 1
-Ik
and
n - 1
n- 1
+ F
" km-1
Jk
k(n-m)+l
m - 1
-Ik
o r , adding t h e s e two,
n - 1
= L,
km
a g e n e r a l i z a t i o n of (3).
n - 1
+ L,
k(n-m)
We note h e r e each u
m - 1
-Ik
i s divisible by F,
the s a m e g e n e r a l i z e d b i n o m i a l coefficients from
IIL
= F . /F.
nk
k
THE FIBONOMIAL TRIANGLE
Pascal's arithmetic triangle
andwe T d get
I967]
389
1
1
1
1
1 4
1
1
4
6
10
10
()(") - Q
1
5
( . : . )
( : )
has been the subject of many studies and has always generated interest,
We
note here to get the next line we merely use the recurrence relation
(n) = ln" V (n'x)

\ ml
\ m I
\m- 1 / '
Here we point out two interpretations, one of which shows a direction for
Fibonacci generalization.
The usual first meeting with Pascal's triangle lies
in the binomial theorem expansion,
(x + y)n = t 0) *n""V
j=o W
However, of much interest to us is the difference equation interpretation. The

difference equation satisfied by n is
(n + 1) - n = 0
while the difference equation satisfied by n is

(n + 2) - 2(n + 1) + n = 0 .
390
[Nov.
For n2 the difference equation is
(n + 3)2 - 3(n + 2)2 + 3(n + I) 2 ~ n2
0 .
Certainly one notices the binomial coefficients with alternating signs appearing
here,
In fact,
/m + l\
<-DJ (
j ( (n + m + 1 - j ) m = 0
(
,
) j=o
It is this connection with the difference equations for the powers of the integers
that leads us naturally to the Fibonomial triangle.
Similar to the difference equation coefficients array for the powers of the
positive integers which results in Pascal's arithmetic triangle with alternating
signs, there is the Fibonomial triangle made up of the Fibonomial coefficients,
with doubly alternated signs* We first write down the Fibonomial triangle for
the first six levels,
1
1
1
1
1 2
1
1
1
5
8
15
40
1
3
15
60
1
5
40
1
8
th
The top line is the 0
row and the coefficients of the difference equation satk
st
isfied by F are the numbers in the (k + 1)
row. Of course, we can get
the next line of Fibonomial coefficients by using our recurrence relation (D),
1967]
391

n
"n - 1"
= F
m+i
"n - 1
+ F
n-m-l
0 < m < n
m - 1
We now r e w r i t e t h e F i b o n o m i a l t r i a n g l e with a p p r o p r i a t e s i g n s so that the r o w s

a r e p r o p e r l y signed to be the coefficients in the difference equations satisfied
Fo
F1
n
F3
n
1
F5
n
-1
-2
-3
-5
_8
-1
-1
-2
+1
-6
-15
-40
+3
+15
+60
+1
+5
+40
-1
-8
-1
T h u s , f r o m the above w e m a y w r i t e
F2
- 2F2
n+3
n+2
2F*
+ F2
n+i
n
and
F4
- 5F4
- 15F 4
+ 15F 4
+ 5F4 , n+5
n+4
n+3
n+2
n+l
F4
n
In J a r d e n f 1] and Hoggatt and Hillman [ 2 ] i s given the a u x i l i a r y polynomial

m
for the difference equation satisfied by F
,
m+i m + 1
E
h=o
( _ 1 } h(h+l)/2 x m + i - h
392
[Nov.
which shows that the sign pattern of doubly alternating signs persists.
For an
interesting related problem, see [5] and [6],
IV. THE GENERALIZED FIBONOMIAL TRIANGLE
If, instead of the Fibonacci Sequence, we consider the sequence
un = F nk.
(k = 13 2 , 3 , -
there results another triangular array for each k > 0 which all have integer
entries,, We illustrate with F ^ * The recurrence relation is
n - 1"
"n - 1"
+ F
= F 2m-1
J
2(m-n)+i
m - 1
and
~n~
n
n
0
- 1
The first few lines, with signs, are given below:
*2n :
An'F
F32n:
*2I1
-8
2n :
1
1
-3
-21
-55
+1
+b
+56
385
-21
-385
+1
+55
We are saying that the difference equation satisfied by F^ n is
-1
1967]
F
2n + 1 0 -
55F
fn+8
385F
2n+6 "
385F
m+4
55F
2n+2 - F | n
393
=
0 .
T h e a l g e b r a i c s i g n s of each t r i a n g l e (singly a l t e r n a t i n g or doubly alternating)

will b e d e t e r m i n e d by the second row by the a u x i l i a r y polynomial of F,
which
is
x2 ~ L.X + ( - i r .
F o r the g e n e r a l s e c o n d - o r d e r r e c u r r e n c e r e l a t i o n
uIO = p u 1 + q u
,
n+2
^ n+l
^ n
q ^ 0 ,
Z1
the a u x i l i a r y polynomial i s given in [ 2 ] to b e
m + 1
m-t-i
h=o
(-ir
(_
vh(h-i)/2 x m+i-h
where
m + 1
h
is the g e n e r a l i z e d binomial coefficient which in o u r c a s e b e c o m e s
m + 1
h
T h u s for all g e n e r a l i z e d Fibonomial t r i a n g l e s the g e n e r a l i z e d Fibonomial

efficients with a p p r o p r i a t e signs p r e s e n t a r r a y s which a r e the coefficients
coof
394
the difference equations satisfied by the powers,
[Nov.
^m ,
F,
of the Fibonacci
sequence.
V.
A GENERAL TECHNIQUE
Three simple pieces of information can be used to directly obtain the

auxiliary polynomials for F.
Lemma. If sequence u
is such that
(E2 + pE + q)u
and sequence v
= 0
is such that
(E2 + p f E + qT)v
s 0 ,
where
x2 + px + q = 0
and
x2 + p'x + qf = 0
have no common roots, then the sequence

w = Au + Bv
n
n
n
is such that
(E2 + pE + q)(E2 + p f E + qT)w
0 ,
for arbitrary constants A and B. See problem B-65, Fibonacci Quarterly

Journal, April, 1965, page 153.
The auxiliary polynomial for F , is
x2 - L k x + ( - l ) k .
The Binet Form for
1967]
F m = (am - pm)/(a
395
- fi)
and
L
= a
+B
where
a = (1 + V 5 ) / 2
and
= (1 - V g ) / 2
Suppose we wish to find the a u x i l i a r y polynomial a s s o c i a t e d with 3

T?3
x
2n
3
6n _ ^4no2n
a- p )
1 I 6n
/Q6n
5" ( F 6n "
3F
= - | { " - 3 ( ^ ) 2 n
( a =0
=
'a2n
^ n ^ & i _ am.
pm\\
2n)
Now, the a u x i l i a r y polynomial for = F 6 n
-3
and for -=- F 2 n
5(or - /5)
is
is
Thus the a u x i l i a r y polynomial a s s o c i a t e d with F 3
is
(x2 - 18x + l)(x 2 - 3x + 1) = x 4 - 21x 3 + 56x 2 - 21x + 1
say 5
396
[Nov.
We i l l u s t r a t e the technique with F 5

n
5n _ ^ n ^ n
-^sn^n __ xo^sn
"n \ - p )
= ^
5 ^ 4 x 1 __ ^511
25 (a - )8)
( F 5 n - 5(aj3) n F 3 n + 1 0 ( a j 8 ) ^ F n )
T h e a u x i l i a r y polynomials a r e
25 F 5n
x 2 - L5x - 1 = x2 - l l x - 1
'
i (-l)nF3n :
x 2 + L 3 x - 1 = x 2 + 4x - 1
^ F
:
25 n
x2 - L l X - 1 = x2 - x - 1
A
s o that the a u x i l i a r y polynomial for F 5 i s
(x2 - l l x - l)(x 2 + 4x - l)(x 2 - x - 1) = x 6 - 8x 5 - 40x 4 + 60x 3

+ 40x 2 - 8x - 1
which the r e a d e r should check with the a r r a y in Section IE with the Fibonomial
Triangle*
T h i s technique can thus b e u s e d to find the factored f o r m o r r e c u r r e n c e
m
r e l a t i o n s h i p for the auxiliary polynomials for any F , (m = 0, 1, 2, ) . S e e
[ 1] and [ 3] and p a r t i c u l a r l y [ 4 ] ,
VL. THE GENERAL SECOND-ORDER RECURRENCE
C o n s i d e r the s e q u e n c e
u0 = 0 ,
m = 1, and u
n ^ 0, Define t h e g e n e r a l i z e d b i n o m i a l coefficient
= pu
+ qu , f o r
1967]

U U
UoUi
L J
int.
n n-i
< > =
.
u__
2 ui)
L l -_
m
(u m u m - i UoUi) (un - m u n - m - i - - - " " *
with
397
i ^
^
-
i < ni < n - 1
Starting with
then
:
qg
n+i
""*
:
n
Rn = 1
n
\
"
II .*
qg
n-i/
nn > 1 ,
c a n b e e a s i l y e s t a b l i s h e d by m a t h e m a t i c a l induction. Thus we can e a s i l y obtain 3

a s in Section II, that
g
m+l g n - m
n ~
mgn-m+l
q g
m gn-m-1
qg
m-l
n-m
T h u s , w e can i m m e d i a t e l y w r i t e
(F)
v
'
in\
(m)
=g
&
<n"H
m+l (
+qg
HB
m f
|n "H
n - m - i | m - 1)
and
in)
|mf
H&
(n-ll
m-l ( m /
We can now examine s o m e s p e c i a l c a s e s .
&
(n -1)
n - m + l \ m - If
If p = 2 and q = - 1 , then g = n*
T h e above identities b e c o m e o r d i n a r y binomial coefficients f
U) --*-i> ( V V * - -
and adding yields
\ mj
\ m - 1/
S."-1.
398
[Nov.
T h u s we can conclude that the b i n o m i a l coefficients a r e i n t e g e r s and that the

p r o d u c t of any m consecutive p o s i t i v e i n t e g e r s i s divisible by
m-factorial.
Since the F i b o n o m i a l coefficients a r e i n t e g e r s , then the product of any m
con-
s e c u t i v e Fibonacci n u m b e r s (with p o s i t i v e s u b s c r i p t s ) is exactly divisible by the

p r o d u c t of the f i r s t
m Fibonacci n u m b e r s 0
If, on the o t h e r hand,

onacci p o l y n o m i a l s ,
p = x and q = 1,
then g (x) = f (x),
the F i b -
and the r o w s of the g e n e r a l i z e d binomial coefficients
a r r a y a r e indeed the coefficients, with doubly a l t e r n a t e d s i g n s , of the difference

equations satisfied by the p o w e r s of the F i b o n a c c i p o l y n o m i a l s ,
f0(x)
0,
fife)
= 1,
and f n + 2 (x) = xf n + 1 (x) + y x ) ,
g e n e r a l i z e d binomial coefficients
are
monic
n^
0o
which
are
The resulting
polynomials w i t h
integral
coefficients
Vn.
THE FIBONACCI POLYNOMIAL BINOMIAL COEFFICIENT TRIANGLE

T h e f i r s t few Fibonacci polynomials a r e
fi(x) = 1,
f 2(x) = x,
f3(x) = x 2 + 1,
f4(x) = x 3 + 2x, f5(x) = x 4 + 3x 2 + 1,
and the f i r s t few lines of the Fibonacci polynomial t r i a n g l e a r e

1
f (x) :
n
f 4 (x) :
n
f^(x) :
f3 (x)
1
1
1
1
-1
-x
-(x 2 + 1)
-(x 3 + 2x)
-1
-(x 2 + 1)
-(x 2 + l)(x 2 + 2)
+1
+(x 3 + 2x)
+1
8 e
{o}
{?}
{m}
-
{n-l}
w h e r e the double signs a r e to be attached to the i ^ as r e q u i r e d .
{n} 3
We a r e saying
+ 4 ( x ) - (x3 + 2x)f 3 i+3 (x) - (x2 + l)(x 2 + 2 ) ^ + 2 ( x )
+ (x3 + 2x)f 3 (x) + f 3 (x)
n+i
n
= 0
1967]
399
T h e next line can b e obtained by u s i n g r e c u r r e n c e r e l a t i o n (F),
< F)
{m} = W^VK-nw^: 1 !}'
where
M-H:}T h i s t r i a n g u l a r a r r a y c o l l a p s e s into the Fibonomial t r i a n g l e when x = L, F r o m

(F) it is e a s y to e s t a b l i s h by induction that <
i n t e g r a l coefficients.
VHL
? a r e monic polynomials with
F o r e v e r y i n t e g r a l x w e get an a r r a y of integers,,
THE CHEBYSHEV POLYNOMIALS O F THE SECOND KIND
T h e Chebyshev p o l y n o m i a l s of the second kind a r e

EL0(X) = 1,
ui(x) = 2x,
and
u n + 2 (x) = 2x u n + 1 (x) - u n (x)
If
g n (x) = u n - 1 W ,
then
g 0 (x) = 05
gi(x) = 1 ,
and we have the conditions for o u r P a s c a l t r i a n g l e r o w s to have singly a l t e r nating signs to r e f l e c t the difference equations for the p o w e r s of g (x).
g (x/2)
a l s o s a t i s f i e s t h i s , the F i b o n a c c i polynomials
and the
Since
Chebyshev
p o l y n o m i a l s yield all p o s s i b l e P a s c a l t r i a n g l e s with i n t e g r a l coefficients,,

IX.
THE FINAL DISCUSSION
In [ l ] and [ 2 ] it is given that the a u x i l i a r y p o l y n o m i a l a s s o c i a t e d with

the g e n e r a l s e c o n d - o r d e r r e c u r r e n c e
y , - py , + q y J
J
n+2
^Jn+i HJn
f o ,

400
Nov, 1967
is
(_q)h<h-1)/2xm+l-h
(_l)h
h=o
>
T h u s , if the c o l u m n s of P a s c a l ' s g e n e r a l i z e d binomial coefficient t r i a n g l e is

left justified with the f i r s t column on the left being the 0
tiplying the h
column by q
column then m u l -
yields a modified a r r a y whose coef-
ficients along each row (with singly a l t e r n a t i n g signs if Chebyshev r e l a t e d o r

Fibc
doubly a l t e r n a t i n g if Fibonacci
r e l a t e d ) a r e the coefficients of the difference
T.
m
equations satisfied by u
REFERENCES
le
Dov J a r d e n ,
R e c u r r i n g Sequences;
Riveon L e m a t e m a t i k a ,
Jerusalem,
2.
A. P . H i l l m a n a n d V . E. Hoggatt, " T h e C h a r a c t e r i s t i c Polynomial of t h e
I s r a e l , 1958, pp e 4 2 - 4 5 ,
G e n e r a l i z e d Shift M a t r i x , " F i b o n a c c i Q u a r t e r l y 3:2, April, 1965, pp. 9 1 94,
3.
T e r r e n c e A. B r e n n a n , " F i b o n a c c i P o w e r s and P a s c a l ' s
T r i a n g l e in a
M a t r i x , " Fibonacci Q u a r t e r l y 2:2, April, 1964, pp. 93-103.

4.
Stephen J e r b i c , p r o b l e m H - 6 3 ,
Fibonacci Quarterly
3:2,
A p r i l , 1965,
p . 116.
5.
V, E. Hoggatt, J r . , p r o b l e m H-76, F i b o n a c c i Q u a r t e r l y 3:4, Dec. , 1965,

p . 300.
6.
N. A. D r a i m and M a r j o r i e Bicknell, "Sums of n

Given Q u a d r a t i c Equation,
P o w e r s of Roots of a
F i b o n a c c i Q u a r t e r l y 4:2, April, 1966, pp. 170-
178.
-k Ur

5 4

Uploaded by

Copyright:

Available Formats

5 4

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

5 4

Uploaded by

Copyright:

Available Formats

FIBONACCI NUMBERS AND SOME PRIME RECIPROCALS

The s e r i e s of Fibonacci n u m b e r s h a s been shown to b e a r s o m e i n t e r e s t ing r e l a t i o n s h i p s to the r e c i p r o c a l s of c e r t a i n p r i m e n u m b e r s .

Maxey Brooke and C. R. Wall set up as P r o b l e m s B-14 (Fibonacci Q u a r t e r l y ,

w h e r e x, an i n t e g e r >2 9 i s the r a d i x in t e r m s of which the n u m b e r (x2 - x - 1)

Equation (3) is r e a d i l y proved by

FIBONACCI NUMBERS AND SOME PRIME RECIPROCALS

Note that x 2 - x - 1 m a y be c o m p o s i t e (e. g. , for x = 8, 13),

1/N = l / ( x 2 - x - 1) i s e x It is found that the 108-digit

shown that if the p e r i o d of 1/N

FIBONACCI NUMBERS AND SOME PRIME RECIPROCALS

Cay)n - (by)n]/(a - b)y

FIBONACCI NUMBERS AND SOME PRIME RECIPROCALS

Now consider the term

Clearly no factor of y will divide y2 + y - 1,

and since R is an integer, y ~ divides R. Thus

R is a number ending in N - 1 zeros when expressed in terms of radix y,

NOTICE TO ALL SUBSCRIBERS!!!

Unless the addressee specifically r e -

All subscription correspondence should be addressed to Brother A. Brousseau f

for publication in the Quarterly should be sent to Verner E. Hoggatt, Jr. ,

RESIDUES OF FIBONACCI-LIKE SEQUENCES

In the February, 1964, issue of the Fibonacci Quarterly, Brother U.

The first part will be to show

that every Fibonacci-like sequence, modulo any member of the sequence, is

Since any divisor of two neighboring

members of Fibonacci-like sequences divides every member of the sequence,

H. will denote the i

member of a general Fibonacci-like

= H. + H. , where H0 and Hj are arbitrary. The

set of integers will be denoted by I, the set of non-negative integers by P,

RESIDUES OF FIBONACCI-LIKE SEQUENCES

It is known that any n u m b e r m u s t eventually divide one of the Fibonacci

r e s u l t s and L e m m a 1, it i s not difficult to p r o v e L e m m a s 3 and 4.

L e m m a 5: F o r the n of L e m m a 3, and for all i n t e g e r s

The proof i s by induction on

A s s u m e that L e m m a 5 holds for i = k - 1 and

Hence, the formula i s c o r r e c t for all i E P .

extend the r e s u l t to include negative i n t e g e r s .

Then, if q G N and F_ = 0 (mod H

T h e proof i s once again by induction on q.

e x p r e s s i o n above b e c o m e s identical to L e m m a 1. A s s u m e that L e m m a 6 holds

RESIDUES OF FIBONACCI-LIKE SEQUENCES

Hence, L e m m a 6 is t r u e for all q E N.

T h e c a s e q = 0 is t r i v i a l , since then t = p and i = k.

we need c o n s i d e r only the c a s e t > 0 o r q E N. By L e m m a 6,

RESIDUES OF FIBONACCI-LIKE SEQUENCES

divides H., we can take k = m or k = m - n.

Since z e r o can o c c u r a s a r e m a i n d e r in any F i b o n a c c i - l i k e sequence and

since T h e o r e m 1, applied to Fibonacci n u m b e r s , l e a d s to the t h e o r e m proved

are either zero or

equal in absolute value to m e m b e r s of the original sequence.

The f i r s t o b s e r v a t i o n to b e m a d e about F i b o n a c c i - l i k e s e q u e n c e s i s that

RESIDUES OF FIBONACCI-LIKE TSEQUENCES

far to the right and to the left,

the absolute v a l u e s i n c r e a s e without l i m i t .

Hence, we need only e x a m i n e a s m a l l section of the whole sequence to d e t e r m i n e if it h a s the d e s i r e d p r o p e r t y .

c a u s e of t h e d i v e r g e n c e of the sequence in both d i r e c t i o n s , t h e r e can be only a

p o s s i b l e r e m a i n d e r equal in absolute value to a m e m b e r of the original sequence

the only such r e m a i n d e r for H2