LIBRARY

THE FIBONACCI QUARTERLY1'

^ : ^ A l $ Dp'T

THE OFFICIAL JOURNAL OF

THE FIBONACCI ASSOCIATION

VOLUME 4

47

Mi

\%\

NUMBER 1

PART I-ADVANCED
SOME CONVERGENT RECURSIVE SEQUENCES, HOMEOMORPHIC
IDENTITIES, AND INDUCTIVELY DEFINED COMPLEMENTARY
SEQUENCES

John C. Holladay

Raymond E. Whitney

37

L. Caditz

43

. J.C. Ahuja and S.W. Nash

49

EXTENSIONS OF RECURRENCE RELATIONS

SOME ORTHOGONAL POLYNOMIALS RELATED TO FIBONACCI NUMBERS
A NOTE ON ORTHOGONAL POLYNOMIALS

ADVANCED PROBLEMS AND SOLUTIONS

A FIBONACCI CROSSWORD PUZZLE

Edited

by VernerE.

Hoggait,

Jr.

56

H.W. Gould

59

Edgar I. Emerson

63

'
PART II - ELEMENTARY

ON THE INTEGER SOLUTION OF THE EQUATION 5x2 6x + 1 = y 2

AND SOME RELATED OBSERVATIONS
STAR GEOMETRY

. . . . . .

R.S. Beard

70

PROPERTIES OF THE POLYNOMIALS DEFINED BY MORGAN-VOYCE.

M.N.S. Swamy

73

PERFECT NUMBER "ENDINGS"

J.AM. Hunter

82

A DIVISIBILITY PROPERTY OF FIBONACCI NUMBERS

A LETTER TO THE EDITOR

Lenard

Enrico T. Federighi and Ronald G. Roll

LETTER TO THE EDITOR

FEBRUARY

Edited

83
85

Weinstein

88

Gerard R. Deily

89

by A.P. Hillman

90

Lenard

A LOGARITHMIC FORMULA FOR FIBONACCI NUMBERS

ELEMENTARY PROBLEMS AND SOLUTIONS

Weinstein

196G

THE FIBONACCI QUARTERLY

OFFICIAL ORGAN OF
THE FIBONACCI ASSOCIATION
A JOURNAL DEVOTED TO THE STUDY OF INTEGERS WITH SPECIAL PROPERTIES
EDITORIAL BOARD

B r o t h e r U. Alfred
He L. Alder
S. L. Basin
M a r j o r i e Bicknell
John L. Brown, J r .
L. C a r l i t z
H. W. Gould

A. P . Hillman
V, E. Hoggatt, J r .
Donald E. Knuth
C T. Long
Leo M o s e r
L D. Ruggles
D. E. Thoro

WITH THE COOPERATION OF

P . M. Anselone
C h a r l e s H. King
Terry Brennan
L. H. Lange
Maxey Brooke
Douglas Lind
Paul F . Byrd
J a m e s Maxwell
Calvin D. C r a b i l l
S i s t e r M. de Sales McNabb
Ho W. Eves
C. D. Olds
John H. Halton
D. W. Robinson
R i c h a r d A. Hayes
A z r i e l Rosenfeld
Ao F . H o r a d a m
M. N. S. Swamy
Dov J a r d e n
John E . Vinson
Stephen J e r b i c
Lloyd Walker
R. P . Kelisky
C h a r l e s R. Wall
The California M a t h e m a t i c s Council

All s u b s c r i p t i o n c o r r e s p o n d e n c e should be a d d r e s s e d to B r o t h e r U.
Alfred, St. M a r y ' s College, Calif. All checks ($4.00 p e r y e a r ) should
be m a d e out to the Fibonacci A s s o c i a t i o n or the Fibonacci Q u a r t e r l y .
M a n u s c r i p t s intended for publication in the Q u a r t e r l y should be sent
to V e r n e r E . Hoggatt, J r . , M a t h e m a t i c s D e p a r t m e n t , San J o s e State
College, San J o s e , Calif. All m a n u s c r i p t s should be typed, doublespaced, Drawings should be m a d e the s a m e size a s they will a p p e a r
in the Q u a r t e r l y , and should be done in India ink on e i t h e r vellum or
bond p a p e r . A u t h o r s should keep a copy of the m a n u s c r i p t sent to the
editors.
The Q u a r t e r l y is e n t e r e d a s t h i r d c l a s s m a i l at the St. M a r y ' s College
P o s t Office, California, as an official publication of the Fibonacci
Association.

SOME CONVERGENT RECURSIVE SEQUENCES, HOMEOMORPHSC IDENTITIES,

AND INDUCTIVELY DEFINED COMPLEMENTARY SEQUENCES
John C. Holladay
Institute for Defense Analyses
Washington, D.C.

I.

Consider the following r e c u r s i v e formula for generating s e -

quences, where

A is a given positive n u m b e r :

(1.1)
x
=x
- Ax
'
n+1
n-1
n
It is well known that any sequence so g e n e r a t e d is of the form
(1. 2)

where

C,

and C ?

= C , R ^ + C 0 R^ ,
n
1 1
2 2
a r e c o n s t a n t s , and R and R

a r e the roots of

x 2 = 1 - Ax .

(1.3)
Let R,

be the positive root which is l e s s than one, and let R_

the root that is l e s s than m i n u s one.

be

Then this sequence c o n v e r g e s

if and only if C ? = 0; and when it does converge, it c o n v e r g e s to z e r o .

So given two positive n u m b e r s
if and only if x / x
R

=R .

x ,

and x n , this sequence c o n v e r g e s

F u r t h e r m o r e , if

A is an i n t e g e r , then

is i r r a t i o n a l .
It should be noted that sequences g e n e r a t e d by a r e c u r s i v e f o r m -

ula such as (1. 1) m a y be continued in the opposite d i r e c t i o n .

If

A= 1,

then the r e c u r s i v e formula obtained for going in the opposite d i r e c tion is the formula used for generating Fibonacci n u m b e r s .
Let P be a h o m e o m o r p h i s m of |?0,oc ) onto itself.

In other

w o r d s , P(0) = 0 and P is a continuous, unbounded, s t r i c t l y i n c r e a s ing function of non-negative r e a l n u m b e r s .

Then the question a r i s e s

as to the convergence of the sequence s t a r t i n g from two positive n u m bers x ,

and x n

and g e n e r a t e d by the formula

(1.4).

x ,. = x 1 - P(x ) .
n+i
n-1
ir
Although the p r o p e r t i e s to be d i s c u s s e d will depend on the n a t u r e
of P on (_0,oo) only, to facilitate the d i s c u s s i o n it will be a s s u m e d
that P is a h o m e o m o r p h i s m of the e n t i r e r e a l line.
1

But for this

SOME CONVERGENT RECURSIVE SEQUENCES,

Feb.

exception, the word homeomorphism as used in this paper will refer to

a homeomorphism of pO, oo)

onto itself.

Given two horneomorphisms

h and g, their sum and products are defined as those horneomorphisms

respectively satisfying
(1.5)

(h + g)(t) = h(t) + g(t)

The inverse

(hg)(t) = h [g(t)]

and

(gh)(t) = g[h(t)]

for all t > 0.

of h is that homeomorphism such that

hh" 1 = h _ 1 h = I ,

(1. 6)
where

I is the identity homeomorphism.

The relation h < g is de-

fined to mean that h(t) < g(t) for all t > 0. Similarly,

h < g means

that h(t) < g(t) for ail t > 0. Note that h < g if and only if h~
and that h <_ g if and only if h

> g

Given two homeomorphisms

homeomorphism such that (hljg)(t)
h(t)

and

g(t) for all

t > 0.

> g~

and

g,

define

h(Jg

as

that

is the largest of the two numbers

Define

hf)g

as that homeomorphism

such that
(1.7)

hHg + h U g - h + g .

In other words, hflg

is the minimum of g and h.

Note that for any

h and g,
(1.8)

hHg = gHh < h < hUg = gUh .

Also note that for any homeomorphism

h,

hDh' 1 < I < hUh"1

(1. 9)

The remainder of this first section of this paper is devoted to

proving the following five interrelated theorems:
Theorem 1:

There exists a unique homeomorphism

that
(1.10)

h =P + h

such

1966

HOMEOMORPHIC IDENTITIES, AND INDUCTIVELY

3
DEFINED COMPLEMENTARY SEQUENCES
T h e o r e m 2:
Let h and g be two h o m e o m o r p h i s m s s u c h t h a t
h = P + g"1

( 1 . 11)

and

g= P + h_1
Then

h = g = t h e h o m e o m o r p h i s m of T h e o r e m 1*
T h e o r e m 3:

Let

g,

be any h o m e o m o r p h i s m .

q u e n c e of h o m e o m o r p h i s m s

| g

g _,_ = p + g " 1
&
n+1
n

(1.12)
x
'

c o n v e r g e s u n i f o r m l y on e v e r y b o u n d e d s u b s e t of
morphism

[ 0 , oo) to t h e h o m e o -

of T h e o r e m 1.

T h e o r e m 4:

The s e q u e n c e g e n e r a t e d by (1.4) f r o m two p o s i -

tive n u m b e r s x , and
h

Then the s e -

I defined inductively by

c o n v e r g e s if a n d o n l y if

is the h o m e o m o r p h i s m

of T h e o r e m

1.

= h ( x ), w h e r e

Also, whenever this s e -

q u e n c e c o n v e r g e s , it c o n v e r g e s to z e r o .
If

h(xn) > x

even subscripts

, t h e n a i l of t h e e l e m e n t s

are positive,

of t h e s e q u e n c e w i t h

b u t a l l b u t a f i n i t e n u m b e r of t h e e l e -

m e n t s w i t h odd s u b s c r i p t s a r e n e g a t i v e .
If

h(x ) < x

, t h e n a l l of t h e odd s u b s c r i p t e d e l e m e n t s a r e

p o s i t i v e a n d a l l b u t a f i n i t e n u m b e r of t h e e v e n s u b s c r i p t e d

elements

are negative.
T h e o r e m 5:

If

m a p s i n t e g e r s into i n t e g e r s , then the

of

T h e o r e m 1 will not m a p any positive i n t e g e r into an i n t e g e r .

Proofs:
induction, for

Let
n

h1

be a h o m e o m o r p h i s m such that

a positive integer,

( 1 . 13)
v

Then

define

,. = P + h " 1
n+1
n

n > 1 implies that

h, < P < P + h " 1 . = h
.
1
n-1
n

(1.14)
B y i n d u c t i o n on

m , if

0 < m < n

and

is even,

then

h.. < P .

By

SOME CONVERGENT RECURSIVE SEQUENCES,

Feb.

= P + h " 1 . > P + h " 1 , = h .

m
m-1
n-1
n
and s i m i l a r l y , if m > 3 is odd, then
(1.15)

= P + h"' 1 , < P + 1 T 1 . 'h

.
m
m-1
n-1
n
So the i n c r e a s i n g sequence of h o m e o m o r p h i s m s With odd s u b s c r i p t s
(1. 16)

(1. 17)

h, < h . <: h_ < h_ < h n <

I

is bounded from above by the decreasing sequence

(1.18)

h2> h4> h6> h 8 > > 1 0 >

Also, the d e c r e a s i n g sequence

h " 1 > h ' 1 > h~ X > h~*>

(1.19)

---

is bounded from below by the i n c r e a s i n g sequence

h"1 < h"1 < h"1 < hg1 < - -

(1.20)

T h e r e f o r e , these four s e q u e n c e s m u s t be pointwise convergent.

Let us now prove that the h o m e o m o r p h i s m s

for

n > 1 are

uniformly equicontinuous on e v e r y bounded subset of [ 0 , oo).

r > 0,

[0, r ]

such that

is c o m p a c t and so for any t > 0, t h e r e exists' a 8 > 0

0 <P^)

Let t, , t ?
(1. 21)

< P(tu) < r

(1.22)

and

P(t^) - P ( t . ) < 8 imply

and n > 1 be such that

0 < h (t, ) < h (t v ) < r
*-

1'

h ( t j - h (t.)
. n 2
n 1

2' -

and
.

<8.

Then
(1.23)

F o r any

0 < P ( t x ) < P(t2) < P(t2) + \ 5 1 ( t z ) = hn(t2)

<r

that

1966

HOMEOMORPHIC IDENTITIES, AND INDUCTIVELY

DEFINED COMPLEMENTARY SEQUENCES

Also
(1.24)

P(t2) - P(tx)

Therefore

<P(t2)-P(t1)+h"|1(t2),-h^(t1)

t. < t_ < t. + fe .
1

Consequently the
x

are

uniformly
J

equicontinuous on any set |~0, r j .

Since the pointwise convergent sequences (1 0 1 9) and (1.20) a r e
uniformly equicontinuous on e v e r y bounded set | 0, r |,
v e r g e uniformly to continuous functions.

they con-

However, s e q u e n c e s ( 1 . 17)

and (1.18) a r e r e l a t e d to ( 1 . 19) and ( 1 . 20) by ( 1 . 1 3 ) .

Therefore,

s e q u e n c e s a l s o converge uniformly to continuous functions.

these

But if a

s e r i e s of h o m e o m o r p h i s m s and t h e i r i n v e r s e s both converge to continuous functions,

morphisms.

then t h e s e continuous functions m u s t be h o m e o -

T h e r e f o r e , t h e r e exist h o m e o m o r p h i s m s h and g such

t h a t h , g, h" 1 . and g " 1 ' a r e the limits of ( 1 . 17), ( 1 . 18), (1.19), and
(1.20) r e s p e c t i v e l y .

Also, (1.13) i m p l i e s (1,11).

Let h and g be any p a i r of h o m e o m o r p h i s m s which satisfy

(1. 11). That at l e a s t one such p a i r e x i s t s has just been p r o v e n .
xn

be a positive r e a l n u m b e r and let x . = h(x_).

Let

Then let the s e -

quence
X , ,

\l , c.0)

X..,

X_ ,

X_,

be defined inductively by (1.4) c

that for

X-2,

X ,,

-'

Then it will be shown by induction

n2 0

(1.26)

x2n= (h^g-1)

(l.?7)

x ^ j

=h(h

(x 0 )

and

-1 - l . n
g ) (x 0 )

. Equations (1.26) and (1.27) a r e obviously satisfied for

since

