|
9.3
Sequences of Integers
9.3.1
Fibonacci and Lucas Sequences
Problem 9.3.5.
Determine the maximum value of m
2
+
n
2
, where m and n are
integers satisfying
1
≤
m
,
n
≤
1981
and
(
n
2
−
mn
−
m
2
)
2
=
1
.
(22nd International Mathematical Olympiad)
Solution.
Let
S
be the set of pairs
(
n
,
m
)
of positive integers satisfying the equa-
tion
(
x
2
−
x y
−
y
2
)
2
=
1
.
(
1
)
If
n
=
m
, then
n
=
m
=
1. Hence
(
1
,
1
)
∈
S
. It is clear that
(
1
,
0
)
and
(
0
,
1
)
are also solutions to equation (1).
We will consider solutions
(
n
,
m
)
with distinct components. Using Fermat’s
method of infinite descent we obtain the following important result on the set
S
.
Lemma.
If
(
n
,
m
)
is a positive solution to equation
(
1
)
and n
=
m, then n
>
m
>
n
−
m and
(
m
,
n
−
m
)
is also a solution to
(
1
)
.
Proof.
From
n
2
−
nm
−
m
2
= ±
1, we obtain
n
2
=
m
2
+
nm
±
1
<
m
2
; thus
n
>
m
. Also from
n
2
−
nm
−
m
2
= ±
1, we obtain
m
2
−
m
(
n
−
m
)
−
(
n
−
m
)
2
=
m
2
+
mn
−
n
2
= ∓
1
.
Apply the first part to the solution
(
m
,
n
−
m
)
and obtain
m
>
n
−
m
.
From the lemma we deduce that any pair
(
n
,
m
)
∈
S
gives rise to a pair
(
m
,
n
−
m
)
∈
M
, which gives rise to a pair
(
a
+
b
,
a
)
∈
M
. In this way, by the
method of descent
(
n
,
m
)
→
(
m
,
n
−
m
)
, or by the method of ascent
(
a
,
b
)
→
(
a
+
b
,
a
)
, we obtain a new solution of the equation. The methods of ascent and
descent are the reverse of each other.
By applying the descending method to a pair
(
n
,
m
)
∈
S
we can only have
finitely many steps, because
n
−
m
<
m
. Hence, in a finite number of steps we
obtain a pair with
n
=
m
, the pair
(
1
,
1
)
. Thus, all solutions
(
n
,
m
)
∈
S
are
obtained from the pair
(
1
,
0
)
by applying the ascending method:
(
1
,
0
)
→
(
1
,
1
)
→
(
2
,
1
)
→
(
3
,
2
)
→
(
5
,
3
)
→
. . .
The components of all such pairs are Fibonacci numbers
F
n
. In this way, the
ascending transformation is exactly the following:
(
F
n
,
F
n
−
1
)
→
(
F
n
+
1
,
F
n
).
336
II Solutions, 9. Some Special Problems in Number Theory
Thus, to obtain the solution
(
n
,
m
)
with maximum value of
n
2
+
m
2
we con-
sider the members of the Fibonacci sequence, not exceeding 1981:
0
,
1
,
1
,
2
,
3
,
5
,
8
,
13
,
21
,
34
,
55
,
89
,
144
,
233
,
377
,
610
,
987
,
1597
.
So, the required maximum is 987
2
+
1597
2
.
Remark.
Fibonacci numbers
F
n
have the property
F
2
n
+
1
−
F
n
F
n
+
1
−
F
2
n
= ±
1
,
for all
n
≥
0
.
To prove it for
n
=
0 or
n
=
1 it is equivalent to see that
(
1
,
0
)
∈
S
and that
(
1
,
1
)
∈
S
. Further, we can use induction. The relation
F
2
n
+
1
−
F
n
F
n
+
1
−
F
2
n
= ±
1
implies
F
2
n
+
2
−
F
n
+
1
F
n
+
2
−
F
2
n
+
1
=
(
F
n
+
1
+
F
n
)
2
−
F
n
+
1
(
F
n
+
1
+
F
n
)
−
F
2
n
+
1
= −
(
F
2
n
+
1
−
F
n
F
n
+
1
−
F
2
n
)
= ∓
1
.
So in fact,
F
2
n
+
1
−
F
n
F
n
+
1
−
F
2
n
=
(
−
1
)
n
.
Another way to prove this relation is to use the matrix form for the Fibonacci
numbers and get
1 1
1 0
n
+
1
=
F
n
+
2
F
n
+
1
F
n
+
1
F
n
.
Passing to determinants on both sides yields
(
−
1
)
n
+
1
=
F
n
+
2
F
n
−
F
2
n
+
1
=
(
F
n
+
1
+
F
n
)
F
n
−
F
2
n
+
1
=
F
2
n
+
F
n
F
n
+
1
−
F
2
n
+
1
.
Problem 9.3.6.
Prove that for any integer n
≥
4
, F
n
+
1
is not a prime.
First solution.
We have the identity
F
4
n
−
1
=
F
n
−
2
F
n
−
1
F
n
+
1
F
n
+
2
.
(
2
)
Assume that
F
n
+
1 is a prime for some positive integer
n
≥
4. Using (1), it
follows that
F
n
+
1 divides at least one of the integers
F
n
−
2
,
F
n
−
1
,
F
n
+
1
,
F
n
+
2
.
Since
F
n
+
1 is greater than
F
n
−
2
and
F
n
−
1
, it follows that
F
n
+
1 divides
F
n
+
1
or
F
n
+
2
. But
F
n
+
1
<
2
F
n
and
F
n
+
2
<
4
F
n
; hence
F
n
+
1 cannot divide
F
n
+
1
or
F
n
+
2
, and the desired conclusion follows.
9.3. Sequences of Integers
337
Second solution.
Note the four equalities
F
4
m
+
1
+
1
=
L
2
n
+
1
F
2
n
−
1
,
F
4
n
+
1
+
1
=
L
2
n
F
2
n
+
1
,
F
4
n
+
2
+
1
=
L
2
n
F
2
n
+
2
,
F
4
n
+
3
+
1
=
L
2
n
+
2
F
2
n
+
1
,
which follow from the Binet formula or induction.
Problem 9.3.7.
Let k be an integer greater than
1
, a
0
=
4
, a
1
=
a
2
=
(
k
2
−
2
)
2
,
and
a
n
+
1
=
a
n
a
n
−
1
−
2
(
a
n
+
a
n
−
1
)
−
a
n
−
2
+
8
for n
≥
2
.
Prove that
2
+
√
a
n
is a perfect square for all n.
Solution.
The Fibonacci numbers are involved here again, but it is much harder
to guess how they are related to the solution.
Let
λ, μ
be the roots of the equation
t
2
−
kt
+
1
=
0. Notice that
λ
+
μ
=
k
,
λμ
=
1. Augmenting the Fibonacci sequence by setting
F
0
=
0, we claim that
a
n
=
(λ
2
F
n
+
μ
2
F
n
)
2
for
n
=
0
,
1
,
2
, . . .
This is readily checked for
n
=
0
,
1
,
2. Assume that it holds for all
k
≤
n
.
Note that the given recursion can be written as
a
n
+
1
−
2
=
(
a
n
−
2
)(
a
n
−
1
−
2
)
−
(
a
n
−
2
−
2
),
and that
a
k
=
(λ
2
F
k
+
μ
2
F
k
)
2
is equivalent to
a
k
−
2
=
λ
4
F
k
+
μ
4
F
k
. Using the
induction hypothesis for
k
=
n
−
2
,
n
−
1
,
n
, we obtain
a
n
+
1
−
2
=
(λ
4
F
n
+
μ
4
F
n
)(λ
4
F
n
−
1
+
μ
4
F
n
−
1
)
−
(λ
4
F
n
−
2
+
μ
4
F
n
−
2
)
=
λ
4
(
F
n
+
F
n
−
1
)
+
μ
4
(
F
n
+
F
n
−
1
)
+
λ
4
(
F
n
−
1
+
F
n
−
2
)
μ
4
F
n
−
1
+
μ
4
(
F
n
−
1
+
F
n
−
2
)
λ
4
F
n
−
1
−
(λ
4
F
n
−
2
+
μ
4
F
n
−
2
)
=
λ
4
F
n
+
1
+
μ
4
F
n
+
1
+
(λμ)
4
F
n
−
1
(λ
4
F
n
−
2
+
μ
4
F
n
−
2
)
−
(λ
4
F
n
−
2
+
μ
4
F
n
−
2
).
Since
λμ
=
1, it follows that
a
n
+
1
=
2
+
λ
4
F
n
+
1
+
μ
4
F
n
+
1
=
(λ
2
F
n
+
1
+
μ
2
F
n
+
1
)
2
,
and the induction is complete.
Now
2
+
√
a
n
=
2
+
λ
2
F
n
+
μ
2
F
n
=
(λ
F
n
+
μ
F
n
)
2
.
Since
(λ
m
−
1
+
μ
m
−
1
)(λ
+
μ)
=
(λ
m
+
μ
m
)
+
λμ(λ
m
−
2
+
μ
m
−
2
),
338
Do'stlaringiz bilan baham: |