(h

is defined as

n =0

I. If they a r e t r u e for a given ,n, then

6
(1

SOME CONVERGENT RECURSIVE SEQUENCES,

-28)

2(n+1)-1

=X

2n-l "

P(x

Feb.

2n>

^Mh^g-V-Pth^g"1)11]^)
= (h-PXh^g-1)
-1 -1 -1
= g > lg ')

(x 0 )

(x Q )

-Hh'g-1)

< x o>

and a l s o
(1 29)

'

2(n+l)=X2n- ^ ( n - H ) - ! *
-1 -1
l

= (h

-1*-1
(x 0 ) - Ph(h

-l

-l

- 1 - 1l
g )

(x 0 )

n+1

= (g-P)h(h n +V1 )
= (h

n+1

(xQ)

(x Q ) .

However, (1.11) i m p l i e s that

h " ^ " " 1 < h ' ^ P + g" 1 ) = h" X h = I .-

(1.30)
T h e r e f o r e , (h

-1 -1 n
g ) (x n ) c o n v e r g e s to z e r o as n tends to infinity.

Consequently, (1.25) a l s o c o n v e r g e s to z e r o .
Let x , y , x

and y

be any positive n u m b e r s such that

x 0 = y 0 and y . - x , = $ > 0. Define the sequence j x

by (1.4) and likewise the sequence j.y } inductively by

<x-31>

yn+i = yn-i -

<V

J inductively

Equations (1.4) and (1. 31) yield

(1.32)

Yl

- x x = y_ x - P(y Q ) - x ^ + P(x Q ) = y ^ - x_ x = .

Then by induction, for

n > 0,

1966

HOMEOMORPHIC IDENTITIES, AND INDUCTIVELY

DEFINED COMPLEMENTARY SEQUENCES
y~
- x_
7
2n
2n

(1.33)
/

= y
- x0
- P (wy 0
, ) + P(x
.
'2n-2
2n~2
2n-l
2n-1
< y7

2n-2

'- x

< 0
2n-2

and
(1.34)

2n+l "

2n+1

= y70
, - x9
, - P (wy , ; ) + P (v x - )
2n-l
2n-l
2n
2n'
>

2 n - l " X 2 n - 1 > B

If x , = h (v x ~ ) , t h e n t h e
'-1
0'
( 1 . 35)

y~
'2n

lim

t e r m s d e c r e a s e to l e s s t h a n

x0 = 0
2n

n ~ * oo
but the

v^
,,
J
2n+l

t e r m s a r e bounded above

( 1 . 36)

lim

Conversely,
the

if

x_ J_1 + 8 = e .
2n+l

n oo
= h(yn), then the

x~

t e r m s s t a y above z e r o but

x~ ,, t e r m s d e c r e a s e b e l o w - P .
2n+l
In v i e w of t h e s y m m e t r i c r o l e s of

and

g in (1.11), it m a y

b e s i m i l a r l y s h o w n t h a t t h e s e q u e n c e d e f i n e d b y ( 1 . 4 ) c o n v e r g e s if
a n d o n l y if x
thatwhenever

= g(xn).
h

and

Since t h i s i s t r u e for a n y

> 0, i t f o l l o w s

s a t i s f y ( 1 . 11) t h e y a r e t h e s a m e .

Therefore,

e x c e p t f o r t h e u n i q u e n e s s of h , T h e o r e m s 1 a n d 2 h a v e b e e n p r o v e n ,
B u t t h e u n i q u e n e s s of

is a l s o s i m i l a r l y p r o v e n s i n c e it m a y l i k e -

w i s e b e s h o w n t h a t if
A

(1.37)

_i

h = P + h
A

for

some homeomorphism

A
= h

_l

h,

t h e n (1 25) c o n v e r g e s if a n d o n l y if

( o)
L e t g, b e a n y h o m e o m o r p h i s m
tested, and choose
(1.38)

for w h i c h T h e o r e m 3 is to be

\ = gl ng 2 np .

SOME CONVERGENT RECURSIVE SEQUENCES,

Then h

< g

implies by induction that for

Feb.

n > 0,

g 0 = P + g^ 1 i < P + h^ 1 i = ho
6
Zn
2n-l ~
2n-l
2n

(1. 39)
x
'

and
(1. 40)
v
'

g, ^
2n+l

to

^P +g ^ P + L ^ L
1
s
2n
2n
2n+l

Therefore, the sequence

/g
. , 1 is bounded from below by<h
.. I
0
4
y
'
^ 2nn + l /
/
,
\ 2x1+1/
and <g_ > is bounded from above by < h~ > . However, h. <5 g^ simf2n/
M 2n/
1*
2 ,
i l a r l y i m p l i e s that )g?
. I is bounded from above by <h
> and <g
\
is bounded from below by Jh~ n 1 . h. < P implies that both { h_ ._>
r
' \ 2n-l/
1 V 2n+lf
and /h~ l converge uniformly to h on every bounded subset of i~0, oo).
Zn

f ( )

Therefore, /g V also converges uniformly to h on every bounded subr

' n '
( "I \
set of |_0,oo). Identity (1.12) then implies that <|g
> also converges
uniformly on every such bounded subset.
To prove Theorem 5, note that if P maps integers into integers
and that if x

and x .

are positive integers such that h(x ) = x

then the sequence defined inductively by (1. 4) must consist of integers.

But
(1.41)

x^ = (h

-1
L
)

(x )

implies a slow convergence of < x

for

n > 0 .

I which contradicts the assertion

that the elements of the sequence a r e integers.

II.
(2. 1)
x
'

Sequences defined by
x , . = P(x ) - x
n+1
n
n-1

a r e considered in this section of the paper.

(2. 2)

The homeomorphic identity

h + h" 1 = P

associated with (2.1) is also discussed h e r e .

In order to establish

theorems concerning the unique convergence of sequences generated by

(2.1) and concerning the existence of solutions to (2.2),
properties of P will need to be assumed.

additional

1966

HOMEOMORPHIC .IDENTITIES, AND INDUCTIVELY

DEFINED COMPLEMENTARY SEQUENCES
L e m m a 1:
Let h and g be any two h o m e o m o r p h i s m s .

9
Then

(hug)"1 = h - 1 n g " 1

(2.3)
and

(hHg)" 1 = h - ^ u g " 1

(2.4)
Proof;
implies

(h

To prove (2. 3), it is sufficient to show that (h(jg)(x) = y

f)g

)(y) = x.

(2.5)

Whenever
g(x) < h(x) = y ,

then
h _ 1 ( y ) = x = g _ 1 g(x) < g _ 1 h(x) = g ' V )

(2. 6)
and so

(h"1ng"1)(y).= h-1(y) = x

(2.7)

Similarly, whenever
(2.8)

h(x) < g(x) = y

then (2. 6) and (2. 7) follow when h is r e p l a c e d by g and g is r e placed by h.

Hence, {2. 3) h a s been proved,,

Replacing h by h"

and g by g

and applying (2. 3) p r o v e s

(2.4).
L e m m a 2:

Let h and g be two h o m e o m o r p h i s m s such that

h + h _ 1 = g + g" 1

(2.9)

Then
hUg + (hUg)" 1 = h + h " 1

(2.10)
and

hHg + (hflg)" 1 = h + I T 1

(2.11)
Proof:

The hypothesis (2. 9) i m p l i e s that for e v e r y x,

(hUg)(x) = h(x) if and only if (h

1^

Dg

-l

,-1,

)(x) = h

(x).

Therefore,

10

SOME CONVERGENT RECURSIVE SEQUENCES,

Feb.

h + h"1

(2. 12)

= (h + h ^ y n t g + g~1)
<.hUg + h ^ D g " " 1
<(h + h " 1 ) U ( g H-g" 1 )
= h + h~X

Since the middle t e r m of (2. 12) equals h + h

1 to it yields (2. 10).

, application of L e m m a

If h is r e p l a c e d by h

(2. 9) r e m a i n s i n v a r i a n t .

and g by g

, then

T h e r e f o r e , if t h e s e substitutions a r e applied

to (2. 10), the r e s u l t is a l s o valid.

But in view of L e m m a 1, this is

equivalent to (2. 11).

L e m m a 3:
that h_> g > I.

Let h and g be any two h o m e o m o r p h i s m s

Then for any x > 0,

(2. 13)

x
_1

[h(t) + h (t)] dt> j

0

[g(t) + g"*(t)] dt

and (2. 13) b e c o m e s an equality if and only if

(2.14)

g(t) = h(t) for all h ' ^ x ) ^ t < x

Proof:

(2.15)

The set of all points

(s, t) such that

0 < s <x ,
h

~ (s) <

< g" ( s )"

is the s a m e a s the set such that

(2. 16)

0 < s <x,
g(t) < s < h(t)
0 <t

T h e r e f o r e (see F i g u r e s 1 and 2)

<g~l(x)

and

such

1966

HOMEOMORPHIC IDENTITIES, AND INDUCTIVELY

DEFINED COMPLEMENTARY SEQUENCES
x
x

(2. 17)

[h(t) + h _1 (t)] dt -J

j
0

11

[g(t) + g _1 (t)] dt

0
x

=f

[h(t) - g(t)] dt - j

[g _1 (s) - h _1 ( S )] ds

g~V)
- f [h(t) - g(t)] dt - f
0

[min(x, h(t)) - g(t)] dt

0
g

=r

(x)

[h(t> - x] dt + c [h(t) - g(t)] dt > o

h_1(x)
g _ 1 (x)
with equality if and only if h (x) = g" (x) and h(t) = g(t) for
g" (x) < t < x. But t h e s e l a s t two conditions t o g e t h e r a r e equivalent
to ( 2 . 1 4 ) .

F i g u r e 1:

[h(t) - g(t)] dt for two typical h o m e o m o r p h i s m s h and

0
g such that h > g > I and h(x) > g(x).

S O M E CONVERGENT RECURSIVE SEQUENCES,

12

Feb.

-1

-1

[ g (t) - h (t)] dt for two typical h o m e o m o r p h i s m s h

0
and g such that h_> g > I and h(x) > g(x).
T h e o r e m 6:
Let h and g be any h o m e o m o r p h i s m s .
Then
h + l T 1 = g + g"1

(2.9)
if, and only if,
(2.18)

g(x) = e i t h e r h(x) or h
Proof:

(2.19).

(x) for a l l x > 0

Define
fj = ( h U h ' ^ U g U g " 1 )

f 2 = (huh'^nfgug" 1 ) .
Then ( 1 . 9) i m p l i e s that
(2.20).

fn > f_ > I .

and

1966

HOMEOMORPHIC IDENTITIES, AND INDUCTIVELY

13
DEFINED COMPLEMENTARY SEQUENCES
"Whenever (2. 9) holds. L e m m a 2 m a y be applied four t i m e s to yield
fx + f"1 = f

(2.21)

+ ~zl = h + h " 1

But i n t e g r a t i n g (2.21) and applying L e m m a 3 to L

that f = f~.
Therefore
hUh" 1 = gUg^ 1

(2.22)

and f

proves

Now L e m m a 1 m a y be applied to obtain

h O h - 1 = ( h U h " 1 ) " 1 = (gUg" 1 )"" 1 = gHg" 1

(2.23)

But (2.22) and (2. 23) together imply (2. 18).

To prove the c o n v e r s e ,
if and only if g(x) = x.
set as | x | g ( x ) y x l .

note that (2. 18) i m p l i e s that h(x) = x

T h e r e f o r e , the set jxlh(x) / x | i s the s a m e

Since

and h a r e both h o m e o m o r p h i s m s ,

each component of this set is mapped h o m e o m o r p h i c a l l y onto itself by

h and a l s o by g. F u r t h e r m o r e , n e i t h e r

h - I nor

g-I changes sign

on any such component. So (2. 18) i m p l i e s that, on each component,

- 1 - 1
-1
-1
e i t h e r g = h and g
=h
or e l s e g = h
and g
= h. T h e r e fore, (2.9) holds on each such component.

But (2. 9) a l s o holds w h e r -

e v e r h(x) = g(x) = x.
Corollary:

Given any h o m e o m o r p h i s m

and only one h o m e o m o r p h i s m

= g +g

T h e o r e m 7:

Let h be any h o m e o m o r p h i s m .

x > 0,
x

(2.24)

[h(t) + h" X (t)] dt> x 2

and (2. 24) b e c o m e s an equality if and only if

(2.25)

h(x) = x .
Proof:

(2.26)

h, t h e r e e x i s t s one

g such that g 2 / 1 and (2. 9)

L e m m a 2 i m p l i e s that

hUh" 1 + ( h U i r V 1 = h + h" 1

Then for each

14

SOME CONVERGENT RECURSIVE SEQUENCES,

Inequality (1.9) i m p l i e s that the two h o m e o m o r p h i s m s

satisfy the conditions of L e m m a 3.

Feb.

hUh

and I

T h e r e f o r e , (2. 24) is e s t a b l i s h e d ,

and (2. 24) b e c o m e s an equality if and only if

(hUn _ 1 )(t) = t

(2.27)

for all

(hUh)"' 1 (x) < t <^x .

But (2.27) is equivalent to ( 2 . 2 5 ) .

Definition:
g^f

Given two functions

f and

g, let e i t h e r

f jg

or

be defined to m e a n that

(2.28)

f(t 2 ) - f(t r ) > g(t 2 ) - g(t x )

for all

t,

and

on the domains of

and g such that t

Note that if f and g both have continuous d e r i v a t i v e s ,

> t .

then this is

equivalent to
(2. 29)

g^f(t) > ^ - g(t)

Remark:

for a l l t .

Let a be a positive r e a l n u m b e r and let f be a con-

tinuous function of [0,).

Then f(0) =? 0 and f fa I i f a n d o n l y i f f is

a h o m e o m o r p h i s m and f

J^a

I.

T h e o r e m 8:
Let a > 2 and P f a l .
Define the sequence of
h o m e o m o r p h i s m s j h | inductively by h = I and
(2. 30)

-= P - h""1
n > 1 .
n+1
n
Then the sequence | h } c o n v e r g e s to a h o m e o m o r p h i s m
h

such

that
h + h"1 = P

(2.2)
and

(2.31)

ht

| a + Va 2 + 4 |

F u r t h e r m o r e , the convergence is uniform on e v e r y bounded subset of [ 0 , oo).

Proof:
Define by induction, r , = 1 and r ,. = a - r
.
J

1
n+1
n
h, I r , I and by induction,

Then

1966

HOMEOMORPHIC IDENTITIES, AND INDUCTIVELY

DEFINED COMPLEMENTARY SEQUENCES

15

h'Ur"1 I

(2.32)

and
(2.33)
and the h

n
Also,

h ,, = P - h ' 1 f a I - r " 1 I = r 1 I
n+1
n '
n
n+1
a r e all h o m e o m o r pr h i s m s ,

(2.34)

h 2 = P - I > I = hx

and so by induction,

h , 7 = P - h"J_. > P - h" 1 = h , _ .

(2. 35)

n+2
n+1
n
n+1
Since for each x > 0, h (x) is a monotonic n o n - d e c r e a s i n g sequence
of n u m b e r s bounded above by P(x), the sequence j h

J is pointwise

convergent. Since the r

a r e i n c r e a s i n g , (2. 32) i m p l i e s that the
-1
n
h
a r e uniformly equicontinuous on e v e r y bounded subset of [0,oo).
But this combined with (2. 30) i m p l i e s that the h a r e a l s o uniformly
equicontinuous on each such s u b s e t . T h e r e f o r e , the sequence j h \
c o n v e r g e s uniformly on e v e r y bounded subset of f0,oo) to some
homeomorphism
Since j r
some n u m b e r

h.
} is i n c r e a s i n g but bounded by a, it m u s t converge to

such that 1 < r < a.

By continuity,

r = a - r

T h e r e f o r e , h f r I which is the s a m e as (2.31).

T h e o r e m 9:
P-i- pi w h e r e

In addition to the hypothesis to T h e o r e m 8, let

p is some r e a l n u m b e r > a.

Then

(2.36)

a(jL^)

I ;

w h e r e h is the h o m e o m o r p h i s m to which the sequence of h o m e o m o r p h i s m s of T h e o r e m 8 c o n v e r g e .

Proof:
(2.37)

Define

v, = 1 and by induction
V U ' P - ^

16

SOME CONVERGENT RECURSIVE SEQUENCES,

Feb.

T h e n by i n d u c t i o n
(2.38)

, . ^ P - h" 1 4,(31 - v " 1 I = v ,_ I

n+1^
n ^
n
n+1

Therefore, h ^ v I, w h e r e

(2.39)

v=
Corollary:

I i

Let P = a L

(2.40)

n =

( P

+ V

f ^ - )

Then

^/aWTTlV m
L e m m a 4:

Let
h + h"1 = P

(2.2)
and let

and

be t w o p o s i t i v e r e a l n u m b e r s s u c h t h a t

(2.41)

xQ < h(xQ) = x _ r
Then the s e q u e n c e j x

( 2 . 1)
N
'

} d e f i n e d i n d u c t i v e l y by

, 1 .= P ( x ) - x
n+1
n
n-1

will c o n v e r g e m o n o t o n i c a l l y to

y, w h e r e

y is the l a r g e s t r e a l n u m b e r

such that
(2.42)

h(y) =? y ^ x Q

However,

for no

Proof:
h

is defined as

(2.43)

n > 0 is

= y.

For

n = -|/ or

0,

I.

Therefore,

by i n d u c t i o n , f o r

we have that

= h

n > 0,

,. = P ( x ) - x
..
n+1
n
n-1
'= h (xx ) + h ' ^ xx ) - x
.
n'
n'
n-1
,-n+l,
, ,-n-l,
.
,-n+l. x
= h
(x Q )v + h
( X() ) - h
(x Q )
= h

(x Q )

(x n )> w h e r e

1966
Since h
scribed.

HOMEOMORPHIC IDENTITIES, AND INDUCTIVELY

17
DEFINED COMPLEMENTARY SEQUENCES
(x ) <* x~, the sequence j x I m u s t converge to y as d e -

T h e o r e m 10: Let h be any h o m e o m o r p h i s m such that h + h~

m a p s positive i n t e g e r s into i n t e g e r s . Then h will n e v e r m a p any
positive i n t e g e r p into an i n t e g e r u n l e s s h(p) = p.
Proof:
If the t h e o r e m is false, then t h e r e exist positive i n t e p and q such that

gers
(2.44)

hUh'^p) = q > p .
L e m m a 2 i m p l i e s that
h U h ' 1 + (hUh" 1 )"" 1 = h + h " 1

(2.45)

Define x n as p and x .

as q and define the sequence j x

} induc-

tively by
(v 2 . 4 6 )

x ^

'

n+1

= h(x ) + h _ 1 ( x ) - x

Then applying L e m m a 4 to

hUh

n-1

, one m a y see that I x I m u s t

slowly converge as d e s c r i b e d in the l e m m a .

However, this c o n t r a -

dicts the fact, which m a y b e e a s i l y verified by induction, that the s e quence j x

I c o n s i s t s of i n t e g e r s .

T h e o r e m 11:
x ,

Let P f 2 I

and P > 21 on (0,oo).

Let x Q and

be two positive r e a l n u m b e r s .
Then a n e c e s s a r y and sufficient condition that the sequence d e -

fined inductively by
(2. 1)
x ,, = P(x ) - x ,
x
'
n+1
n'
n-1
c o n v e r g e s is that h(x ) = x , w h e r e h is the unique h o m e o m o r p h i s m
such that h_> I and
(2. 2)

h + h"1 = P

The sequence will contain a non-positive e l e m e n t if and only if

h(x^) < x , . Also, x ,_
, _ >> xx for
for some
some e l e m e n t if and only if
0
-1
n+1
n
h(x ) > x , , and this holds if and only if

18

SOME CONVERGENT RECURSIVE SEQUENCES,

(2-47)

lim x

Feb.

= + oo .

n* oo
Proof:

The e x i s t e n c e and uniqueness of h is given by T h e o r e m

8 and the c o r o l l a r y to T h e o r e m 6.

P > 21 and (2. 2) imply that h > I.

If x , = h(x ), then L e m m a 4 i m p l i e s that x

c o n v e r g e s monotonically

to z e r o .
Let x , y , x ,

and y

and y , - x , = > 0.

be positive n u m b e r s such that x

Define j x

<2-48>

= y

| inductively by (2. 1) and likewise

yn+i = p^n> - v i

If n = - 1 , then
(2. 49)

- y
y

> n e

and
(2.50)

(x

,. - y

,_) - (x

- y ) > .

s
n+1 ; n + r
n
T h e r e f o r e , by induction, for n > 0,

(2.50)

n' -

(x ,. - y , . ) - (x - y )
n+1
'n+1
n
n
= P(x
) - P(y
) - (x - Jy ) - (x . - y7 . )
x
w
n'
n
n
n'
n~1
n-l
> (x

- y y - (x

, - y

,) >

n-1

n-l

- y

and
x

- y

= (x
x

- y

) -

(x

n 3n'
n-1
> + v(xn - 1, - y' n - l, )'

>e+(n-i)e=ne
If y

= h(y ),

) + (x

n-1

i - y

n-1

i)

n-l'

then (2.49) i m p l i e s that

n > 0 and it c o n v e r g e s to infinity.

that y

is always positive for

If x ,.= h(x ), then (2.49) i m p l i e s

is monotonic and will a t t a i n negative v a l u e s .

1966

HOMEOMORPHIC IDENTITIES, AND INDUCTIVELY

19
DEFINED COMPLEMENTARY SEQUENCES
III.
Let a and b be monotonic i n c r e a s i n g mappings of positive
i n t e g e r s into positive i n t e g e r s . Then the sequences { a(nj } and { b(n) }
a r e said to be c o m p l e m e n t a r y if and only if each positive i n t e g e r is
r e p r e s e n t e d in one and only one of t h e s e s e q u e n c e s .
Given a r e a l n u m b e r r, define
n a m e l y f r l is that i n t e g e r such that
(3. 1)
Define

frl

[r] < r < [r] + 1

as the i n t e g e r p a r t of

r,

|~rl* as that i n t e g e r such that

(3.2)

[r]* < r < [r]* + 1 ,

or equivalently
(3.3)

[ r j * = -1 - [ - r ]
A r e s u l t of S. Beatty,

see R e f e r e n c e [ l J is e s s e n t i a l l y that

given a positive i r r a t i o n a l n u m b e r x, then the s e q u e n c e s |~(1 + x) n ]

r
-1
and (_(1 + x ) n j a r e c o m p l e m e n t a r y . This r e s u l t has since turned
up m a n y t i m e s in the l i t e r a t u r e , often in the form that if a and (3
x
- 1 - 1
a r e two positive i r r a t i o n a l n u m b e r s such that a
+ (3 = 1, then the
two s e q u e n c e s j a n l and [ P n ] a r e c o m p l e m e n t a r y .
A g e n e r a l i z a t i o n of this r e s u l t by Lambek and M o s e r s t a t e s
that the s e q u e n c e s |a(n) | and | b(n) \ a r e c o m p l e m e n t a r y if and only
if for each pair of positive i n t e g e r s
or e l s e b(n) - n < m but n e v e r both.

m and n, e i t h e r

a(m) - m < n

This r e s u l t combined with L e m -

m a 5 m a y a l s o be used to prove T h e o r e m 12 instead of the proof given.

L e m m a 5:
(3.4)

Let f and g be h o m e o m o r p h i s m s such that

f"1 + g" 1 = I .

Then f - I and g - I a r e h o m e o m o r p h i s m s and

(3.5)

<f - I) (g - I) = I .

C o n v e r s e l y , let h be any h o m e o m o r p h i s m .
(3.6)

Then

(I + h ) _ 1 + (I + 1 T 1 ) " 1 = I .

20

SOME CONVERGENT RECURSIVE SEQUENCES,

Feb.

Proof:
f - I = (I - f " 1 ) f = g " 1 f

(3.7)

g - I = (I - g" ) g = f"
But

f and

and

g a r e h o m e o m o r p h i s m s w h i c h a r e i n v e r s e s of e a c h

other.
(I + h ) " 1 + (I + h " 1 ) " 1

(3.8)

= (I + h ) " 1 + (I + h " 1 ) " " 1 (h + I) h~l

h (I 4 - h ) " 1

= (I + h ) " 1 + (I + h " 1 ) " 1 (I + h " 1 ) h (I + h ) " 1

= (I + h ) " 1 + h (I + h f 1
= (I + h) (I + h ) " 1 = I
T h e o r e m 12:

Let

f and
f"1

(3.4)

.
g be two h o m e o m o r p h i s m s s u c h t h a t

+ g"1 = I

T h e n t h e t w o s e q u e n c e s { [~f(n)l J- a n d { [ " g ( n ) ] * | a r e
Proof:

Given a non-negative integer

m,

let

complementary.
n]

be t h e n u m -

b e r of e l e m e n t s of j [ f ( n ) l } w h i c h a r e l e s s t h a n o r e q u a l t o
n

m, and let

b e t h e n u m b e r of s u c h e l e m e n t s of {["gin)"]*.} T h e n

( 3 . 9)

f (n ) < m + 1 <_f (n

+ 1)

g ; ( n 2 ) < m + 1 < g ( n 2 + 1)
Applying
( 3 . 10)

and

n L = f"1

= g

-1

to ( 3 . 9) y i e l d s

f ( n x ) < f"1

and

(m + 1) < f"
-1

(m

+ X

f ( i ^ + 1) = i ^ + 1
-1

) < g

g ( n 2 + 1) = n 2 + 1

A d d i n g t h e t w o p a r t s of ( 3 . 10) t o g e t h e r y i e l d s
(.3. 11)

+ n , <; m + 1 < n

+ n

+ 2

1966

HOMEOMORPHIC IDENTITIES, AND INDUCTIVELY

DEFINED COMPLEMENTARY SEQUENCES
Since n , n and m a r e all i n t e g e r s , it follows that
(3.12)

n, 4- n

Therefore,

21

= m

each positive i n t e g e r is r e p r e s e n t e d once and only once

by the s e q u e n c e s , but only positive i n t e g e r s a r e r e p r e s e n t e d .

Corollary:
quences

Let

n + [h

Proof:

(n)]*

be any h o m e o m o r p h i s m .
and

n + [ h (n)]

Then the s e -

are complementary.

Apply L e m m a 5 to the t h e o r e m .

The a n a l y s i s of Wythoff's game (see R e f e r e n c e f 4"J) involves

c o m p l e m e n t a r y s e q u e n c e s | a(n) I and | b(n) | such that
(3. 13)

b(n) = a(n) + n .

In a l a t e r p a p e r , a g e n e r a l i z a t i o n of Wythoff's game will be given for

which the a n a l y s i s will involve c o m p l e m e n t a r y sequences such that
(3. 14)
where

b(n) = a(n) + (k + 1) n ,
k. is some non-negative

integer

which defines the g a m e .

B e a t t y ' s r e s u l t is e a s i l y u s e d to show that the c o m p l e m e n t a r y s e quences satisfying (3. 14) a r e

(3.15)

a(n)
b(n) =

k+ V(k+1) +4

sh

and

3+k+ V(k+1) +4
) -

T h e o r e m 13 m a y be thought of as a g e n e r a l i z a t i o n of this r e s u l t .
T h e o r e m 13:

Let P m a p i n t e g e r s into i n t e g e r s .

quences be defined inductively as follows:

(3.16)

a(l) = 1

(3.17)

b(n) = a(n) + P(n)

n >0

a(n+l) = s m a l l e s t i n t e g e r not
r e p r e s e n t e d by e i t h e r

a(i)

(3.18)

or b(i) for some i < n

Let the se-

22

SOME CONVERGENT RECURSIVE SEQUENCES,

'Feb.

Then
a(n) = n + [h" 1 (n)"|

(3.19)

b(n) = n + [h(n)"]

and

,.

w h e r e h is the unique h o m e o m o r p h i s m such that

h = p + h~l

( i . io)
Proof:

T h e o r e m . 5 i m p l i e s that

(3.20)

[h(n)J* = [h(n)] .

So the c o r o l l a r y to T h e o r e m 12 shows that the s e q u e n c e s defined by

(3. 19) a r e c o m p l e m e n t a r y .

Since ( 1 . 10) i m p l i e s that h > h

and (3. 16), which is a s p e c i a l c a s e of (3. 18), a r e satisfied.

, (3. 18)
Equation

(3.17) follows from (1.10) and (3.19) and the fact that the P(n)

are

integers.
In R e f e r e n c e (~4J is p r e s e n t e d the following r e s u l t :
i n t e g e r g r e a t e r than 4.

(3.21)

Then the s e q u e n c e s defined by

<

-4k
\I7.
2

'k-

a(
b(n) =

a r e the s e q u e n c e s such that for

(3.22)

Let k be an

and

-4k

n any positive i n t e g e r ,

a(n) + b(n) = nk-1

and such that a(n) is the s m a l l e s t positive i n t e g e r not r e p r e s e n t e d by

any a(i) or b(i) with i < n.
The following t h e o r e m and its c o r o l l a r y m a y be thought of a s
g e n e r a l i z a t i o n s of this r e s u l t since they imply it with the help of the
c o r o l l a r y to T h e o r e m 9.
T h e o r e m 14:

Let P m a p i n t e g e r s into i n t e g e r s .

exist a homeomorphism
(2.2)

satisfying
h + h" 1 = P .

Let t h e r e

1966

HOMEOMORPHIC IDENTITIES, AND INDUCTIVELY

23
DEFINED COMPLEMENTARY SEQUENCES
Let the s e q u e n c e s j a(n) | and | b(n) | be defined inductively as follows: a(n) is the s m a l l e s t positive i n t e g e r not r e p r e s e n t e d by e a r l i e r
e l e m e n t s of a and b, and
(3.23)

b(n) = P(n) + 2 n - l - a ( n )

Then no positive i n t e g e r will be r e p r e s e n t e d twice by the two

s e q u e n c e s and for each n ^ 0,
(3. 24)

a(n) = n + [ h ' ^ n ) ] *

and

b(n) - n + [h(n)] ,
w h e r e h is the unique h o m e o m o r p h i s m such that h > I and (2.2) is
valid.
Pjrjoof:

The sequences defined by (3. 24) a r e c o m p l e m e n t a r y by

the c o r o l l a r y to T h e o r e m 12. Since h s a t i s f i e s (2.2), the s e q u e n c e s

defined by (3. 24) satisfy (3. 23).

Finally, monotonicity of the s e -

q u e n c e s , their being c o m p l e m e n t a r y and the fact that h

imply

that a(n) is the f i r s t such i n t e g e r not p r e v i o u s l y r e p r e s e n t e d .

Corollary:

Let P(n) / 2n for any i n t e g e r

a(n) = n + [ h _ 1 ( n ) ]

(3. 25)
Proof:

T h e o r e m 13.

Let x

the sequence j x
(1.4)
x
'

(n)~]*=[~h

Let { a(n) } and j b(n) | be the

and x

sequences

of
Let

I be inductively defined by
x

. - P(x )
xl = x
n+1
n-1
n
Then the f i r s t e l e m e n t of this sequence of i n t e g e r s to be non-

xQ a f x ^ ) - x ^

which in t u r n is equivalent to
(3.27)

(n)"| .

be any two positive i n t e g e r s .

positive will have an even s u b s c r i p t if and only if

(3.26)

Then

T h e o r e m 10 i m p l i e s that [ h

T h e o r e m 15:

n > 0.

x _ 1 > b(x Q ) - x Q

24

SOME CONVERGENT RECURSIVE SEQUENCES,

Proof:

T h e o r e m 5 i m p l i e s that h(x ) ^ x

Feb.

Hence (3.19) i m -

p l i e s that (3. 26) and (3. 27) a r e both equivalent to x

> h(x ).

The

proof is now completed by applying T h e o r e m 4.

This t h e o r e m m a y a l s o be p r o v e n by the r e s u l t s of Lambek and
M o s e r (Reference [6J)
T h e o r e m 16:

Let P m a p i n t e g e r s into i n t e g e r s and P ^ 2 I and

P > 21 on fO, oo) and let

14.

Let x

xn

and x ,

a(n)

and

b(n)

be the s e q u e n c e s of T h e o r e m

be any two positive i n t e g e r s .

Let the sequence

be inductivelyJ defined by
J

(2.1)

= P(x ) - x
.
n+1
n
n-1
Then the following four s t a t e m e n t s a r e logically equivalent;

(3.26)

x Q < a(x_ 1 ) - x 1

(3.27)

x _ x > b(xQ) - xQ

(3.28)

|x

\ contains a n o n - p o s i t i v e e l e m e n t

jx

{-is monotonic d e c r e a s i n g

Proof:

T h e o r e m 10 i m p l i e s that h(x ) / x

Hence (3. 24)

i m p l i e s that (3. 26) and (3.27) a r e both equivalent to x , > h(x ).

The

proof is now completed by application of T h e o r e m 1 1 .

IV.

In this section, r e p r e s e n t a t i o n s a r e sought for h o m e o m o r p h i s m s

and c o r r e s p o n d i n g c o m p l e m e n t a r y s e q u e n c e s a s s o c i a t e d with P ' s

such

that
(4. 1)

P(n) = 2an + 2(3

for n a positive i n t e g e r . The n u m b e r s 2a and 2(3 a r e a s s u m e d to

be i n t e g e r c o n s t a n t s . The r e q u i r e m e n t that P be a h o m e o m o r p h i s m
leads to the conditions that a > 0 and
(4.2)

a + p - I P ( l ) > 0.
Example 1:

F o r this e x a m p l e , let the function

F be defined a s

(4. 3)
F(x) = ( Va 2 +1 - a) x - (3 + ( V a ^ f l - 1) (3/a .
The i n v e r s e of this function is

1966

HOMEOMORPHIC IDENTITIES, AND INDUCTIVELY

DEFINED COMPLEMENTARY SEQUENCES
F - 1 ( x ) = ( V a 2 + 1 + a) x + p + ( V ? + l - 1) p / a

(4. 4)

25

Define
(4.5)

For

h~ X (x) = x F ( l )

0 < x <1

h _ 1 ( x ) - F(x)

x > 1

to be a h o m e o m o r p h i s m , it is n e c e s s a r y that F ( l ) > 0.

With some a l g e b r a i c manipulation, it is r e a d i l y seen that this r e q u i r e m e n t is equivalent to

(4.6)

(a + 2p)(l-p)>: ap

or

. ta+ p)(l-?P) > -P .

By utilizing (4. 2), it is seen that (4. 6) is satisfied if and only if p _ < l / 2 .
Condition (4. 2) and the r e q u i r e m e n t that a > 0 i m p l y t h a t h

(1) < 1.

Therefore,
h(x) = F _ 1 ( x )

(4. 7)
and so for

x > 1

n a positive i n t e g e r ,
h(n) = 2an + 2p + h _ 1 ( n )

(4.8)

So T h e o r e m s 5 and 13 give that the s e q u e n c e s

(4, 9)

a(n) = n + [ F ( n ) ]

and

b(n) = n + [ F _ 1 ( n ) ]
a r e c o m p l e m e n t a r y and satisfy
(4.10)

b(n) = 2an + 2p + a(n) > a(n)

unless

p > 1.

needed.

In the c a s e w h e r e

p > 1, other r e p r e s e n t a t i o n s a r e

Setting P = 0 and a = (k+l)/2 yields (3. 15).

F o r the next two e x a m p l e s , a h o m e o m o r p h i s m

such that for
(4.11)

However,

h > I is sought

n a positive i n t e g e r
h(n) + h ' V ) = 2an + 2p .

in some c a s e s of E x a m p l e 3, a h o m e o m o r p h i s m is found

that only g e n e r a t e s the c o m p l e m e n t a r y s e q u e n c e s that would be gen-

26

SOME CONVERGENT RECURSIVE SEQUENCES,

e r a t e d by a h o m e o m o r p h i s m satisfying (4. 11).

Feb.

In t h e s e c a s e s , a r e -

p r e s e n t a t i o n of t h e s e s e q u e n c e s is obtained.
T h e o r e m 7 i m p l i e s that a > 1.

Since the sum of two unequal

positive i n t e g e r s is at l e a s t t h r e e , T h e o r e m 14 i m p l i e s that
a + p = ([h(l)] + [ h _ 1 ( l ) ] * + l)/2 > 1

(4. 12)

E x a m p l e 2:

F o r this e x a m p l e ,

let |3 < 0 and let the function

F be defined a s
F(x) = (a V a 2 - 1 ) x + (3 - (3 V a 2 - l / ( a - l )

(4.13)

If a = 1, then P = 0 and let the l a s t t e r m of (4. 13), which would be

i n d e t e r m i n a t e , be a s s u m e d to v a n i s h .

F 4 ( x ) = (a + V - l ) x + p + P V - l / ( a - l )

(4.14)
Let h
of the

The i n v e r s e of this function is

be defined a c c o r d i n g to (4.5) with this

F being u s e d i n s t e a d

F of Example 1 The conditions on a and (3 imply that

(4. 15)

0 < F(x) < x

T h e r e f o r e , for x j> 1, h(x) = F

positive i n t e g e r

x > 1

(x) and so (4. 11) is satisfied for any

n.

If a > 1 and (3 = 0, then application of the c o r o l l a r y to T h e o r e m

14 yields Ky F a n ' s r e s u l t s u m m a r i z e d by (3.21) and ( 3 . 2 2 ) .

If a = 1

and p = 0, then h = I and the r e s u l t i n g c o m p l e m e n t a r y s e q u e n c e s a r e

r e p r e s e n t e d by
(4. 16)

a(n) = 2n - 1

and

b(n) = 2n .
E x a m p l e 3:
F o r this e x a m p l e , let P > 1/2
F be defined for x > 1 as

and let the function

F(x) = ax + P - ^ ( a x + p ) 2 - ( x - p ) 2 -

(4. 17)

= ax + p - y ( a + l ) ( a x 2 - x 2 + 2|3x) -
where

is a constant to be a p p r o p r i a t e l y chosen.

function is often two-valued.

v a l u e s yields

The i n v e r s e to this

Considering only the l a r g e s t of t h e s e two

1966.

HOMEOMORPHIC IDENTITIES, AND INDUCTIVELY

DEFINED COMPLEMENTARY SEQUENCES

(4. 18)

F ' ^ x ) = a x +..(3 + ^ ( a x + ( 3 ) 2 - ( x - P ) 2 -
It m a y b e . s h o w n t h a t

d F ( x ) / d x > 0 if a n d o n l y if

(x+p) i ( a - l ) x + p a + p j > a 2 / ( a + l )

(4.19)
Furthermore,

if

the c a s e w h e r e

27

= 0, t h e n
p = =-, s e t

F(x)

is p o s i t i v e for all

= 0 and define

.
x > p.

with this

So f o r
F

ac-

c o r d i n g t o (4. 5 ) .
F o r t h i s c a s e , 0 < F ( l ) < 1.

Therefore

h(x) = F _ 1 ( x )

(4. 20)

x > 1 .

A p p l i c a t i o n of T h e o r e m 1 4 a n d i t s c o r o l l a r y i m p l y t h a t t h e s e q u e n c e s
defined by :
a(n) - [ ( a + l ) n + i- - \ ( a 2 - l ) n 2 + ( a + l ) n ]

(4. 21)

and

b(n) = [ ( a + l ) n + \ + f ( a 2 - l ) n 2 + ( a + l ) n ]
2
a r e c o m p l e m e n t a r y and that
(4.22)

a(n) < b(n) = 2 ( a + l ) n - a(n)

In t h e p a p e r t h a t w i l l g e n e r a l i z e W y t h o f f ' s g a m e , r e l a t e d g a m e s w i l l
be p r e s e n t e d w h o s e a n a l y s i s u t i l i z e s t h e s e two c o m p l e m e n t a r y s e quences,
For

p = 1, c h o o s e > 0 b u t s u f f i c i e n t l y s m a l l t h a t

(4.23)

0 < F ( l ) < F(2) < 1

a n d t h a t , ( 4 . 19) i s s a t i s f i e d f o r

x > 2.

Define
(4.24)

h - 1 ( x ) = xF(x)

0 ^ x < l

h"1(x) = (2-x)F(l) + (x-l)F(2)

h"1(x) =.F(x)
Then

h(x) = F

for this c a s e .

(x)

for

x > 1,

1 < x < 2
x > 2 .

C o n s e q u e n t l y , h w i l l s a t i s f y (4. 11)

28

SOME CONVERGENT RECURSIVE SEQUENCES,

If (3 > 1 4, then F ( l ) > 0 i m p l i e s that

< ((3-1) .

Feb.
It m a y be

shown that this in t u r n i m p l i e s that F ( l ) > F ( 2 p ~ l ) .

Consequently,

t h e r e does not exist a n y h o m e o m o r p h i s m which equals

F for positive

integers.

However,

for c e r t a i n c a s e s , h o m e o m o r p h i s m s will be d e -

fined such that

(4.25)

[ h ' V ) ] * = [F(n)]* = [F(n)]

and

h(n) = F ' V ) .
So in t h e s e c a s e s ,
and satisfy
(4.26)

the s e q u e n c e s defined by (4. 9) a r e c o m p l e m e n t a r y

a(n) < b(n) = 2(a+l)n + 2p - 1 - a(n) .

If 2p > 3 is odd, then the r e q u i r e m e n t that

i m p l i e s that 8 > - l / 4 .

F(P y) be positive

If 2p > 4 is even, then positivity of

F(p)

i m p l i e s that > 0. F o r the s e q u e n c e s defined by (4. 9) to be monotonic

and c o m p l e m e n t a r y , it is n e c e s s a r y that
(4.27)

[F(l)] =a(l) - 1 = 0'.

The r e q u i r e m e n t that F ( l ) < 1 is equivalent to

(4.28)

2(CL+1)

- (p-2)2 > 8 .

If 2p is odd, then the left side of (4.28) equals 3/4 modulo one, but
if 2p is even,

the left side is an i n t e g e r .

Therefore, a necessary

condition for the a t t a i n m e n t of the p r e s e n t objectives is that

(4.29)

2(a+l) > ( p - 2 ) 2

This condition will a l s o t u r n out to be sufficient.

F u r t h e r m o r e , to a t -

tain t h e s e objectives when (4. 29) is valid, it is sufficient that

(4.30)

0 <<i

Condition (4. 30) i m p l i e s that (4. 19) is satisfied w h e n e v e r

x > p +.-= A l s o , (4. 30) m a y be shown to imply that
(4.31)

F(p+1) < 1 .

1966

HOMEOMORPHIC IDENTITIES-, AND INDUCTIVELY

DEFINED COMPLEMENTARY SEQUENCES

29

Define
' h " 1 ^ ) = xF([P+l])/[p+l]

(4.32)

0<x<[p+l]

h _ 1 (x) = F(x)
Then h '

x>

[p+ll

is a homeomorphism, and since

h_1([p+l])< 1 ,

(4.33)
it follows that

h(x) = F _ 1 (x)

(4. 34)

x > 1

Condition (4. 30) implies that

for any integer

n.

For any

are between zero and one.

F(n) can never be a multiple of =-1

1 < x < [(3+11, both h (x) and F(x)

Therefore,

(4. 25) is satisfied for all

positive integers as desired.

V.

The purpose of this section is to generalize the results of the

first section.

Whereas the proof of Theorem 17 uses ideas not found

in the first section,

the remainder of this section utilizes mostly

straightforward generalizations of the techniques of Section I plus applications of Theorem 17. In this section, jtf always refers to a positive real number and Al
Theorem 17:

Let

to its reciprocal.
/I < 1 and let h and g be two homeomor-

phisms such that

h + JLfg"1 = g + / / h _ 1

(5.1)
Let

h(x) 4 g ( x )
Proof:

(5.2)

f o r

some x > 0.

Then h(t) > t for all t > x.

Given any point t > 0, if h(t) > g(t), then

h" l h(t) = g^gft) < g^Mt)

which by (5. 1) implies that

(5.3)

hh(t) > gh(t)

Similarly, h(t) < g(t) implies (5.3) with the inequality reversed.

30

SOME CONVERGENT RECURSIVE SEQUENCES,

If the t h e o r e m is false,

Feb.

then for some point x, h(x) ^ g(x) and

either
(5.4)

h(x) <_x

or e l s e
(5.5)

x < h(x) < x Q = h(x Q )

for some point x .

Define x

as e i t h e r

x or h(x), whichever s a t i s -

fies
(5.6)
For

h ( X l ) < g(Xl)
n > 1, define x

as h

(x, ).

Then in c a s e of (5.4), the s e -

quence < x i is monotonic n o n - i n c r e a s i n g and bounded below by z e r o .

In c a s e of (5. 5), <x

I is monotonic i n c r e a s i n g and bounded above by x .

The f i r s t p a r a g r a p h of this proof i m p l i e s that for

(5.7)

h x

and

( 2n-l> < ^ Z n - l *

h ( x 2 n ) > g(x2n)

n > 0,

Let (y , z ) be the component of <t|h(t) ^ g(t) / w h i c h conta m s x .

n
Then the f i r s t p a r a g r a p h of this proof i m p l i e s that the open i n t e r v a l s
(y
, z ) a r e a l l disjoint
and that for n > 0
w
J
n
n
(5.8)

y n + 1 = h(y n ) = g t y j
z

n+l=.h(zn)

= g(z

n)

and
'

When (5.4) holds, then

z

(5.9)
x

, , <

'
n+1
and when (5.5) holds, then
(5. 10)

<x

< z

< x

< z

< y

Integration by p a r t s and (5. 8) imply that

1966

HOMEOMORPHIC IDENTITIES, AND INDUCTIVELY v

DEFINED COMPLEMENTARY SEQUENCES

(5.11)

(-ju)

n + 1

g(t) - h(t)

dt

^n+1
Z

(-^

y*
y

which r e p l a c i n g

n+1

jtdg(t) - tdh(t) j

n+l

g(t) by u- and h(t) by v

z

z
n

(-Uf if
y

= (-/u)

h'^vjdv !

z
n_1

g~V)du - f

j g (t) - h(t) j dt

which by induction on n
Z

J g(t) - h(t) j dt > 0 .

*1

'

In c a s e of (5.4), define

x 0 as

}"\
(5. 12)

J
0

z] .

Then for e i t h e r c a s e ,

i
hUg - hHg
'
z

oo

(t) dt
'

>ZJ

hUg hng

"

(t) dt

n=ly

n=l

/i1_n

f
y

j g(t) " h(t) { dt = oc

31

32

SOME CONVERGENT RECURSIVE SEQUENCES,

Feb.

which i s i m p o s s i b l e .
Corollary:

Let Jl >. 1 and let h and g satisfy ( 5 . 1 ) .

Then

h(x) ^ g(x) i m p l i e s that h(t) < t for all t > x.

Proof:

Replace

by h

, g by g

and

/j by JJ

and

apply the t h e o r e m .
T h e o r e m 18:

Let h and g be t w o - h o m e o m o r p h i s m s such that

h + g" 1 = g + h " X

(5.13)

Then h = g.
Proof:

Use T h e o r e m 17 and its c o r o l l a r y .

T h e o r e m 19:

Let h,

Define by induction for

be a h o m e o m o r p h i s m such that h ] P .

n > 0,

h ,. = P +/i h " 1 .
n+1
n
00
Then on each bounded subset of fO, ), <h

(5. 14)

uniformly to h o m e o m o r p h i s m s

'

. [ and { h 0

I 2n-l )

h and g r e s p e c t i v e l y .

> converge

2n I

&

Furthermore,

h < g and
h = P + fj g" 1

(5. 15)

and

g = P + Vh~l

Proof:

The a r g u m e n t s of (1. 13) through (1. 24) and the next p a r -

a g r a p h r e m a i n unchanged except that h

h

,
m-1

is r e p l a c e d by /Lf h

and

is r e p l a c e d by Mo h
T h e o r e m 20:

..
m-1
Let M 1

an(

be a positive n u m b e r .

t h e r e cannot exist m o r e than one positive n u m b e r

sequence x
(5. 16)
'
converges.
Proof:

x ,

Then

suGh that the

defined inductively by
x , . = ~lx
. - nlP(yi
n+1
/* n-1
**
Let y n , x . ,

yQ = x Q and y ^ - x ^ = 8 .

and y

)
n

be positive n u m b e r s such that

1966

HOMEOMORPHIC IDENTITIES, AND INDUCTIVELY

DEFINED COMPLEMENTARY SEQUENCES
Define / y i inductively by
<5-17)

yn+i = ^ ^ n - i -

33

tf'lp<yn>

Then analogous to ( 1 . 32), (1.33) and (1.34) a r e the s i m i l a r l y obtained

results
(5.18)

Yl

Xj

=M_1e

and
(5

" 19)
and
(5- 20)

^Zn '

2n

<

" " ^ Z n - Z " XZn-2> <

y 2 n + 1 - x 2 n + 1 > ^ " V ^ . ! - x 2n _j) > /, - " ^

>

So at m o s t one of the s e q u e n c e s m a y c o n v e r g e ,
T h e o r e m 21:

Let h and g b e t w o h o m e o m o r p h i s m s s u c h t h a t
h = P +/j- h." 1

(5.21)
and
(5.22)

g= P +/lg"1

Then h = g.
Proof:

Identities (5. 21) and (5. 22) imply (5. 1). If /I > 1, then

(5.21) i m p l i e s that h > h

T h e r e f o r e , h > I and the c o r o l l a r y to

T h e o r e m 17 finishes the proof for fJ > 1.

If /J < 1, then for any x > 0, e i t h e r h(x) <^ x or g(x) < x or
e l s e h(x) > x and g(x) > x. In the f i r s t two c a s e s T h e o r e m 17 i m plies that h(x) = g(x) 0 In the l a s t c a s e , the s e q u e n c e s | x J = i h
and i y 1 = I g

(x)i a r e both c o n v e r g e n t .

(5. 16) and (5. 17).

(5.23)

(x) }

But t h e s e s e q u e n c e s satisfy

Since x = y = x, T h e o r e m 20 i m p l i e s that
h(x) = x_ x = y ^ = g(x) .

T h e o r e m 22:
homeomorphism.
inductively by

Let JJ < 1 and P +

I > I.

Let g

Then the sequence of h o m e o m o r p h i s m s

be any
defined

34

SOME CONVERGENT RECURSIVE SEQUENCES,

(5.24)

Feb.

gn+1 = P + * g ^

c o n v e r g e s uniformly on e v e r y bounded subset of j 0,oo) to a unique

homeomorphism

h such that
h = P + Mh""1 .

(5.21)
Proof:

Choose

(5.25)

hx = ^ g l n g 2 ( M i ) n p

Then T h e o r e m 19 is a p p l i c a b l e .

F o r any x > 0, g(x) > x for if not,

h(x) <. g(x) < x which i m p l i e s that h

(x) > x and hence that

g(x) = P(x) +/i h" X (x) > P ( x ) + / i x > - x

(5.26)

Therefore,
hg = (P +/i g" X )g = Pg + / l l > P +/i I > I .

(5.27)

But hg > I i m p l i e s that h > g

which in t u r n i m p l i e s that gh > I.
F o r any point x > 0, define x
as h(x ). Let the sequence

{ x j be dlefined

inductively by ( 5 0 l 6 ) .

Then a r g u m e n t s analogous to

(1.28) and (1.29) imply (1.26) and ( 1 . 2 7 ) .

Since

h ^ g " 1 = (gh)" 1 < I ,

(5.28)

the sequence y x \ c o n v e r g e s to z e r o .
is defined a s

By s i m i l a r a r g u m e n t s , if x ,

g(x ), the sequence <x / will still c o n v e r g e .

Theorem

20 t h e r e f o r e i m p l i e s that g(x n ) = h(x ) Since h = g, the c o n v e r g e n c e

for

g. , i n s e r t

/j into the p r o p e r positions of (1.39) and (1.40), and

continue the a r g u m e n t of the p a r a g r a p h containing (1.39) and ( 1 . 4 0 ) .

Uniqueness of h is obtained from T h e o r e m 2 1 .
Corollary:
(5. 15)

Let h and g be two h o m e o m o r p h i s m s such that

h = P + ^g"1
P + Uh" 1

Let

U < 1 and P + /I I > I.

Then h

and

1966

HOMEOMORPHIC IDENTITIES, AND INDUCTIVELY

DEFINED COMPLEMENTARY SEQUENCES
Theorem

23:

Let

/l 4 1

and

P +JJ I > I.

Then a sequence

g e n e r a t e d b y ( 5 . 16) w i l l c o n v e r g e if a n d o n l y if x
h

is the h o m e o m o r p h i s m

of T h e o r e m 2 2 .

35

= h(x )

Furthermore,

where

if i t d o e s

c o n v e r g e , it will c o n v e r g e to z e r o .
If h ( x ) > x , , t h e n a l l of t h e e v e n l y s u b s c r i p t e d e l e m e n t s of t h e
sequence a r e positive,

b u t a l l b u t a f i n i t e n u m b e r of t h e e l e m e n t s

w i t h odd s u b s c r i p t s a r e n e g a t i v e .
If h ( x ) < x . , t h e n a l l of t h e odd s u b s c r i p t e d

elements are

p o s i t i v e a n d a l l b u t a f i n i t e n u m b e r of t h e e v e n s u b s c r i p t e d e l e m e n t s
are negative.
Proof:
then < x

P +u I > I a n d ( 5 . 21) i m p l y t h a t

\ = sh

h > I. If h ( x Q ) = x

(xn) 1 and the s e q u e n c e c o n v e r g e s to z e r o .

h ( x ) / x , , t h e n ( 5 . 19) a n d ( 5 . 20) m a y r e p l a c e
o r d e r to continue the a r g u m e n t s

When

( 1 . 33) a n d ( 1 . 34) i n

of t h e p a r a g r a p h s c o n t a i n i n g ( 1 . 33)

t h r o u g h ( 1 . 36).
T h e o r e m 24:

L e t /*

be an i n t e g e r ,

i n t o i n t e g e r m u l t i p l e s of \X a n d l e t

let

P +/I I > I.

map integers

Then the

satis-

fying
h = P +/I h " 1

( 5 . 21)

will n e v e r m a p a positive integer into an i n t e g e r .

Proof:

U s e t h e p r o o f p r e s e n t e d i n t h e l a s t p a r a g r a p h of S e c -

t i o n I.
B I B L I O G R A P H Y ON C O M P L E M E N T A R Y S E Q U E N C E S *
1.

Problem
(1926),

3177 ( o r i g . # 3 1 7 3 ) ,

Amer.

Mathe

Monthly,

p . 159 b y S a m u e l B e a t t y ; S o l n s . , v o l .

v o l . 33

34(1927), pp.

159-160.
2.

R. S p r a g u e , E l n Satz u b e r Teilfolgen d e r R e i h e d e r n a t u r l i c h e n
Zahlen.

3.

M a t h e m a t i s c h e A n n a l e n , v o l . 115 ( 1 9 3 8 ) , p p . 1 5 3 - 1 5 6 .

Uspensky and Heaslet,

9, p . 9 8 .

C o u r t e s y of H . W. G o u l d

Elementary Number Theory,

Problem

36

SOME CONVERGENT RECURSIVE SEQUENCES,

Feb.

4.

P r o b l e m 4399, A m e r . Math. Monthly, vol. 57 (1950), p . 343 by

Ky Fan; Soln. vol. 59 (1952), pp. 48-49 by H. S. Z u c k e r m a n .

5.

H. S. M. Coxeter, The Golden Section, P h y l l o t a x i s , and Wythoff's

Game, Scripta M a t h e m a t i c a , voL 19 (1953), pp 0 135-143.

6.

Lambek and M o s e r ,

On Some Two Way Classifications of Inte-

g e r s , Canad. Matho Bull. vol. 2 (1959), pp. 8 5 - 8 9 .

7.

Dan G. Connell,

Some P r o p e r t i e s of Beatty Sequences, Canad*

Math. B u l l . , vol. 2 ( 1 9 5 9 ) , pp. 181-197.

8.

Howard D. G r o s s m a n ,

A Set Containing All I n t e g e r s ,

Amer.

Math. Monthly, vol. 69 (1962), pp. 5 3 2 - 5 3 3 .

9.

E. N. Gilbert,

Functions Which R e p r e s e n t All I n t e g e r s , A m e r .

Math. Monthly, vol. 70 (1963), pp. 736-738, (Acknowledgement,

vol. 70, p. 1082).
10.

Myer Angel,

P a r t i t i o n s of the N a t u r a l N u m b e r s , Canad. Math.

B u l l . , vol. 7 (1964), pp. 219-236.

xxxxxxxxxxxxxxx

NOTICE TO A L L SUBSCRIBERS! I I
P l e a s e notify the Managing E d i t o r AT ONCE of any a d d r e s s change.
The P o s t Office D e p a r t m e n t , r a t h e r than forwarding m a g a z i n e s - m a i l e d
third c l a s s , sends them d i r e c t l y to the d e a d - l e t t e r office.

Unless the

a d d r e s s e e specifically r e q u e s t s the Fibonacci Q u a r t e r l y be forwarded

at f i r s t c l a s s r a t e s to the new a d d r e s s ,

he will not r e c e i v e it.

(This

will u s u a l l y cost about 30 cents for f i r s t - c l a s s p o s t a g e . ) If p o s s i b l e ,

p l e a s e notify us AT
dates:

LEAST THREE WEEKS PRIOR to publication

F e b r u a r y 15, A p r i l 15, October 15, and D e c e m b e r 15.

EXTENSIONS OF RECURRENCE RELATIONS

Raymond E. Whitney
Lock Haven State College

The p u r p o s e of this a r t i c l e is to investigate analytic extensions

of F

and

to the complex p l a n e . We shall begin by c o n s i d e r i n g

a p a r t i c u l a r extension.

L a t e r we will c o n s i d e r a l t e r n a t e e x t e n s i o n s .

We begin with the following notation

a=(l+i/5)/2
Since

and (3 = (1 - V ? ) / 2

(3 < 0 we adopt the convention

(3 = e

(-P).

With t h e s e conventions, we shall m a k e the following definitions:

The Fibonacci Function,

F(z) = 1 / i/5~ (a Z - p Z )

The Lucas Function 3

Mz) =

+P

Note that F(n) = F and L(n) = L , w h e r e n denotes an i n t e g e r .

\
a
n
n
I
P e r i o d i c P r o p e r t i e s of F(z) and L(z)
T h e o r e m 1.
_
Proof.

is p e r i o d i c with period

z + pa
a

Jru

z
= a

Ziri
e

pz

Proof.

F(z) and

Deny!

implies a ^ = p
Thus F ( z + 0 ) ) =
Hence

F(z) has p e r i o d o> .

F(0) = 0 = F(co)

.
1//?Q

(Q

- PZ) .
Then p w / 1 u n l e s s a> = 0.

L(z) is s i m i l a r ,

Z e r o e s of F(z) and

T h e o r e m 4.

PP = p z e 2 7 r i = pZ .

a w = 1, so Re(co) = 0.

The proof for

II

?
2
2 7T/(ln a + ?r )( 7T - i l n a ) = p .

L(z) a r e not periodic 0

Assume
w

.= a .

T h e o r e m 2.
p is p e r i o d i c with period
Proof.
Since - l n a = l n ( - p ) , we have

T h e o r e m 3.

Z?Ti/lna = p

L(z).

The z e r o e s of F(z)

are

4k7Tlna/(41n 2 a + 7T2)( - ?r/21na + i ) .

37

38

EXTENSIONS OF RECURRENCE RELATIONS

Proof.

Feb.

N o t e t h a t t h i s t h e o r e m i m p l i e s t h e o n l y r e a l z e r o of
F(z)

i s 0.

F ( z ) = 0 i m p l i e s (a/(3)
Setting

= 1= e

, k an integer.

z = x + iy and collecting real and imaginary parts and

equating, the result follows.

T h e m o d u l i of t h e z e r o e s a r e
Theorem 5.

|Zk|7r/v/41n a + V

T h e z e r o e s of L ( z ) a r e

2 ( 2 k + 1) l n a / ( 4 1 n 2 a + 7T 2 )( - 7 r / 2 1 n a + i) = z^,
where
Proof.

k is an integer.

Note that this t h e o r e m i m p l i e s , L(z) h a s no r e a l

ir -4i
(2k+l)7ri
,
,
,
W r i t e - 1 = ev
'
andproceed as above.

zeroes0

T h e m o d u l i of t h e z e r o e s a r e | 2 k + l | TT/
O b s e r v e t h a t a l l of t h e z e r o e s of L ( z ) a n d F ( z ) a r e o n t h e r a y
= A r c t a n ((-21na)/7r) ~ - 2 0 .
III

Behavior of F(z) and

Theorem 6.

L(z) on the real axis.

On the real axis, the only real values of

are at z = n (an
integer),
\
to
/> that is, Fn
_.
r
Proofo

and

F(z) and

L(z)

Ln .

.
_
z
x Qz
-xlna + TTxi
Since y = 0, a = a , p = e
;
Im F(z) = Im L(z) = 0 yields
i / /T -xlna .
- 1/ y5 e
sm TT x = 0 or
-xlna
e

.
~
sm 7Tx = 0.

Hence x = k, k an integer.
(It is not too difficult to show that the only lattice points with real images for
IV

F(z) are on the real axis. )

Identities Satisfied by F(z) and

Many of the identities of F

L(z).

We shall list a few of them.

L(z).

and

carry over to

F(z) and

They are easy to verify,

a.

F(z+2) = F(z+1) + F(z)

c.

F(z+1 )F(z-1) - F 2 (z) = eW1Z

b.

L(z+2) = L(z+1) + L(z)

d.

L2(z) - 5 F 2 (z) = 4e ? r i Z

1966

EXTENSIONS OF RECURRENCE RELATIONS

e.

F(-z) = -eWlZ

f.

F(z)L(z) = F(2z)

g.

F(z+w) = F ( z - l ) F ( w ) + F(z)F(w+l)

h.

F(3z) = F 3 (z+1) + F 3 ( z ) - F 3 ( z - 1 )

i.

LimF(x)/F(x+l) =

39

F(z)

X > 00

LimF(iy)/F(iy+l) = - p
y->oo
In g e n e r a l , (-1)
in an identity for F
and L c a r r i e s over to
7T iz
e
. The i d e n t i t i e s which do not c a r r y over to F(z) and L(z) a r e
those which only m a k e s e n s e for i n t e g r a l a r g u m e n t . That i s , those
which involve binomial coefficients, e t c .
V
Analytic P r o p e r t i e s of F(z) and L(z).
Note that our convention for
is thus i m m e d i a t e that

F(z) and

(3 i m p l i e s

ln(3.= Wi 4- ln(-(3).

It

L(z) a r e h o l o m o r p h i c in the plane

(entire functions).
F r o m the Taylor formula, we have for any finite

F(z) = 1 / / 5

L(z)' = I

z,

oo
2 j [ ( l n k a ) a W - (lnkp)pW] / k l j (z-w)k
k=0

and

| [ ( l n k a ) a W + (lnkp)pW] /k! } (z-w)k .

k=0
Note the r e s u l t s when t h e s e a r e used with w = 0 and z = n or with
w = n-1

and z = n.

Fn= IA/5

X [ ( l n k a ) a n - 1 - ( I n ^ P ^ 1 ] /k!
k=0

This i s , I believe, a new r e p r e s e n t a t i o n for

F . The H a d a m a r d
n
F a c t o r i z a t i o n t h e o r e m can be used to e x p r e s s L(z) as a canonical
producto As in t h e o r e m 5, let z, r e p r e s e n t a z e r o of L(z). R e n u m b e r z, a s follows:
k

40

EXTENSIONS OF RECURRENCE RELATIONS

Feb.

k = - 1 , 0, - 2 , 1, - 3 , 2, . . .
n = 1, 2, 3, 4, 5, 6, . . .
Now 1z
< z ,,
and
z
= 0(n). It is e a s y to see that
n ' ~" ' n+1 '
' n'
of o r d e r and genus 1 and we have
L(z) = e

fl

(1 -

/z )

n ,

L(z)

is

where

n=l
oo

l~ ln d - l /' z n ) + l / z n 1J

c =- 2

n=l
We s h a l l now d i s c u s s e x c e p t i o n a l v a l u e s of
and

L(z)

a r e entire functions

F(z)

with essential

and L(z).

Since

F(z)

s i n g u l a r i t i e s a t oo,

by

P i c a r d ' s t h e o r e m , t h e y m u s t t a k e on e v e r y v a l u e , e x c e p t p o s s i b l y o n e ,
a n d i n f i n i t e n u m b e r of t i m e s .
Lim L(x-ix) = Lim F(x-ix) = 0
x -> oo
Thus

' x '-> oo

0 is a n a s y m p t o t i c value for

F(z)

and

L(z).

L i m L(x) = L i m F ( x ) =ooand oo
X->00

X - > 00

is an a s y m p t o t i c value for F(z) and L(z).

A h l f o r s h a s shown that e n t i r e functions of o r d e r
2 P a s y m p t o t i c values [ l ] .

P have at m o s t

F u r t h e r , if an i n t e g r a l function has

an exceptional value, then z is an a s y m p t o t i c value [2~] .

not an exceptional value for

F(z) or

L(z); P a r t II,

Hence

z as

Now 0 is
F(z)

and

L(z) have no finite exceptional v a l u e s .

Thus the Fibonacci P r i m e Conjecture is t r i v i a l in the complex
plane; that i s , t h e r e a r e an infinite n u m b e r of Fibonacci i m a g e s which
a r e distinct p r i m e s .

It is conceivable that a knowledge of the d i s t r i -

bution of p r i m e i m a g e s might yield a r e s o l u t i o n of this c o n j e c t u r e , a l though this p r o b l e m is probably m o r e difficult than the conjecture itself.
P o i s s o n ' s formulae for r e a l and i m a g i n a r y p a r t s of F(z) m i g h t be
useful, but the i n t e g r a l s a r e h o r r i b l e F r e s n e l type i n t e g r a l s ("3] .
A c h a r a c t e r i z a t i o n of the point set c o r r e s p o n d i n g to Im F(z) = 0
should p r e s e n t an i n t e r e s t i n g problerru

Graphs of | z | R e F ( z ) = 0. |. ,

1966

EXTENSIONS OF RECURRENCE RELATIONS

41

| z I ImF(z) = 0 | , | z I I F(z) I = M J in some neighborhood of the origin

should yield i n t e r e s t i n g d i a g r a m s .
VI

Alternate Extensions.
T h e r e a r e an infinite n u m b e r of extensions of F

and

to
n

e n t i r e functions in the complex p l a n e . If the functional equation

G(z+2) = G(z+1) + G(z); G(0) = 0, G(l) = 1 ,
is used a s a s t a r t i n g point,

it a p p e a r s that v e r y little can be e s t a b -

lished. However it is p o s s i b l e to obtain extensions which a r e r e a l at

e v e r y point of the r e a l a x i s .

Consider, for e x a m p l e ,

F x ( z ) = 1/ \ / 5 [ a Z - s i n ( ^ i 7 r ) (-P)2]

Note that F , (z) s a t i s f i e s the r e l a t i o n ,

F ^ z + l J F ^ z - l ) - F 1 2 (:z) = sin (2z + l) ir /Z

F , (z) is an e n t i r e function and has z e r o e s on the negative r e a l axis

and F , (n) = F ,

n an i n t e g e r .

Another type of extension i s ,

. .
Zwiz _ . x .
F?(z) = e
F(z) + s m ir z
P r a c t i c a l l y n o n e of the above t h e o r e m s hold for a r b i t r a r y e x t e n s i o n s .
The following c o n s t r u c t i o n s e e m s to indicate that

could be ex-

tended to a p e r i o d i c e n t i r e function in the complex plane.

the r e c t a n g l e , R, in the complex plane bounded by
(1,0), (1,1), ( - 1 , 1 ) , (-1,0)

Select a function, F - ( z ) , subject to the following conditions:

a.

F 3 (0) = 0

b.

F 3 ( - l + i y ) + F 3 (iy) = F 3 ( l + i y ) ; . y e [ 0 , l ]

c.

F 3 (x) = F 3 (x+i); x e [ - 1 , 1 ]

d.

F 3 ( - l ) = F3(l) = 1

e.

F^(z), analytic on R .

Consider

42

EXTENSIONS OF RECURRENCE RELATIONS

Extend

F3( )

Feb.

v e r t i c a l l y by p e r i o d i c i t y and h o r i z o n t a l l y by the func-

tional equation, F~(z+2) = F~(z+1) + F~(z) 0

e n t i r e function with p e r i o d i and

The extension would be an

F~(n) = F , n an i n t e g e r .

REMARKS
Selection of a p r o p e r extension for

F(n)

should, via the m a c h -

i n e r y of Analytic Function theory, put a powerful w r e n c h on the F i b onacci P r i m e Conjecture.

REFERENCES
1.

E. T i t c h m a r s h , The T h e o r y of Functions, 2nd ed. (1952), p. 284b.

2.

Ibid, p . 284a.

3.

Ibid, pp 0 124-125*

xxxxxxxxxxxxxxx

CORRECTIONS
"Binomial Coefficients, the B r a c k e t Function,

and Compositions with

Relatively P r i m e S u m m a n d s " by H W. Gould,

Fibonacci Q u a r t e r l y ,

2(1964), pp. 241-260

Page 241.

The second p a r a g r a p h should begin:

equivalent to the identical congruence

"Indeed this r e s u l t is

(1 - x ) P = 1 - x P ( m o d p )

! I

Page 245.

In T h e o r e m 3 it is n e c e s s a r y to r e q u i r e

P a g e 257.

Line after r e l a t i o n (48), r e p l a c e "out" by " o u r " .

P a g e 251o

Line 9 from bottom, for " a s " r e a d "an".

XXXXXXXXXXXXXXX

a. > 0.

SOME ORTHOGONAL POLYNOMIALS RELATED TO FIBONACCI NUMBERS

L Carlitz
Duke University, Durham, North Carolina

1.

We c o n s i d e r polynomials

f (x)
n

such that

(1)

f n + 2 (x) = (x+2n+p + l ) f n + 1 ( x ) - (n 2 +pn+q)f n (x)

(n = 0, 1, 2, . . . ),

where
(2)

fQ(x) = 0, f ^ x ) = 1 .

It foLlows at once that f (x) is a polynomial in x of d e g r e e n-1

n k 1.

The p a r a m e t e r s

(4)

p, q a r e a r b i t r a r y but we shall a s s u m e that

p 2 - 4q / 0 .

(3)

Let a, p denote the r o o t s of the equation

2
x - px + q = 0 .

In view of (3), the r o o t s

(5)

a, p a r e d i s t i n c t and
a+P = p,

ap = q .

We shall c o n s t r u c t a g e n e r a t i n g function for

(6)

F(t) = F(t,x) = 2

n(

f (x):

x tn

) /ni

n=0
It is e a s i l y verified that (1), (2) and (6) imply
(7)

( l - t ) 2 F " ( t ) - [ ( x + ( p + l ) ( l - t ) ] F ' { t ) + qF(t) = 0 ,

w h e r e the p r i m e s indicate differentiation with r e s p e c t to t.

It is convenient to define an o p e r a t o r .
(8)

A = ( l - t ) 2 D 2 - (p+l)D + q

(D = d/dt)

Thus (7) b e c o m e s
(9)

for

A F(t) = x F ' ( t )

Supported in p a r t by NSF g r a n t GP 1593 0

43

44

SOME ORTHOGONAL POLYNOMIALS R E L A T E D

Feb.

Consider
A(l-t)~a~k=

|(a+k)(a+k+l)-(p+l)(a+k) + q [ ( l - t ) " a " k

M a k i n g u s e of (4) w e find t h a t t h i s r e d u c e s t o
/\(l-tfa~k = k(2a-p+k)(l-t)-a"k

(10)

T h u s , if w e p u t

00
H

< >

(aKxk

*" < ' * > * !

k=0

ki(2a-P + n

V-*

where
(a), = a ( a + l ) . . . ( a + k - 1 )

we get
oo

xk+1

(a)

A*.(t.a)= 2 -

kKZa-p + lK

k=0

(1 t}

We h a v e t h e r e f o r e
(12)

A 4> (t, a) = x <D (t, a)

and in exactly the s a m e way

(13)

A <t> ( t , p) = x <&'(t, P) .
It f o l l o w s f r o m (11) t h a t
oo ^

(t a)

'

= E'

xk

(a)

(a+k)n

kTTZa^TT)- E

-HT^

k=0
00

n=0
jc
V^

nT

Z-f k ! ( 2 a - p + l )
k=0
^

n=0
If w e p u t

(14)

, v
k
(a) M x
v ;
n+k

^n
t

*n(x.a) =

k=o

.i

k ! ( 2 an-+pk+ l ) ,

tR

1966

TO FIBONACCI NUMBERS

45

then we have

(15)

$n(x, a)tn/n:

* (t, a) =

n=0
Note that (14) i m p l i e s
(16)

0 n ( x , a) = ( a ) n

where
2.

F,

j F j l a + n ; 2 a - p + l ; x) ,

denotes a h y p e r g e o m e t r i c function in the u s u a l notation.

If we m a k e use of (12) and (15) we find without m u c h difficulty

that 4> (x, a) s a t i s f i e s the r e c u r r e n c e

(17)

0 n+2 ( X s

a) =

( x + 2 n + P + 1 ) $ n + 1 ( x > a)-(n Z +pn+q)^ n (x, a) (n > 0) .

C l e a r l y $ (x, p) s a t i s f i e s the s a m e r e c u r r e n c e .

Thus any linear

combination
q, (x) = A $ (x, a) + B ^ (x, p) ,
w h e r e A, B, a r e independent of n but m a y depend on x, a, p, will
a l s o satisfy (17).
We choose A, B so that
(18)

ip Q (x) = 0,

^(x) = 1

This r e q u i r e s
AC = 0 Q ( x , P),

BC - - $ 0 ( x , a) ,

where
(19)

C = * 1 ( x , a)0 Q (x, P) - ^ 1 ( x J p ) < ^ 0 ( x , a)

It is c l e a r by c o m p a r i s o n of (17) and (18) with (1) and (2) that

* n(x)

= f

n(x)

( n = 0, 1, 2, . . . )

We have t h e r e f o r e
A (x, a ) (x, p) - A (x, P)* n (x, a)

(20)

yx) =

T-B

46

SOME ORTHOGONAL POLYNOMIALS R E L A T E D

Feb.

with C defined by (19).

Thus by (6) and (15)
(21)

F(t) = C " 1 U ( t ,

Q)^0(X,

(3) - c D ( t , P ) ^ 0 ( x , a) J ,

so that we have obtained a g e n e r a t i n g function for

3.

f (x).

In addition to the polynomial f (x) we m a y c o n s t r u c t a second

solution g (x) of (1) such that

(22)
Thus

g ( ) (x)

- 1,

g x (x) = x+p + 1 .

g (x) is a polynomial in x of d e g r e e n.

By exactly the s a m e

method we have used above, we find that

(23)

< (x, a) A (x, P) - A (x, P)0 (x, a)

g (x) = - 2 - B
i
2
i
+ (x+p)f (x) .
n
c
If we put
G(t) = G(t, x) = J2 g n < x )
n=0

(24)

tn

A!

it follows that
# ( t , ^ ( x , P) - <D(t, P)</) 1 (x,a)
(25)

G(t) = -2
x+p U ( t , a)* (x, P) - cj>(t,p)^ (x, a) 1
Q
0
C
2
If the coefficient n'+pn+q o c c u r r i n g in (1) is positive for all

n > 0 then by a known r e s u l t [ l ] we can a s s e r t that the polynomials

g (x) a r e orthogonal on the r e a l line with r e s p e c t to some weight function.

The s a m e r e m a r k a p p l i e s to the f (x).

It would be of i n t e r e s t

to explicitly d e t e r m i n e t h e s e weight functions.

4.
tinct.

(26)

We have a s s u m e d in the above d i s c u s s i o n that a and p a r e d i s When a and p a r e equal we m a y r e p l a c e (1) by

f ^.(x) = (x+2n+2a+l)f , _ (x) - (n+a) 2 f (a)

n+2
n+1
n

(n = 0, 1, 2,

1966

TO FIBONACCI NUMBERS
We n o w p u t
00

+k
*n(x) = -<^>n
ITET

(27)

k=0
00

(28)

(a) x

00

<&(t)= *n

(x)t / n i =

n=0

E ~k^T~ t1"1)"
k=0

It i s e a s i l y v e r i f i e d t h a t
(29)

4> , , ( x ) = ( x + 2 n + 2 a + l ) 0
(x) - ( n + a ) 2 0 (x)
n+c.
n+1
n

(n = 0, 1

and that
A * ( t ) = x4) l (t)

(30)

A s a s e c o n d s o l u t i o n of (26) w e t a k e

* n W=f; T ^ ( W a > - 2 k ) x

(31)
where

(32)

cr x/Q) = 1 + 1 + . . . # +
k

'

a+1

""

a+k-1

<r = cr' (U 1 1 + + . . o + .
k
k* '
2 * k "
We o m i t t h e p r o o f t h a t $ (x) d o e s i n d e e d s a t i s f y ( 2 6 ) .
It i s c o n v e n i e n t t o p u t

(33)

V(t) - ^
n=0

It c a n b e v e r i f i e d t h a t ^ ( t )

^n(x)

a l s o s a t i s f i e s (30).

If w e n o w p u t

(34)

* ( x ) * (x) - 0\,(x)<f (x)

n
f (x) = - J ^ J l - ^
-. J

then we have

(n = 0, 1, 2, . . . )

48

SOME ORTHOGONAL POLYNOMIALS R E L A T E D

(35)

fQ(x) =.0,

f x (x) = 1

Feb.

Thus f (x) is a polynomial of d e g r e e n-1 in x for

n > 1 and is the

unique solution of (26) that s a t i s f i e s (35).

S i m i l a r l y if we put
(36)

g (x) = 2

0 (x)$ (x) - iff ( x U (x)

\ . '*
Y_^L_^

+ ( x +2a+l)f (x)

then
(37)

g Q (x) = 2,

Thus g (x) is a polynomial of d e g r e e

gl

( x ) = x + 2a+l

n in x and is the unique solu-

tion of (26) that satisfies (37).

Explicit f o r m u l a s for the g e n e r a t i n g functions <t>(t) and ( t )

can

now be stated without any difficulty,,

Here again it would be of i n t e r e s t to explicitly d e t e r m i n e the
weight functions connected with }f (x) f and |g (x) \ , r e s p e c t i v e l y .
REFERENCE
1.

J. F a v a r d , Sur les polynomies de Tchebicheff,

Comptes r e n d u s

de 1' A c a d e m i e des Sciences, P a r i s , vol. 200 (1935), pp. 20522053.

xxxxxxxxxxxxxxx

A NOTE ON ORTHOGONAL POLYNOMIALS

J.C. Ahuja and S.W. Nash
University of Alberta, Calgary, Canada

1.
The r e c u r r e n c e

INTRODUCTION

r e l a t i o n for

orthogonal

polynomials

(leading coefficient one) a s s o c i a t e d with the density function

q (x)

f(x)

over

the i n t e r v a l a, b is d e r i v e d explicitly in t e r m s of the m o m e n t s of f(x).

Further,

an a l t e r n a t i v e proof is given of the t h e o r e m that if f(x)

s y m m e t r i c a l about x = 0, then the polynomials

is

q (x) a r e even or

odd functions a c c o r d i n g as n is even or odd.

2.

RESULTS

Let f(x) denote the density of a d i s t r i b u t i o n function

F(x)

with

infinitely m a n y points of i n c r e a s e in the finite or infinite i n t e r v a l

a, b , and let the m o m e n t s

= I x f(x)dx

exist for r = 0, 1, 2, o e e
It is well known, see S z e g o f l ] , that t h e r e e x i s t s a sequence
of polynomials

p 0 (x), p (x), p 2 (x),

oee

uniquely d e t e r m i n e d by the

following conditions:
(a) p (x) is a polynomial of p r e c i s e d e g r e e
coefficient of x
(b) the s y s t e m

n in which the

is positive.

p (x) is o r t h o n o r m a l , that is
1 for m = n

P m (x)p n (x)f(x)dx =

If, on the other hand,

0 for m -f
F(x) has only N points of i n c r e a s e , then

the p (x) exist and a r e uniquely d e t e r m i n e d for

and if

F(x)

n = 0, 1, . . . , N - 1 ;

has only finitely many finite m o m e n t s ,

49

say

ro71

or

A NOTE ON ORTHOGONAL POLYNOMIALS

50

r r u , in e x i s t , t h e n t h e
Zk+1
n = 0, 1, . . . , k.
The p o l y n o m i a l s

p (x)
n
p (x)

Feb.

e x i s t and a r e uniquely d e t e r m i n e d for

s a t i s f y i n g c o n d i t i o n s (a) a n d (b) a b o v e a r e

of t h e f o r m

(i)

. D

ii-1

mQ

mx

mz

m1

mz

m3,

n+l

2n-l

,
n-1

n+l

where
mQ

n^

m2

m,

m~

m~

n+l

D
,
n-1

m
n

a n d w h e r e t h e l e a d i n g c o e f f i c i e n t s of

p (x)

q (x)
n

t h e n the

q (x)

are

Dn - 1

If w e n o w d e f i n e t h e p o l y n o m i a l s

(2)

.,
n+l

,, . . . . m n
,
n+l
Zn-1
m .0 . . . . mn
n+Z
Zn

q (x)

as

pw

a r e orthogonal polynomials whose leading

coefficients

a r e always one.
A c c o r d i n g t o S z e g "o |r_ l T] ,

the

following

three consecutive orthonormal polynomials:

r e l a t i o n holds for

any

1966

A NOTE ON ORTHOGONAL POLYNOMIALS

(3)

51

P n (x) = (A n x + B n )p n _ l ( x) - C n p n _ 2 (x), n = 2, 3, . . .

where

A , B and C are constants, A > 0 and

n
n
n
n
highest coefficient of p (x) is denoted by k , then
k
A

n ~

k =\l^
J 3 - 17 " ,

Since k

5_
n-1
TT~T

n ~ An-1
;

C > 0,
n

If the

k k ^
n n-2
k ,
72
n-1

we shall have

n n-2
The relation (3) then becomes

4,> p M =

i+

p w

fofe vK' -V^?ftO -*

Multiplying both sides of (4) by

D
n

and using (2), we get

n- 1

B , let us suppose
that k! is the coefficient of x "
r r
n
n
p ( x ) , w h i l e k i s t h e c o e f f i c i e n t of x
i n p (x) e B y e q u a t i n g
To find

in

t h e c o e f f i c i e n t s of x

o n b o t h s i d e s of (3), w e g e t
k' = A k'
+B k .
n
n n- 1
n n- 1

which gives

k1 ,

(6)

B =
n

*
n-l

*tl
n-l

52

A NOTE ON ORTHOGONAL POLYNOMIALS

Feb.

But

A =
n

n-1

so that (6) can be w r i t t e n a s

k1
n

(7)

n-1
n- 1

n-1

Let D* denote the d e t e r m i n a n t obtained by deleting the

row and the nth column of D

Then
D*
n

kfn = -

JlDD
^

Substituting for

Jyj

Using the value of B

<U >

n-1

D D
n

+ -ill
D

n-1

n-

n-2

given by (8) in (5), we obtain

D*

(9)

n n-1

k , k' and k' . in (7), we get

n
n
n-1
D

(8)

(n+l)th

D* ,

n-J.

, I

n-Z

n-l

(x)

n-1
D

n-3

V2(X)

n-2

Thus (9) gives the r e c u r r e n c e r e l a t i o n for orthogonal polynomi a l s a s s o c i a t e d with the density function
m o m e n t s of f(x).

f(x) explicitly in t e r m s of the

The r e c u r r e n c e r e l a t i o n (9) is valid a l s o for

if we set DJT = 0, D ,

1 and D

n =1

= 0.

If the density function f(x) is s y m m e t r i c a l about x = 0, that i s ,

if f(-x) = f(x) and a = - b , then
= 0

"1 "
3 '
i i A 2r+l
' *
If the odd o r d e r m o m e n t s a r e all z e r o , we shall prove below in
T h e o r e m 1 that D* v a n i s h e s for n = 1, 2, . . . which will imply that
B = 0 for n = 1, 2, . . . .
n
We shall a l s o p r o v e below in T h e o r e m 2 that, in this c a s e , the
polynomials
or odd.

q (x) a r e even or odd function a c c o r d i n g as n is even

1966

A NOTE ON ORTHOGONAL POLYNOMIALS

53

The r e c u r r e n c e r e l a t i o n for orthogonal polynomials a s s o c i a t e d

with the s y m m e t r i c a l d e n s i t y function

f(x) is then obtained as

q (x) = xq
(x) ^n
n-1

(10)

D
D n-1 n - i
D

V2(X)

n-2

In p a r t i c u l a r , for n = 0, 1, 2, 3, and 4, the orthogonal polyn o m i a l s a s s o c i a t e d with the s y m m e t r i c a l density function f(x) a r e
obtained as foLlows:
q 0 (x) = 1
q x (x) = x
q 2 (x) = x'
q 3 (x) = x~

2m6'm4
x +
z_
m
4"'m2
m4-m2
We now p r o v e the following two T h e o r e m s :
d.. b e a n (n x n) m a t r i x w h e r e
T h e o r e m 1. Let D

d.. = 0 for

i+j odd, and d.. is a r b i t r a r y for i+j even.

(n- l)x(n-1) <

q 4 (x) = x

6'mZm4
2_

Let D* b e a n

m a t r i x obtained by deleting the uth row and the vth column of D

such that u+v is odd.
Proof.

Then the d e t e r m i n a n t of D* is z e r o .

To prove the t h e o r e m we c o n s i d e r two c a s e s :

(1) n even and

(2) n odd.
Case 1

n = 2k (even)

Let us a s s u m e that we get D* by deleting an odd row and an

even column.

Then by shifting rows and columns of D*, we obtain

1

D** =
A.

A.

54

A NOTE ON ORTHOGONAL POLYNOMIALS

where

D## is a m a t r i x of (2k- l ) x ( 2 k - l )

Feb.

e l e m e n t s and

A, = k x k m a t r i x with z e r o e l e m e n t s
A ? = k x (k-1) m a t r i x with a r b i t r a r y e l e m e n t s
A~ = (k-1) x k m a t r i x with a r b i t r a r y e l e m e n t s
A . = (k-1) x (k-1) m a t r i x with z e r o e l e m e n t s .
If we now take the Laplace expansion of D#* by (k x k) m i n o r s ,
then it can be e a s i l y s e e n that the d e t e r m i n a n t of D## is z e r o , which
will imply that the d e t e r m i n a n t of D* is z e r o .
The r e s u l t a l s o follows if we take

D* by deleting an even row

and an odd column.

Case 2

n = 2k+l

(odd)

In this c a s e , we obtain
B

D## =
L
where

D## is a m a t r i x of (2k x 2k) e l e m e n t s and

B 1 = k x (k+1) m a t r i x with z e r o e l e m e n t s
B ? = k x (k-1) m a t r i x with a r b i t r a r y e l e m e n t s
B~ = k x (k+1) m a t r i x with a r b i t r a r y e l e m e n t s
B A - k x (k-1) m a t r i x with z e r o e l e m e n t s .
If we take the

Laplace

expansion of D** by (k x k) m i n o r s ,

then we shall have the d e t e r m i n a n t of D*# equal to z e r o , which will

i m p l y that the d e t e r m i n a n t of D* is z e r o .
T h e o r e m 2 Let q (x), defined by (2), be the orthogonal polynomials
a s s o c i a t e d with the density function
Then the polynomials
is even or odd.

f(x)

s y m m e t r i c a l about x = 0.

q (x) a r e even or odd functions a c c o r d i n g a s

1966
Proof

A NOTE ON ORTHOGONAL POLYNOMIALS

If the density function

55

f(x) is s y m m e t r i c a l about x = 0, then

all the odd o r d e r m o m e n t s a r e z e r o , that is

1

Zr+1

The proof of the t h e o r e m follows i m m e d i a t e l y by expanding p (x),

defined by (1), in t e r m s of the l a s t row of the d e t e r m i n a n t and making
u s e of the r e s u l t of T h e o r e m 1.
REFERENCE
I !

1.

Szego, G. , Orthogonal P o l y n o m i a l s , r e v . ed. , A m e r . Math.

Soc. Colloquium P u b l i c a t i o n s , Vol. 23, New York, 1959.
XXXXXXXXXXXXXXX

These booklets a r e now available for p u r c h a s e .

Send all o r d e r s to:

B r o t h e r U. Alfred, Managing E d i t o r , St. M a r y ' s College, Calif. 94575

(Note.

This a d d r e s s is sufficient,

since St. M a r y ' s College is a post

office. )
Fibonacci D i s c o v e r y

$1.50

Fibonacci E n t r y Points I

$1.00

Fibonacci E n t r y Points II

$1.50

C o n s t r u c t i o n s with B i - R u l e r & Double Ruler

by Dov J a r d e n
P a t t e r n s in Space by Re S. B e a r d

$5.00
$5.00

ADVANCED PROBLEMS AND SOLUTIONS

Edited by Verner E. Hoggatt, Jr.
San Jose State College, San Jose, California

Send all c o m m u n i c a t i o n s c o n c e r n i n g Advanced P r o b l e m s and

Solutions to V e r n e r E. Hoggatt, J r . , M a t h e m a t i c s D e p a r t m e n t , San
J o s e State College, San J o s e , California.

This d e p a r t m e n t e s p e c i a l l y

w e l c o m e s p r o b l e m s believed to be new or extending old r e s u l t s .

Pro-

p o s e r s should submit solutions or other information that will a s s i s t

the e d i t o r .

To facilitate their c o n s i d e r a t i o n , solutions should be sub-

m i t t e d on s e p a r a t e signed s h e e t s within two months after publication

of the p r o b l e m s .
H - 7 8 \Proposed by Verner E. Hoggatt, Jr., San Jose State College, San Jose,

California

00

(i)

show

11

where

(n)

(m,)xm,

>

x;

( n > 1)

m=0

a r e the binomial coefficients.

See "Diagonals of P a s c a l ' s

T r i a n g l e " , D. C. Duncan, pg 1115, AMM, Dec. 1965.

(ii)

Show

^~ =
1-x-x

[ Xia ]

xm

m=0
x

23
l - 2 x - 2 x +x_

' r 1 ^!

[?]

m=0

00

^ ,
X

l - 3 x - 6 x +3x +x
where

ion

^
m=0

rm-i

] a r e the F i b o n o m i a l coefficients as in H - 6 3 , A p r i l 1965,

F Q J and H-72 of Dec. 1965, F Q J .

The, g e n e r a l i z a t i o n i s :

Let

x m

y>

( _ 1 } h(h+i)/2

j-k. ^h

f(x) = 2 ^ , ( - l r ' " 1 * " " L J

h=0
56

1966

ADVANCED PROBLEMS AND SOLUTIONS

57

then show
k-1
x
=
f(

xT

r m -i

'm

[kmiJ x ^>

<k^ D

m=0
H-79

Proposed by J.A.H. Hunter, Toronto, Ontario, Canada

Show
4

H-80

4
4
. - 2
n^>
_,, + F + F
. = 2 f2F
+ (-1)1
J
n+1
n
n-1
*- n

Proposed by J.A.H. Hunter, Toronto, Ontario, Canada and Max Rumney, London,

England

Show

L o *? - E <";'' t
r2
J

2r+5

r=0

H-81

'

r=0

Proposed by Vassili Daiev, Sea Cliff, N.Y.

Find the

nth

t e r m of the sequence

1 , 1 , 3 , 1 , 5 , 3 , 7 , 1 , 9 , 5 , 1 1 , 3, 1 3 , 7 , 1 5 , 1 , 17, 9, 1 9 , 5 , . . .
H-82

Proposed by Verner E. Hoggatt, Jr., San Jose State College, San Jose,
If

fn(x) = 0 and
0

Tan

H-83

f. (x) = 1,
1

,~(x) = xf , . (x) + f (x)

n+2v
.n+1
n

I = V Tan'1 (f

* ..)

Proposed by Mrs. William Squire, Morgantown, West Va.

Show
i - m + I -i

L ~2"J
\"^

ixt-l

.m-t,

m+l-2t

t=i

where

[xj

is the g r e a t e s t integer functionc

California
then show

58

ADVANCED PROBLEMS A N D SOLUTIONS

Feb.

SOLUTIONS
T H E L O S T IS F O U N D
H-42

Proposed by J.D.E. Konhauser, State College,

Pa.

A set of nine i n t e g e r s having the p r o p e r t y that no two p a i r s have

the s a m e sum is the set consisting of the nine consecutive Fibonacci
n u m b e r s , 1, 2, 3, 5, 8, 13, 21, 34, 55 with total sum 142.

Starting with

1, and annexing at each step the s m a l l e s t positive i n t e g e r which p r o duces a set with the stated p r o p e r t y yields the set 1, 2, 3, 5, 8, 13, 21,
30, 39 with sum 122

Is this the b e s t r e s u l t ?

Can a set with lower

total sum be found?

Solution by Frank Urbanija, Student, St. Joseph High School, Cleveland,

Ohio

The following solution is submitted:

1, 2, 3, 5 , 7 , 15, 20, 2 5 , 4 1 ,
the sum of which is 121
E d i t o r i a l Comment:

This is the m i s s i n g solution and the b e s t r e -

ceived to d a t e .

A BETTER P R O B L E M SOLUTION
H-74

Proposed by Douglas hind, University

of Virginia, Charlottesville,

Va.

Let f(n) denote the n u m b e r of positive Fibonacci n u m b e r s not

g r e a t e r than a specified i n t e g e r

n.

Show that for n > 1

f(ii) = [ K l n ( n A + j ]
where

j xl

'

denotes g r e a t e s t i n t e g e r not exceeding x, and K is a

constant n e a r l y equal to 2.078086943. (See H. W. Gould's N o n - F i b onacci N u m b e r s , Oct. 1965, F Q J ) .

Comments by John D. Cloud, Manhattan Beach,

California

P r o b l e m H-74 in the Dec. 1965 i s s u e of the Fibonacci Q u a r t e r l y

is not new.

I p r o p o s e d the s a m e p r o b l e m in the Nov. 1963 i s s u e of

the A m e r i c a n M a t h e m a t i c a l Monthly (Vol. 70, No. 9, p. 1005, p r o b .

E l 636). A m o r e p r e c i s e solution than the one indicated by M r . Lind
in the FQ a p p e a r s o n p . 798 of the AMMfor Sept. 1964 (Vol. 7 1 , No. 7).

1966

ADVANCED P R O B L E M S AND SOLUTIONS

59

T h e s o l u t i o n by W i l l i a m D* J a c k s o n a l l u d e d t o s h o w s :
The n u m b e r

of F i b o n a c c i n u m b e r s n o t g r e a t e r t h a n

g r e a t e s t integer less than

log[(N + ~ ) / 3 ]
I
i
/ i + VST
log ( )

xxxxxxxxxxxxxxx
A FIBONACCI CROSSWORD PUZZLE
H.W. Gould
West Virginia University

N is the

60

ADVANCED P R O B L E M S AND SOLUTIONS

Feb.

ACROSS
2

A k i n d of n u m b e r d i s c o v e r e d by 1 7 D o w n of 22 Down w h i l e s t u d y i n g 50 A c r o s s .

Series (French).

A r i v e r in K a n s a s and M i s s o u r i .

12

S m a l l e s t n u m b e r i n t o w h i c h e a c h of t w o n u m b e r s w i l l d i v i d e .

14

The s m a l l e s t n a t u r a l n u m b e r ( F r e n c h ) .

15

One m o r e t h a n a p e r f e c t

16

O c c u r r e n c e of F i b o n a c c i n u m b e r s i n n a t u r e .

20

lim

square.

(1 + l / n ) n .

21

n*- oo
Device s o m e t i m e s u s e d to g e n e r a t e r a n d o m n u m b e r s .

23

C o m b i n i n g f o r m of " C h i n e s e " .

26

L e t t e r u s e d to d e n o t e a f a m o u s n u m b e r

27

S i g n of d i f f e r e n t i a t i o n .

28

B r o t h e r of A b e l .

29

Iron.

31

The numbers 1, 3, 4, 7, 1.1, ... are

32

Girl's name.

33

M e a s u r e of i n t e l l i g e n c e ( t h e y s a y ) .

35

Chemical element.

36

39
41

,, = F + F
is an e x a m p l e .
n+1
n
n-1
Roman emperor.
(eX + e " x ) / 2 .

43

Amateur.

44

Latin connective.

45

Utilizes.

46

S q u a r e r o o t of m i n u s o n e .

47

If n

is a natural n u m b e r ,

then

numbero
49

Bitter Vetch0

50

S t u d i e d i n 1202 A D b y 2 A c r o s s .

51

T h r o w s out.

n+1

sequence.

numbers.

is the

natural

1966

ADVANCED P R O B L E M S AND SOLUTIONS

61

DOWN
1

The first d e g r e e .

Battle.

F a m o u s m a t h e m a t i c i a n w h o w r o t e n o v e l s u n d e r the n o m de p l u m e
John Taine.

Definite a r t i c l e ( A r a b i c ) .

Cone-shaped.

A f o r m of t h e c o p u l a .

B a s e of t h e d e c i m a l s y s t e m .

10

Preposition.

11
13

2-1
The function x(l - x - x )
"
" the
In f a c t , a F i b o n a c c i n u m b e r i s t h e
2-1
s e r i e s e x p a n s i o n of x ( l - x - x )

16

Discovered a famous

Fibonacci numbers.
of x
in the p o w e r

triangle named after him.

Known e a r l i e r

to t h e C h i n e s e .
17

A n o t h e r n a m e of 2 A c r o s s .

18

One of t h e s i m p l e s t w a y s to c o m b i n e n u m b e r s .

19

T h e n u m b e r s 1, 1, 2, 3, 5, 8, . . .

22

A town in Italy.

24

An adjectival

25

A f a m o u s g a m e w h o s e t h e o r y i s b a s e d on t h e b i n a r y s y s t e m .

30

W h a t o n e u s u a l l y d o e s w i t h 13 D o w n i n o r d e r to d i s c o v e r a r e l a -

form a

suffix.

tion.
34

City in ancient S u m e r .

37

C h e m i c a l e l e m e n t d i s c o v e r e d in Y t t e r b y ,

38

A b b r e v i a t i o n f o r a t r i g o n o m e t r i c a l f u n c t i o n ; c o u n t e r p a r t of 41

Sweden.

Across,
39

Man's nickname0

40

A p e r s o n w h o m i g h t l i v e n e a r 40 E . L o n g . , 22 N .

42

To m a k e a s h a r p s i b i l a n t s o u n d .

43

Black substance obtained from coal.

45

A n I n d i a n of t h e S h o s h o n e a n t r i b e s D

48

T h e U n k n o w n Quantity.,
XXXXXXXXXXXXXXX

Lat.

62

Feb.
CORRECTIONS

"A Variant of Pascal's Triangle" by H. W. Gould, FQJ Vol. 3, Dec.

1965:
Page 265, line 6, for (6.7) read (6.6).
Page 268, relation (7. 14): Left-hand member should read
n+1 n+b
Page 268, line 5 up from bottom:

n n+b+1
Right-hand member should read

(~l)n(K
K - KnK , J
' x a b
0 a+b

and line 3 up from bottom:

Right-hand member should read

Page 269, line 1: Right-hand member should read

and line at bottom of page 269: In right-hand member for
read

K . ,, .
n+a+b

"Power Identities for Sequences Defined by W , ? = dW

. -c

by David Zeitlin, FQJ Vol. 3, No. 4, 1965

Page 245.

Line 2 of (3# 1) should read

rn

+ (mq(4r-q-l)/2)

Page 246. The factor, c

page.

r / ) (4c-d2)

q-r

^ , was omitted from the first line of the

Page 247. The factor, p

, was omitted from the last line (on the
right hand side) at the bottom of the page.
Page 250. In line (1) of (3.16), the exponent of c should read
(r-l)n Q + i 2 r _ 1 .
Page 250.

In line (2) of (4.3), (-5) q

Page 251. In (4. 8),

Page 254.

+4 should read

should read

(-5) q " r

-4.

The second line in (5. 9) begins with a + sign.

XXXXXXXXXXXXXXX

ON THE INTEGER SOLUTION OF THE EQUATION

Sx^ + 6x + 1 = y2
AND SOME RELATED OBSERVATIONS
Edgar I. Emerson
Boulder, Colorado

The integer solution of the equation

5x26x+l = y 2

(1)

is interesting because of the Fibonacci and Lucas relationships that

appear.
One method of solving the problem involves the solution of the
Pythagorean* (Py) equation
(2)
where

?
2
?
X + Y = 2T ,
2
2
2
2
X = 2ab, Y = a - b , Z = a + b s and a > b.

Since no other

restrictions are placed on a and b this solution of (2) is not necessarily primitive.
When 4x
is added to both sides of (1) we obtain
(3)

9xZ6x+l = y 2 +4x 2

(4)

(3xl) 2 = y 2 +(2x) 2

(5a)

3xl = Z = a 2 + b 2 ,

(5b)

y= Y = a 2 - b 2

and

(5c)

2x = X = 2ab

or

(5d)

x = ab.

or
.

Now let

Substituting this value of x in (5a) we get

2
3ab 1 = a

or

a 2 - 3ab + (b 2 1) = 0 .

(6)

Solving this equation for

(7)

2
+b

a =

a > b we have

3b + / 9 b 2 - 4(b 2 l)
3b + V 5 b 2 4
*
L =
2
2
63

ON THE INTEGER SOLUTION O F THE EQUATION

64

2
If the values of b a r e such that 5b
ways even and t h e r e f o r e

Feb.

/
2
4 = Q then 3b + * 5b 4 is a l -

a is always i n t e g r a l .

Changing equation (7)

to
2
2a = 3b + V5b 4

(8)

we p r e p a r e Table I by filling in the column under

numbers,

number's, L.

The r e s t of the table is then c a l c u l a t e d .

Table I

'

n+2'

b with the Fibonacci

F , and the column beneath the r a d i c a l sign with the Lucas

Showing F i b o n a c c i and Lucas R e l a t i o n s h i p s

Involved in the Solution of
2
2
5x 6x+l = y
3b+ V 5b 2 4;
2a
2 = 0+2

y=a2-b2

x=ab;

n,

a,

0,

1,

1,

2,

2,

3,

4=3+1
6=3+3

10

21

0
2

3,

5,

10 = 6 + 4

4,

8,

16=9 + 7

24

55

5,

13,

26 = 15 + 11;

65

144

6,

21,

42 = 24 + 18;

168

377

n;

2F

n+2=3Fn+Ln; ^ l " * "

=

>"= F n F n + 2 ;

!+2"Fn=

2n+2

<Ln+l-Fn+l)/4;=Ln+lFn+l

Note that x +x ,. = F 9 ,~ = F 2
+F2
n n+1
2n+3
n+1
n+2
The solution to equation (1) is
(9)

(10)

,~ = 2(x , +x 9 ) - x
= F 2 , , - ( - l ) n = F n *.
Fn+2
n-1 n - 2 '
n-3
n+1
=

?~F

4-9

4.1F

4.1

i-y

7
n
n+2 n
2n+2
n+1 n+1
n-l
F r o m (9) we have the i n t e r e s t i n g r e c u r r e n t equation

= 2(x
n

+x
n-1

) - x
n-2

,
n-3

n-2

2
1966

5x

2
6x + 1 = y

AND SOME R E L A T E D OBSERVATIONS

65

w h i c h c a n be e x p r e s s e d w i t h F i b o n a c c i t e r m s a s :
(ID

F2

The

(-1)

+ 1

-(-l)n=2[F2-(-l)n-

+ F

2_

r (

1 )

n-2].

[ F

2^_(_

F2X1 = 2F2 + 2F2 _ - F2 ,

n+1
n
n-1
n-2

or

F2
- F 2 , = ( F 2 - F 2 9) + ( F 2 + F 2 .)
x
n+1
n-1
n
n-27
n
n-17
F9 = F9
- + F0
,
Zn
Zn-Z
Zn-1
F

2n

= F

or

E q u a t i o n (12) c a n b e w r i t t e n a s

2 ( F 2 + F 2 .) = F 2 _ u l + F 2 9
x
n
n-1
n+1
n-2
2F9
. = F2,.+F2 ?
2n-1
n+1
n-2

(13)
interesting

Fibonacci

identity-

t u t e d i n e q u a t i o n (8), 2 a = 3b + ^ 5 b 4 .
2F

or

Another interesting

identity t u r n s up when the a p p r o p r i a t e

(14)

and

L terms are substi-

We h a v e

3F

t o e a c h s i d e of t h e i d e n t i t y

, + F ,, = L
as follows:
n-1
n+1
n
.+F , , =
n-1
n+1

L
n

F +F +F = 3F
n
n
n
n
F +(F +F
, ) + ( F , . + F ) = 3 F +L
n
n
n-1
n+1
n
n
n
(F +F

Fibonacci

,- = 3 F +L
n+Z
n
n

This identity is p r o v e d by adding

or

2n

a n d t h u s w e h a v e p r o v e d (11) a n d (1 2 ) .

n-3

t e r m s d i s a p p e a r so that

(12)

an

1 )

)+F

1 7
n+1

n+29

= 3F

F ^.,+F ^ = 3 F +L
n+2
n+2
n
n
2 F ^ 9 = 3 F +L
n+Z
n
n

+L

66

ON THE INTEGER SOLUTION OF THE EQUATION

Feb.

Equation (1) can be written as

2
5x 2 + 6 ( - l ) n x + 1 = y
J
n
n
n

(14)
v
'

and when the appropriate

F t e r m s a r e substituted, this equation be-

comes
5F F
+ 6(-l)nF F
+1= F
K
n n+2
'
n n+2
2n+2

(15)

K D)

which equation is equivalent to

(16)
N
'

5F2 , F 2 , - 6(-l)nF
.F x l + 1 = F2
n-1 n+1
n-1 n+1
2n

(17)
1

5Lr F 2 + ( - lJ) n l
n

n
-6(l)
fF 2 + ( - l ) n 1
l ,
L n x / J

or

+ 1 = F2 = L2F2
2n
n n

When the indicated operations a r e performed we have successively

5rF4+2(-l)nF2+(-l)2n]
L
n
'
n s ' J

-6(-l)nrF2+(-l)nl
.
' L n * ' -J

5F4 + lQ(-l)nF2 + 5 -6(-l)nF2 -6(-l)2n

n
'
n
n

+ 1 = L2F2
n *n

+ 1 = L2F2
n n

5F4 + 4(-l)nF2 = L2F2

n
n
n n
5 F 2 + 4 ( - l ) n = L2
n
n
and thus we have proved the identities (16) and (17).
2
2
2
Now we examine the solution of equation (2), X + Y = Z , where
F and L t e r m s a r e used for (a) and (b). For this purpose we first
prepare Table II where the a's

and b's

a r e transferred from Table I.

The r e s t of Table II is then calculatedo

The solution of X 2 + Y 2 = Z 2
(18a)

is

X = 2ab = 2F F I O
n n+2
Y = a2-b2 = F2
- F 2 = F9 , 9
n+2
n
Lxi-rL
Z = a 2 +b 2 = F 2
+F 2 = 3 F 2 X 1 - 2 ( - l ) n
n+2
n
n+1
'

2
1966

5x

2
6x + 1 = y AND SOME R E L A T E D OBSERVATIONS

Table II

Showing Fibonacci and Lucas Relationships

Involved in the Solution of X 2 +Y 2 = Z 2

X = 2ab, Y = a 2 - b 2 , Z = a 2 + b 2 , a = F , 0 , and b = F
a,

b,

o,

1,

2,

3,

20

4,

5,

13

6,

21

n+2

-a 2 -b 2 =Y,

2ab=X,

n,

n, F

a +b = z,

a-b,

a+b
1

10

21

29

48

55

73

11

130

144

194

18

336

377

505

13

29

2F F
n n +2'

,F ,
n

[ Fln-^

The identity (18c), F . ? + F

F2-F2 ,
n n+2
F

Li+l-Fn+l)/2''

2n+2'

n+lFn+r

2 2
F ^ + F ^ +2 5 F n + 1 '
n n
n+1
n+1)A
^ I v

but

F . 1 F . 1 = F2+(-l)n
n+1 n - 1
n

and

F , = 2F2+2(-l)n
n+1 n~1
n
tl

and t h e r e f o r e

F 2 +F2 . = 2F , . F . + F 2
n+1 n-1
n+1 n-1
n

or

F2
-2F , . F ,+F2
= F2
n+1
n+1 n-1
n-1
n

or

(F , . - F , ) 2 = F 2
n+1 n-1
n
F
-F , = F
n+1 n-1
n
F ,. = F +F .
n+1
n
n-1

n-

= 3 F ,, - 2 ( - l ) , is equivalent to

F 2 +F2 , = 3F2+2(-l)n
n+1 n-1
n

2F

(19)

67

or
or

68

ON THE INTEGER SOLUTION OF THE EQUATION

and thus we have p r o v e d the F i b o n a c c i identity for

2 2
2
An equivalent equation for

+ Y

= Z

Feb.

Z in (18c).

is the following F i b -

onacci identity:

<2o>

c^+i-<"Mn]2

+F

L+2 = i^+i-^nz

When the indicated o p e r a t i o n s a r e p e r f o r m e d and the t e r m s a r e collected this equation b e c o m e s

5F4
n+1

_4(_i)nF2
= F 2
l
}
^n+1
2n+2

or

5F4+4(-l)nF2 = F2 = L2F2
'n
n
2n
n n

or

5 F 2 + 4 N( - l ) n = L 2
n
n
a n d t h u s we h a v e p r o v e d the F i b o n a c c i i d e n t i t y e x p r e s s e d by e q u a t i o n
(20).
The following equations r e p r e s e n t f u r t h e r

observations.

(21)
x
'

Z+X = a 2 + 2 a b + b 2 = ( a + b ) 2 = x( F , - + F ) 2 = L 2 ,
'
n+2
n
n+1

(22)
x
'

Z - X = a 2 - 2 a b + b 2 = ( a - b ) 2 = ( F ^-F
'
n+2
Adding t h e s e e q u a t i o n s and dividing by

(23)
v
'

2 we have

Z = v( L 2
+F2
)/2
n+1
n+1"

a n d s u b t r a c t i n g the e q u a t i o n s and dividing by

2 we get

(24)

X=

(L^-F ,,)/^
n+1
n+1 '
a n d m u l t i p l y i n g (21) by (22) w e o b t a i n
(25)

Z2-X2=L^+1F2+1

< 26 >

Y = L

T h e a r e a , A, of t h e

(27)

)2 = F 2
n+1

Py

'

triangle is

A = ab(a2-b2)

Y2

and
..

2
6x + 1 = y AND SOME R E L A T E D OBSERVATIONS 69
2 2
In g e n e r a l , the module, ab(a - b ), is divisible by 6, consequently
when the a p p r o p r i a t e F a n d / o r L t e r m s a r e substituted in the m o d ule the r e s u l t i n g e x p r e s s i o n m u s t likewise be divisible by 6. Thus
the following e x p r e s s i o n s a r e all divisible by 6:
1966

5x

F F , ,%( F 2 - F ? ) ;
n n+2 n+2 n

L[

F 2 - ( - l ) n Jl L["F2 - F 2 T
;
n+1
n+2
nJ

F F
F
L
F F
F

n n+1 n+2 n+1 '

n n + 2 r 2n+2 '

C F n + r<-^ n ] F 2n + 2

0 ^ + 1 - ( - l ) n ] F n + l L n+1

( L 2 - F 2 ) L , . F ,,
n+1 n+1 n+1 n+1

and

(Ln+l-Fn+l)F2n+2
(Ln+rFn+l^Fn+2-Fn)
a r e all divisible byy 24 since ab = s(Ln+1
,, - F n+1
. ,, )' / 4 ;
In the foregoing c o n s i d e r a t i o n s the values of a and b w e r e
r e s t r i c t e d by equation (1) to a = F

~, b = F .

tion of a P y t r i a n g l e , we substitute for

and/or

If now, in the solu-

a and b any a r b i t r a r y

L t e r m s then Fibonacci a n d / o r Lucas n u m b e r i d e n t i t i e s a r e

e a s i l y produced in infinite v a r i e t y and divisibility e x p r e s s i o n s a r e

e a s i l y produced and p r o v e d .
XXXXXXXXXXXXXXX

STAR GEOMETRY
Pythagoras, Fibonacci and Beard
R.S. Beard

The diagonal of the pentagon is made the unit of length in the

upper left c i r c l e of the accompanying d r a w i n g s .

K is the r a t i o of the

side of the pentagon to its diagonal.

Line 4. 3 is the s h o r t side of t r i a n g l e 1-4-3 and the long side of
triangle 3-4-6.
Line 4. 6 is the s h o r t side of t r i a n g l e 3-4-6 and the long side of
triangle 4-6-7.
T h e r e f o r e the sides of t h e s e t h r e e s i m i l a r i s o s e e l e s t r i a n g l e s
2
2
3
a r e r e s p e c t i v e l y 1 and K, K and K , K and K . Lines 1-6 and
3-6 have the s a m e length, K, as they a r e the equal sides of the i s o s c e l e s t r i a n g l e 1-3-6. Diagonal 1-4 of unit length is thus divided into
2
2
s e g m e n t s K and K , that is K + K = 1.
It follows from this equation that
K = \\HT-

i = 0.618034

and that K n = K n + 1 + K n + 2 .
Since each power of K is the sum of its next two higher p o w e r s ,
t h e s e powers form a Fibonacci s e r i e s when a r r a n g e d in t h e i r d e s c e n d ing o r d e r .
The r a d i u s is m a d e the unit of length in the upper right c i r c l e .
2
S i m i l a r t r i a n g l e s divide r a d i u s O - l into s e g m e n t s K and K . This
c o n s t r u c t i o n d e m o n s t r a t e s that each side of a r e g u l a r decagon has the
golden section r a t i o to the r a d i u s of its c i r c u m s c r i b i n g c i r c l e .
The right t r i a n g l e in the lower c i r c l e has sides of 1, 1/2 and
1 / 2 V 5 7 The d i m e n s i o n K with the value of 1 / 2 V 5 - 1 / 2 is the length
of the side of the i n s c r i b e d decagon.
The leaf shaped figure shows one simple way to c o n s t r u c t a five
pointed s t a r of a given width.
The Fibonacci s t a r of s t a r s is proportioned in the ten s u c c e s s i v e
0
9
powers of the golden section from K to K .
70

1966

STAR GEOMETRY.

PYTHAGORAS,

71

72

FIBONACCI AND BEARD

Feb.

AB is m a d e the unit of length or K .

AC, the side
The side

of the bounding pentagon h a s the length of K.

of each r a y of the m a s t e r s t a r is K

long.

3
The bounding pentagon of the c e n t r a l s t a r h a s sides of K length.
Since one diagonal of each of the s m a l l e r s t a r s is a side of the
bounding pentagon of the next l a r g e r s t a r all of the c o r r e s p o n d i n g d i m e n s i o n s of these s u c c e s s i v e s t a r s a r e in golden section r a t i o .
The bounding pentagons of the s u c c e s s i v e s t a r s have s i d e s of
K , K , K

and K

respectively.

8
The r a y s of the s m a l l e s t s t a r s have K edges and base widths

of K 9 .
This figure can be used to d e m o n s t r a t e that any power of the
golden section K , is the sum of a i l of its higher powers from

to K.
The lines connecting the tips of the c e n t r a l s t a r and the c e n t e r s
of the five next s m a l l e r s t a r s form a decagon.
XXXXXXXXXXXXXXX

RENEW YOUR SUBSCRIPTION! I I

All s u b s c r i p t i o n c o r r e s p o n d e n c e should be a d d r e s s e d to B r o t h e r U.
Alfred, St. M a r y ' s College, Calif. All checks ($4.00 p e r y e a r ) should
be m a d e out to the Fibonacci A s s o c i a t i o n or the Fibonacci Q u a r t e r l y .
M a n u s c r i p t s intended for publication in the Q u a r t e r l y should be sent
to V e r n e r E . Hoggatt, J r . , M a t h e m a t i c s D e p a r t m e n t , San J o s e State
College, San J o s e , Calif. All m a n u s c r i p t s should be typed, doubles p a c e d . Drawings should be m a d e the s a m e size a s they will a p p e a r
in the Q u a r t e r l y , and should be done in India ink on e i t h e r vellum or
bond p a p e r . A u t h o r s should keep a copy of the m a n u s c r i p t sent to the
editors.

PROPERTIES OF THE POLYNOMIALS DEFINED BY MORGAN-VOYCE

M.N.S. Swamy
Nova Scotia Technical College, Halifax, Canada

1.

Introduction

In dealing with e l e c t r i c a l ladder n e t w o r k s , A. M. Morgan-Voyce

defined a set of polynomials by:
(1)

b n (x) = x B n _ 1 (x) + b n _ x (x)

(n > 1)

(2)

B n (x) = (x + 1)

( n > 1)

Bn-1(x) + bn-1(x)

with,
b Q (x) = B Q (x) = 1

(3)

These polynomials
J

and B have a n u m b e r of v e r Jy f a s c i n
n
nating and i n t e r e s t i n g p r o p e r t i e s , and is the subject m a t t e r of this
article.

A few p r o p e r t i e s of t h e s e have been studied by Basin.

F r o m (1) and (2) we see that

(4)

= B

.
n~l
(5)
and,
x B = b ,, - b
n
n+1
n
Substituting (4)'in (1) we have that B s a t i s f i e s the difference equan

- B

tion,
B n (x) = (x + 2)

B n _ x (x) - B n _ 2 (x)

(n > 2)

with
(6)

B Q (x) = 1,

and B ^ x ) = x + 2

F r o m (1) and (2) it can e a s i l y be d e r i v e d that b (x) a l s o s a t i s f i e s the

s a m e difference equation, n a m e l y ,
b (x) = (x + 2)
n

, (x) - b ? (x)
n-1
n-2

with
(7)

b (x) = 1,

and b ^ x ) = x + 1
73

(n > 2)

P R O P E R T I E S OF THE POLYNOMIALS

74

The difference

Feb.

e q u a t i o n (6) m a y be e x p r e s s e d a s t h e c o n t i n u a n t ,
x+2

x+2

x+2

0
0

B (x)
n

(8)

0
1
0
and h e n c e we m a y study the p r o p e r t i e s
continuants.

of

x+2

(n > 1)

by u s i n g t h o s e of t h e

We s h a l l l i s t b e l o w o n l y s u c h of t h o s e p r o p e r t i e s of

w h i c h we w i l l u s e in studying
t h e sr
p o l yj n o m i a l s

b n (x)

(9)

and

b (x)

and in d e r i v i n g r e l a t i o n s b e t w e e n

B n (x):
B

, = B
m+n
m

- B

,
m-1

n-1

B, = B2 - B2 .
2n
n
n-1

(10)
(11)

(12)

(x
+ 2)
v
'

(13)

,
n-1

x(B

- B

)
n - 27 '

B9
, = B~
3 2 - B" 9
2n-l
n
n-2
n
B

2n-1

,xl
r-h+1

(14)

B
B

n-1

n-h+1

,, - B
n+1
n

h-2

n-r- 1

n-1
(15)

2.

dx

B (x) =

(B

n -i l - r )'

R e l a t i o n s b e t w e e n b (x) a n d B (x), a n d p r o p e r t i e s of b (x):

n
n
n
F r o m (5) a n d (7),

(16)
Also we have,

B (x)

(x + 1) b

- b
n-1

1966

DEFINED BY MORGAN-VOYCE

(17)

B ,. - B . = b \ _ + b
n+1
n-1
n+1
n

75

F r o m (4) and (5),

(18)

- b
= x (B + B _)
n+1
n-1
n
n-1
By s u c c e s s i v e l y substituting 0, 1, 2, . . . for

in (5) and

adding we have,
n
19

< >

Br=bn+l - 1
0

S i m i l a r l y from (4) we m a y deduce that,

(20)

V
b = B
LJ r
n
0

Now,
b

,_ = B , - B , 1 = (B B - B
,B , ) - ( B B . -B
, B J)
m+n
m+n m+n~l
m n
m - 1 n-1
m n-1
m - 1 n-Z
= B

(B
m

- B
n

J - (B , - B 9 )
n-1
n-1
n-2

,
m-1

Hence,
(21a)

= B b - B
.b m+n
m n
m - 1 n-1
Interchanging m and n we have,
(21b)

, =b B - b
.B .
m+n
m n
m-1 n-i

Hence,
(22)
x
'

b B - B b = b
,B , - B
,b ,
m n
m n
m - I n-1
m - 1 n-1

We will see l a t e r that this is a p a r t i c u l a r c a s e of the m o r e g e n e r a l

r e l a t i o n s h i p (29).
Putting m = n in (21),
(23)

b^ = b B - b ..B ,
Zn
n n
n-1 n-1

Putting m = n+1 in (21),

76

P R O P E R T I E S OF THE POLYNOMIALS

(24a)
x
'

Feb.

b9 xl = b X1B - b B '
2n+l
n+1 n
n n-1

(24b)

= B

..b - B b
.
n+1 n
n n-1

F r o m (7) w e h a v e
(x + 2) b 9 ,, = b 9 , 9 + b 9
2n+l
2n+2
2n
b ^ B L1 - b B + b B
-b
_B
,
n+1 n+1
n n
n n
n-1 n-1
Hence,
(24c)
x
'

(x + 2) b 9 ,. = b , _ B ,. - b
B
,
' 2n+l
n+1 n+1
n-1 n-1

A l s o f r o m (12),
(x + 2) B 9 ,, = B 2 ,, - B 2 ,
'
2n+l
n+1
n-1
Hence,
(x + 2 ) ( B ? , 1 - b 9 ,, ) = B ,, (B , . - b ,, ) - B
, (B
, - b )
'
2n+l
2n+l
n+1 n+1
n+1
n-1
n-1
n-1
Hence,
(25)
'

(x + 2) B 0 = B . _ L 1 B - B
.B
2n
n+1 n
n-1 n-2

F r o m (23) a n d (24) w e d e d u c e t h a t ,
b9 - b9
. = b2 - b2
2n
2n-l
n
n-1

(26)

S u b t r a c t i n g (12) f r o m (25),
(x
+ 2 /)v( B 9 - B 9
J = B (B ,, - B ) - B 9 ( B
. - B
)
v
2n
2n-l
n n+1
n
n - 2 ' n-1
n - 29 '
Hence,
(27a)

(x + 2) b 0 = B b _,__ - B 9 b
.
2n
n n+1
n-2 n-1

(27b)

= b B
- b
_B
n n+1
n-2 n-1
We w i l l n o w d e r i v e a r e l a t i o n s h i p b e t w e e n t h e p o l y n o m i a l s

and

B (x), c o r r e s p o n d i n g to t h e r e l a t i o n (13) f o r
Consider the e x p r e s s i o n ,

B :

b (x)

1966

DEFINED BY MORGAN-VOYCE

77

B - B, 9 b
n-h+1 r
h-Z n - r - 1
(B , x l - B . )B - (B
,
n ~ r - 2 ' h-2
x
x
n-h+1
n-h' r
n-r-1
(B , , , B - B
B, 9 )
(B
B - B
B, 9 )
n-h+1 r
n - r - 1 h-2
n-h r
n - r - Z h-Z
from (13)
B B
n r-h+l ' Bn-lBr-h+l

= (B n - Bn - 1, )'B r-h+1
, , . = bn B r-h+1
, xl
Hence,
b B , ,. = b , , , B - B, 9 b
n r-h+1
n-h+1 r
h-2 n - r - 1

(28a)
Similarly,
(28b)

b B , x l = B , , . b - b, 9 B
,
n r-h+1
n-h+1 r
h-Z n - r - 1
Hence from (28a) and (28b) we get the r e l a t i o n ,

Changing

B r b n-h+1
,
n ,, - B, 0 b
h-2 n - r -n1 = b B , .- - b, 0 B
r n-h+1
h-Z n - r - 1
r to m, h - 2 to m - 4 , and n to m + n + l - r in the above

relation,
(29a)

B b - B
b
= b B - b
B
m n
m-r n-r
m n
m-r n-r
Using the r e l a t i o n (4) in (29a) we d e r i v e the c o r r e s p o n d i n g r e l a t i o n
for B (x) a s ,
n
(30a)

,
n-1

B
B
B
T = B B
,
1
n-r m-r-1
m-r n-r-1
n m-1
These r e l a t i o n s m a y be w r i t t e n n e a t l y in the form of d e t e r m i n a n t s :
m

m-r
b
m-r

m-1

Bm - r

(29b)
and
B

(30b)

n-r

n-r
m- 1 -r

B
n-r
n-1-r!
n- 1
Now putting h = 2, and n = r+1 in equation (28) we get,
(31)

b r B r - b r+1
, . B r - .i = 1

78

P R O P E R T I E S OF THE POLYNOMIALS

,Feb.

Putting m = n - 1 , and r = n - 1 in (29b) we get,

(32)
x
'

B b . - b B , =1
n n-1
n n-1
F r o m (31) and (32) we see that b (x) is p r i m e to b , (x), B (x)
n
^
n-1
n
and B , (x) for i n t e g r a l value's of x. Also, for i n t e g r a l values of x,
B x(x)' is ^p r i m e to B n - l, x(x),
.-.(x).
' bnx(x)' and b n+1
n
By s u c c e s s i v e l y substituting 1, 2, 3, . . for n in (10) and adding, we have
n
V B
L-J

= Bn2 - B02 = Bn2 - BCf

2r

1
Hence,
(33)

E B 2r

B2
n

0
Simi .larly, , using ( 1 1 ) , (23), (24) and (26) we d e r i v e :
n-1

(34)

2r+1

= Bn B n-1.

= b B
n n

0
n
E

(35)

2r

0
n-1

(36)

2r+l

= b B ,
n n-1

0
2n

2
("l)rbr = b
n

(37)

L e t us now find an e x p r e s s i o n for the d e r i v a t i v e of

n-1

b ' ( x ) = B 1 - B'
n
n
n-

n-2

B :
n- 1i - r
r

.i-L

At

B B

n-Z-r

n-2

n-2 B

*E

y
0

0
= Bn B
-1 0

b (x):
n

(B
r

.
, -B
o) = B , b n + Y^ B b
-r-1
n-r-2'
n-1 0 L*t r n - r - 1
0

1966

D E F I N E D BY M O R G A N - V O Y C E

79

Hence,
n-1

,w = E B

(38)

3.

E x p l i c i t p o l y n o m i a l e x p r e s s i o n s f o r B (x) a n d b (x):
We c a n e s t a b l i s h b y i n d u c t i o n t h a t ,
n
B (x) = V
(ck xk)
n
-*^
n
k=0

where,
(39)

k
n

,n+k+l,
n - ki )'

Now

b x(x) = B v(x) - B
, (x) = V
n
n
n-1
LJ

(39)

n+k,

- z a>

,n+k+l.
* n+k .
n-k ' ' *n-k-l'

0
Therefore we have

bn (x) = V
L-J

(dknk

k,

x )

k=0
where,
d

(40)

k
/n+k
= ( , x)
n
n-k *

T h e e q u a t i o n s (39) a n d (40 a r e e x p l i c i t p o l y n o m i a l e x p r e s s i o n s
for

and

B , a n d s h o w t h a t t h e yJ a r e of d e g r e e
n

We s h a l l n o w d e r i v e a f o r m u l a

for

B (x)

dx

n.

P R O P E R T I E S OF THE POLYNOMIALS

80

Feb.

F r o m (39),
n

/ >\l3n(x)

k+ k+1
dx = ^2 <ckn x k+1
V ) +c

Now the coefficient of x

k+1
-

J_i

"

n+1

k+1
i

n-1

k+1

for the e x p r e s s i o n
r

,n+k+3.
(

,n+k+L
"

n-k

->)

(n

B ,, - B , i s ,
n+1
n-1
, ,x k
l

n-k-2

- (n + 1)(coefficient of x

k+1

in j B (x) dx . )

Hence,
(41)

/ /B(x) dx =

n+

i ^1n"1

+c

It m a y a l s o be e s t a b l i s h e d that over the i n t e r v a l (-4, 0),

B (x)
n
and b (x) a r e orthogonal polynomials with r e s p e c t to the weight func-

tions

V 4 - <x + 2>2

and

V { x + 4)/-x

respectively

It m a y a l s o be seen from (6) that,

(42a)

B (x) = S (x+2)
n
n

and hence,
(42b)
where
4.

b (x) = S (x+2) - S . (x+2)

n
n
n-1

S (x) is the Chebyshev polynomial.

Conclusions:
The a r t i c l e deals with the p r o p e r t i e s of a set of polynomials

b (x)

and B (x) defined by (1), (2) and (3) Even though they a r e r e l a t e d to
the Chebyshev p o l y n o m i a l s , the author believes that B (x) and b (x)
a r e of use in the study of ladder n e t w o r k s and hence d e s e r v e a study of
this n a t u r e .
REFERENCES
1.

Ao M. M o r g a n - V o y c e , Ladder n e t w o r k a n a l y s i s using Fibonacci

n u m b e r s , IRE. T r a n s , on C i r c u i t Theory, Vol. C T - 6 , Sept. 59,
pp. 321-322 0

1966
2.

DEFINED BY MORGAN-VOYCE
S. L. Basin,

81

The a p p e a r a n c e of Fibonacci n u m b e r s and the Q

m a t r i x in e l e c t r i c a l n e t w o r k theory, Math. Magazine, Vol. 36,

M a r c h - A p r i l 63, pp. 8 4 - 9 7 .
3.

S. L. Basin, An application of continuants,

Math. Magazine,

Vol. 37, M a r c h - A p r i l 64, pp. 83-91..

4.

V. O. Mowery, Fibonacci n u m b e r s and Tchebycheff polynomials

in ladder n e t w o r k s , IRE. T r a n s , on C i r c u i t Theory, Vol. C T - 8 ,
June 61, pp. 167-168.

5.

T. R. Bashkow, A note on ladder n e t w o r k a n a l y s i s , IRE. T r a n s .

on C i r c u i t Theory, Vol. C T - 8 , June 61, pp. 168-169.

6.

T. R. O ' M e a r a ,
fer functions,

G e n e r a t i n g a r r a y s for ladder network t r a n s -

IEEE.

Trans,

on C i r c u i t Theory, Vol. C T - 1 0 ,

June 63, pp. 285-286.

7.

F . Bubnicki, Input i m p e d a n c e and t r a n s f e r function of a l a d d e r

network,

I E E E . T r a n s , on C i r c u i t Theory, Vol. C T - 1 0 , June

63, pp. 286-287.

8.

Solution to p r o b l e m 33, Canadian M a t h e m a t i c a l Bulletin, Vol.

4, No. 3, 1961, pp. 3 1 0 - 3 1 1 .

ACKNOWLEDGEMENTS
This w o r k was supported by the National R e s e a r c h Council of Canada,
under Grant No. A - 2 8 7 5 .

The author would like to thank the r e v i e w e r

and P r o f e s s o r V. E. Hoggatt for t h e i r useful suggestions and c o m ments.

XXXXXXXXXXXXXXX

PERFECT NUMBER "ENDINGS"

J.A.H. Hunter
Toronto, Ontario, Canada

Helen A. M e r r i l l , in h e r book M a t h e m a t i c a l E x c u r s i o n s , (Dover

P u b l i c a t i o n s , Inc. ; New York) outlined the m a i n f e a t u r e s of P e r f e c t
N u m b e r s . After stating that 6, 28, and 396 a r e P e r f e c t N u m b e r s , she
continued:
"The next P e r f e c t Number is 8128, and the next contains eight
digits.

All t h e s e P e r f e c t N u m b e r s end in 6 or 28, but no one

knows whether this is t r u e of all such n u m b e r s . "

The 1st edition of that book was published in 1933. It is p o s s i b l e
that an e l e m e n t a r y proof for the noted " e n d i n g s " h a s been published
s o m e w h e r e since then, but if so it has e s c a p e d m y n o t i c e .
A c c o r d i n g l y I venture to lay out the n e c e s s a r y but quite e l e m e n t a r y proof that all e v e n P e r f e c t N u m b e r s end in 6 or 28; the n o n - e x i s t ence of any odd P e r f e c t Number has not yet been p r o v e n .
E v e r y even P e r f e c t Number is known to be of g e n e r a l form:
n

2 -V-l).
The mod 100, by a c t u a l calculation for s u c c e s s i v e values of n
(n > 1), we see that 2

( 2 - 1 ) has s u c c e s s i v e values 6, 28, 0, 6;

this sequence of 4 values being r e p e a t e d for all c a s e s up to n - 22.

Still to mod 100, each of 2

- 2

- 1 has a period of 20, r e p e a t i n g

the r e m a i n d e r s . Hence, the "6, 28, 0, 6" sequence of endings for the
product

(2

- 1) m u s t continue for all values of n.o

It will be noted, the proof being t r i v i a l , that z e r o endings o c c u r

only when n = 4k.
Now, the a c t u a l p a r t i c u l a r form for all even P e r f e c t N u m b e r s
requires

n to be p r i m e . Hence, with n = 4k, we can have no P e r f e c t

Number.
So, for all e v e n P e r f e c t N u m b e r s we m u s t have 6 or 28 as "ending. "
xxxxxxxxxxxxxxx

82

A DIVISIBILITY PROPERTY OF FIBONACCI NUMBERS

Lenard Weinstein
Massachusetts Institute of Technology

The following is an i n t e r e s t i n g t h e o r e m c o n c e r n i n g the f i r s t

2n

Fibonacci n u m b e r s :
Theorem
Give any set of . n + 1 F i b o n a c c i n u m b e r s s e l e c t e d from the set
F , , F~, . . . , F~ , it is always p o s s i b l e to choose two e l e m e n t s from
the n + 1 Fibonacci n u m b e r s such that one divides the o t h e r .
This t h e o r e m will be proved using the following two t h e o r e m s :
T h e o r e m 1:
Give any set of n + 1 i n t e g e r s s e l e c t e d from the set 1, 2, . . . ,
2n, it is always possible to choose two e l e m e n t s from the n..+ 1 i n t e g e r s such that one divides the o t h e r .
Proof:
We shall u s e induction.
c a s e n = 1.

The t h e o r e m is t r i v i a l l y t r u e for the

A s s u m e it t r u e for n = k.

If n = k+1, we m u s t prove

that any set of k+2 i n t e g e r s selected from the set 1, 2, . . . , 2(k+l)

contains two e l e m e n t s such that one divides the o t h e r .

If the k+2 i n -

t e g e r s a r e contained in the set 1, 2, . . . , 2k, then by the inductive

hypothesis,

the t h e o r e m is t r u e .

Similarly,

if k+1 of the i n t e g e r s

a r e contained in the set 1, 2, . . , 2k, and the other i n t e g e r i s e i t h e r

2k+l

or 2(k+l), the s a m e r e a s o n i n g applies a s above.

If only k of

the i n t e g e r s belong to the set 1, 2, . . . , 2k, then the other two i n t e g e r s m u s t be the n u m b e r s
numbers

2k+l

and 2(k+l).

Consider any set of k

from the set 1, 2, . . . , 2k and the i n t e g e r

k+1.

By the

inductive h y p o t h e s i s , we can find two n u m b e r s from this set such that

one n u m b e r divides the o t h e r .
but itself,

in the set 1, 2, . . . , 2k, at best it is divisible by another

e l e m e n t of the s e t .
2(k+l).

Since k+1 does not divide any n u m b e r

Any n u m b e r that divides k+1, though,

divides

Thus, any set of k e l e m e n t s chosen from the set j 1, 2, . . . ,

2k | and the e l e m e n t

2(k+l), contains two n u m b e r s such that one n u m -

b e r divides the o t h e r .

T h e r e f o r e , the set of any k i n t e g e r s from the

83

84

A DIVISIBILITY P R O P E R T Y OF FIBONACCI NUMBERS

set

1, 2, . . . , 2k

, plus the n u m b e r s

2k+l

Feb.

and 2(k+l), a l s o con-

tains two e l e m e n t s such that one divides the o t h e r .

T h e o r e m 2:
If F
F,

is the n

Fibonacci number

(F, = 1 , F
l

= 1), then

,v = (F , F ) [l] ( (a, b) is the g r e a t e s t c o m m o n d i v i s o r of the

i n t e g e r s a and b. ) This is a widely known t h e o r e m , e a s i l y p r o v e d .

It follows that if any set of n+1 F i b o n a c c i n u m b e r s F , F ,
a
a
l
2
. .. F
, is chosen from the set F , , F 9 , . . . , F 9 , t h e r e e x i s t two
a
l
L
Zn
n+l
e l e m e n t s of the n+1 F i b o n a c c i n u m b e r s such that one n u m b e r divides
the o t h e r . F o r c o n s i d e r the n u m b e r s a , , a~, . . . , a ,, . By t h e o r e m
1, we can find two n u m b e r s a., a, from t h e s e n+1 i n t e &g e r s such that
,
J
k
a. a, . Thus (a., a, ) = a.. It follows that F ,
, = F = (F , F )
j' k
j ' k'
j
(a j9 a k )
a..
a..' a ^
by t h e o r e m 2. This m e a n s F | F , and the t h e o r e m is p r o v e d .
a.

3.1

REFERENCES
1.

N. N. V o r o b ' e v , F i b o n a c c i N u m b e r s , B l a i s d e l l , New York, 1961,

p 30.

xxxxxxxxxxxxxxx

The F i b o n a c c i B i b l i o g r a p h i c a l R e s e a r c h Center d e s i r e s that any

r e a d e r finding a Fibonacci r e f e r e n c e , send a c a r d giving the r e f e r e n c e
and a brief d e s c r i p t i o n of the c o n t e n t s .

P l e a s e forward all such in-

formation to:
F i b o n a c c i Bibliographical R e s e a r c h Center,
Mathematics Department,
San J o s e State College,
San J o s e , California

A LETTER TO THE EDITOR

Enrico T. Federighi and Ronald G. Roll
The Johns Hopkins University
Silver Spring, Maryland

A careful study of the Tables of Fibonacci E n t r y Points h a s

l e d . us to m a k e some o b s e r v a t i o n s r e g a r d i n g the f a c t o r s of Fibonacci
numbers.
I t i s r e a d i l y seen that Z(p) divides p - 1 w h e n e v e r
10) and divides p-fl

whenever

p = 3 (mod 10).

Our p r o b l e m is to d e t e r m i n e ,
which

Z(p)

p = 1 (mod

if p o s s i b l e , the p r i m e s

divides p(k) = ( p l ) / k for

k > 1.

p for

We conjecture the

following solutions.
k=2:

Z(p) divides p(2) if and only if

p=4n+l.

k=3:

Z(p) divides p(3) if and only if p=x

or p = 5x + 27y .

k=4:

Z(p) divides p(4) if and only if p=x

or p = 5x + 16y .

2
+135y

2
+ 80y

The rule is m o r e c o m p l i c a t e d but is still r e a s o n a b l e if k is a

small prime.
Let

Let k be such a p r i m e and define

p(k,-) = 2 cos (2 7T^/k) and

p r i m i t i v e root of k.

A l s o let

(3 = ( k - l ) / 2 .

1 J

y.. = g " , where

1J
= 2 - p(k, gJi-1 ). Define

C(k,x, y) = n

_i=l

i=l

Ec

Zrx

26-2r

is a

"E Pbip(k' yJ 1

2r

r=0

k > 4:

Z(p) divides p(k) if and only if m p = C(k, s / 5 , 1)

mp = C(k, 1, \s5)

where

c^g = 0 (mod k ).

The n a t u r e of m is un|3

xi

c e r t a i n but it will u s u a l l y be unity or a power of 2 . If 5

k) for n < p, m m a y a l s o contain an even power of 5.
85

or

= 1 (mod

86

Feb.

A L E T T E R TO THE EDITOR

To i l l u s t r a t e how the f o r m u l a t i o n s look in p r a c t i c e , a table of a l l

p r i m e s under 1000 with k > 3 is listed.

It is a s s u m e d that

x=y=l.

Type 1 m e a n s that

P
mp =

.r

L c2r51
r=0

and type 2 m e a n s that

p
mp =

E C2r5

P-r

r=0

47
61
89
107
109
113
139
149
151
199
211
233
263
269
281
307
331
347
353
389
401
421

3
4
4
8
3
4
3
3
4
3
3

5
3
9
3
4
5
7
3
3
3
4
4
4

type

cQ

c2

1
1
2
2
1
1
1
2
1
2
2
2
2
1
1
1
1
2
1
2
1
1
1
2
1

1
1
1
1
1
1
1
1
1
1
1
64
16
1
64
1
1
16
64
1
1
1
1
1
1
16

4
9
9
1
16
9
1
4
1
16
64
361
1
25
1
4
25
121
1
196
64
49
49
81
81
361

27
16
16
12
27
64
108
27
144
27
27
585
50
108
153
243
144
250
581
27
27
108
144
64
16
650

c4

c&-

243
125

27

2187

27

125
931

343

125

1966

A L E T T E R TO THE EDITOR
ktype

461
521
541
557
563
619
661
677
691
701
709
743
761
769
797
809
811
821
829
859
881
911
919

953

5
4
5
3
3
9
3
3
3
4
3
5
4
3
3
4
8
4
8
7
4
3
4
3
4
11
5
13
3
9

3
9
967 11
977
3
991 5

2
16
2
1
16
2
2
1
1
64
1
2
2
1
1
2
16
1
2
1
2
2
2
1
1
64
2
2
1
2
1
1
1024
16
2
1 102400
2
1
2
64

1
1
1
1
2

87
10

1
441
961
1
25
1
64
484
121
81
49

125

15 3

4779

1681

1250

25
169
100
441
1
49
289
169
729

576
108
243
64
96
144
76
917
16
27
576
108
784
319

67 6

49
289
9
1

1450

3721

1
784
1

125

850
16
850
108
432
243
27
108
256
432

'12

78.03

125

256
4
1323

343

3146

9438

9317

1331

125

182 10595 222404 1595191 3405350 1373125

27
153 2187
27

1 169 108
64 361 585
243
27
32768
1 1551 105754 642510 286165 1331
1
1 972
16 3481 1850
125

C o m m e n t s on Table:
1) As can be seen whenever k is an odd prime c,

2) If k is an odd p r i m e
divisible by k~

is divisible by

b. = 0 (mod k) wilL e n s u r e that c, , be

A L E T T E R TO THE EDITOR

88

Feb.

3) If one s u m s the coefficients in the table without f i r s t multiplying by

p o w e r s of five one obtains k - t h power r e s i d u e s of two.
Some of this has undoubtedly been o b s e r v e d before and even
probably proved but we have no idea how m u c h .
We have enjoyed playing around with t h e s e concepts and actually
s u s p e c t much m o r e than we have indicated h e r e .

If anyone is i n t e r -

e s t e d in p u r s u i n g this further, we shall be glad to h e a r from h i m .

XXXXXXXXXXXXXXX

LETTER TO THE EDITOR

Lenard Weinstein
Massachusetts Institute of Technology

Conjecture 2 . , m a d e by M r . Thoro, on page 186 of the October

i s s u e , follows i m m e d i a t e l y from the following t h e o r e m found on page
126 of W. J. Leveque, Topics in Number Theory, Vol. I:
Definition
A r e p r e s e n t a t i o n of a positive i n t e g e r n as a sum of two s q u a r e s ,
2
2
say n = x + y is t e r m e d p r o p e r if (x, y) = 1.
Theorem
If p is a p r i m e of the form

4k + 3 and p |n, then n h a s no

proper representation.
Since

F 0 ,. = F + F ,_ , and ( F , F , . ) = 1, F - ,. always
J
2n+l
n
n+1
n n+1
2n+l
has a p r o p e r r e p r e s e n t a t i o n .
T h e r e f o r e , by the above t h e o r e m , no
pc r i m e of the form 4k + 3 can divide F - ,, .
2n+l
XXXXXXXXXXXXXXX

A LOGARITHMIC FORMULA FOR FIBONACCI NUMBERS

Gerard R, Deiiy
United States Department of Defense
Washington, D.C.

If the l o g a r i t h m of the F i b o n a c c i n u m b e r

is plotted a g a i n s t

n, it can be seen that for l a r g e n the graph is a s t r a i g h t line.

Thus

one might expect that F i b o n a c c i n u m b e r s could be computed from a

formula of the form
log& F n = m n + b

(i)

w h e r e m is the slope of the line and b its i n t e r s e c t i o n with the

vertical axis.

That this is so can e a s i l y be shown by manipulating

B i n e t ' s formula
(2)

=l-

V"

(^)" - i^J

into the following form:

(3)

-^M' i-m)

F o r l a r g e n, the second t e r m within the b r a c k e t b e c o m e s negligible,

and hence (3) b e c o m e s
(4)

a(^r

Taking l o g a r i t h m s then gives

(5)

log F n

n[log (1. + V 5 ) - log 2 ] - ~ log 5

which is of the form (1). If b a s e 10 is used, the c h a r a c t e r i s t i c of the

l o g a r i t h m computed in (5) then gives the o r d e r of magnitude of F
This knowledge is useful in d e t e r m i n i n g r e q u i r e d s i z e s of r e g i s t e r s
when setting up F i b o n a c c i p r o b l e m s for computation.
xxxxxxxxxxxxxxx
89

ELEMENTARY PROBLEMS AND SOLUTIONS

Edited by A.P. Hillman
University of New Mexico, Albuquerque, New Mexico

Send all c o m m u n i c a t i o n s r e g a r d i n g E l e m e n t a r y P r o b l e m s and

Solutions to P r o f e s s o r A. P . Hillman,

D e p a r t m e n t of M a t h e m a t i c s

and S t a t i s t i c s , U n i v e r s i t y of New Mexico, Albuquerque, New Mexico.

Each p r o b l e m or solution should be submitted in legible form, p r e f e r ably typed in double spacing, on a s e p a r a t e sheet or s h e e t s in the form a t used below.

Solutions should be r e c e i v e d within two months of

publication.
B-82

Proposed by Nanci Smith, University

D e s c r i b e a function

of New Mexico, Albuquerque,

N.M.

g(n) having the table:

n | I 0 1 2 3 4 5 6 7 8 9 10 11 12 . . .
g(n)| | 0 1 1 2 1 2 2 3 1 2
B-83

Proposed by M.N.S. Swamy, Nova Scotia Technical

Show that
B-84

2 .. .

College, Halifax,

+ F _,_. = F , + F
+ 4F
n+4
n+1
n+3
n+2

Proposed by M.N.S. Sivamy, Nova Scotia Technical

Canada

College, Halifax,

Canada

The Fibonacci polynomials a r e defined by f. (x) = 1, f ^ x ) = x,

fn+1(x) = x f n ( x ) + f n _ 1 ( x ) J
If z

B-85

n> 1 .

= f (x) + f (y),
show that z
satisfies
r
r J
r
z , A - (x+y)z l o + (xy-2)z l 0 + (x+y)z
+z = 0 .
3
J
n+4 v y' n+3
n+2
n+1
n
Proposed by Douglas Lind, University

of Virginia, Charlottesville,

Find c o m p a c t e x p r e s s i o n s for:

(a)

FZ2+rZ4

Tl+...

(b)

F^

F2

+ r

F2

90

...

F*n

2n_

Va.

1966

E L E M E N T A R Y P R O B L E M S AND SOLUTIONS

B - 8 6 , Proposed by Verner E. Hoggatt, Jr., San Jose State College, San Jose,

91
California

Show that the s q u a r e s of e v e r y t h i r d Fibonacci n u m b e r satisfy

17

yn+3B-87

yn+2

+ 17

Proposed by A.P. Hillman, University

Vu

= 0

-yn

of New Mexico, Albuquerque,

N.M.

P r o v e the identity in
n

r[^r-

k=0

j=0

k)

V ]
_^

v<n2+1> +

Xj

j=0

SOLUTIONS
AN N- T U P L E I N T E G R A L
B-70

Proposed by Douglas hind, University

Denote x

by ex(a).

of Virginia, Charlottesville,

Va.

Show that the following e x p r e s s i o n , con-

taining n i n t e g r a l s ,
1

equals
n

ex ( I

ex(

F , , / F 1OJ w h e r e
n + 1 ' n+2

ex(. o .

0
n

ex( /

x dx)dx). . . dx)dx)dx

is the n - t h F i b o n a c c i n u m b e r .

Solution by John Wessner, Melbourne, Florida

Let I

denote the n - t h
Ir =

such i n t e g r a l .

Then

J x dx = 1/2 '.
0

Let us a s s u m e that I

, = F / F L 1 , in which c a s e
n-1
n n+1

In=/xF/F+1dx={(Fn/Fn+1,+l}-1
0
=

|(F

IP

{ n
which was to be shown.

4- FTT

\ /XT
4-1 ) / F

n+1"

4-1

\ ~
f

n+1;

TT

/T,
_L7/F

n+2'

n+1 *
r

Also solved by R.J. Hursey, Jr; M.N.S. Swamy; Howard L. Walton; David Zeitlin;

and the proposer

92
B-71

E L E M E N T A R Y P R O B L E M S AND SOLUTIONS
Proposed by Douglas hind, University

Find

-2

' -3

+a

+a

- 4

of Virginia, Charlottesville,

+ ...,

where

a = (1 -

Va.

5)/2 .

Solution by John W. Milsom, Slippery Rock State College, Slippery Rock,

-2

If S = a

-3

+ a,

-4

+a

Feb.

Penna.

-1

- 2

+ . . . , then a S - 1 + a

+a

+ ...-.

Subtracting the f i r s t equation from the second,

a 2 S - S = 1. + a" 1
S = ( l + a " r ) / ( a 2 - 1)

S= l/[a(a - 1)] .
Using a - (1 +V5T/2, we find that S = 1.

If you u s e a = (1 + 5)/2 =

= 6/2 = 3, as the p r o b l e m r e a d s , the r e s u l t is S = l / 6 .

Also solved by R.J, Hursey, Jr; Sidney Kravitz; M.N.S. Swamy; C.W. Trigg; Howard L. Walton;
John Wessner; David Zeitlin; and the proposer.

ADDING RABBITS?
B-72

Proposed by J.AM.

Hunter, Toronto, Canada

E a c h d i s t i n c t Letter in this simple a l p h a m e t i c stands for a p a r t i c u l a r and different digit.

We all know how r a b b i t s link up with the

F i b o n a c c i s e r i e s , so now evaluate our RABBITS.

RABBITS
BEAR
RABBITS
AS
A SERIES
Solution by Charles W. Trigg, San Diego,

California

By the f i r s t column from the left, 0 < R < 5.

column, 2S + R = 10k, so S / 0, and R is even.

By the seventh

That i s , Jl = 2 or

4.
By the fourth column, 3B + .1 = R, so B is odd.

1966

ELEMENTARY PROBLEMS AND SOLUTIONS

93

With t h e s e and the obvious r e l a t i o n s from the other columns we

can p r o c e e d to e s t a b l i s h the values of the l e t t e r s in the o r d e r given in
the table below:
R

1 9

Since the f i r s t two s e t s contain duplicate digits, the third set is

the unique solution.

Thus
4 9 115 6 8
1 29 4

4 9 115 6 8
9 8
9 8 2 4 5 2 8

That i s , RABBITS = 4911568, which j u s t g o e s to show what 2 r a b b i t s

can do.
Also solved by Murray Berg; Rudolph W. C as town; Sidney Kravitz; John W. Milsom;
Azriel Rosenfeld; and the proposer.

D O U B L E SUMS
B-73

Proposed by Douglas Lind, University

P r o v e that
n n

2n+r-2

m=0

p=0

k=0 j=0
where

( ) = 0 for

Solution by David Zeitlin,

of Virginia, Charlottesville,

Va.

n < r
Minneapolis,

Minnesota

The given identity is valid only for

[n/2]
F n _! = 2 f'ih.
j=0

r < n '+ 1.

Since

n
n
F k = F n + 2 - 1, and ) F k + m = F 2 n + m .
k=0

k=0

we have
2n+r-2

i +

2n+r-2

m=0

p=0

rri=0

94

ELEMENTARY PROBLEMS AND SOLUTIONS

while for

Feb.

r <_ n + 1, we have

k=0

j=0

k=0

Also solved by the proposer.

FIBONACCI POLYNOMIALS
B-74

Proposed by M.N.S. Swamy, University

of Saskatchewan,

Regina,

Canada

The F i b o n a c c i polynomial f (x) is defined by f, = 1 , ? - x,

and f (x) = xf 1 (x) + f ~(x) for n > 2.
n
n-1
n-2
n
(a)

x Y

f (x) = f

+f

Show the following:

te

- 1 .

r=l

(b)

, , . = f ,. f ,. + f f .
m+n+1
m+1 n+1
m n
[(n-l)/2]
n-j-l^xn-2j-l
j=o.

where

the n - t h

is the g r e a t e s t i n t e g e r not exceeding k.

Donacci numbe
Fibonacci
number

Hence show that

[(n-l)/2]
j=0
Solution by David Zeitlin,

(a)

Minneapolis,

Minnesota

Assuming the r e l a t i o n to be t r u e for

n = n, we have

n+1
x J ] f" L (x)
(f n+1
,, +' fx - 1)
r w =" xf
^ n +,.1 +' Vi
n
r=l

W ^ n - f l "

and the r e s u l t now follows by m a t h e m a t i c a l induction.

1966
(b)

ELEMENTARY PROBLEMS AND SOLUTIONS

Using f o r m u l a (6) in m y p a p e r ,

95

"On s u m m a t i o n f o r m u l a s for

F i b o n a c c i and Lucas n u m b e r s , " this Q u a r t e r l y , vol. 2, 1964, No. 2,

p 105, we have (since L = 0)
f'
+f y
m+1
m J

/, v

(1)

{2)
1

- xy - y
f
T
-xy-y
f

(3)
,

y
2LJ_

oo
v^

= E
n ^o

= E
n =o

m+n+i y >

m+i

n+1

y >

= E f f y11
M

m n

" y "
n=0
n
Since (1) = (2) + (3), the r e s u l t follows by equating coefficients of y
(c)

We note that
oo

Ux

11

- v

/^w
2 - E 4y*>y

y-y

n =o

and r e c a l l that
1

1-2tz+z

U (t)z n ,

~
n=0
U (t) is the C h e b y s h e v p o l y n o m i a l of the second kind defined by

where

[n/2]
U n (t) =
(-1) J ( y ) ( 2 t )
j=o

(4)
with i

oo

= - 1 , we s e e that for z = iy and t = x / 2 i , we have

T-^

- y-y

n =o

x x

and thus f

(x) = i

oo

.n

TT

,x . n

U (x/2i), the d e s i r e d r e s u l t , using (4).

96

ELEMENTARY PROBLEMS AND SOLUTIONS

Since F

Feb.

= f (1), we obtain
n

|>-l)/2l

*n =

("t1).

/1/so solved by the proposer.

DERIVATIVES OF FIBONACCI POLYNOMIALS

B-75

Proposed by M.N.S. Swamy, University

of Saskatchewan,

Let f (x) be a s defined in B-74.

n
n-1
f
Solution by David Zeitlin,

Regina,

Canada

Show that the d e r i v a t i v e

(x) = Y\ f (x) f
(x) for n > 1.
"
r
n-r
r=l

Minneapolis,

Minnesota

If we differentiate with r e s p e c t to x the identity

oo

-2 = E

l x

- ?-y

n (-)y

n =o

we obtain

52 ^ = 1 - ^ ) ^ 1 1 : yx)yn)
n=0

1-xy-y

n=Q

= Z [ f r (x)f n-r W] y"

n=0

r=0

If we equate coefficients of y , we obtain

n

f (x) = L
n

A-

(x)f

(x)

' r
n-r
r=0
n-1
= Z f r (x)f n _ r (x)
r=l

Also solved by Lawrence D. Gould and the proposer.

XXXXXXXXXXXXXXXX

(since fQ(x)

= 0) .