|
9.3. Sequences of Integers
183
Second solution.
Expanding Binet’s formula using the binomial theorem gives
2
n
−
1
F
n
=
n
/
2
k
=
0
5
k
n
2
k
+
1
.
Therefore
F
n
≡
3
n
−
1
n
+
5
n
3
(
mod 25
)
. Modulo 25, 3
n
−
1
has period 20,
n
has period 25, and 5
n
3
has period 5. Therefore
F
n
clearly has period dividing
100. The period cannot divide 50, since this formula gives
F
n
+
50
≡
3
10
F
n
≡ −
F
n
(
mod 25
)
and the period cannot divide 20 since it gives
F
n
+
20
≡
F
n
+
3
n
−
1
·
20
(
mod 25
)
.
Problem 9.3.3.
Let
(
a
n
)
n
≥
0
be the sequence defined by a
0
=
0
, a
1
=
1
, and
a
n
+
1
−
3
a
n
+
a
n
−
1
2
=
(
−
1
)
n
for all integers n
>
0
. Prove that a
n
is a perfect square for all n
≥
0
.
Solution.
Note that
a
2
=
1,
a
3
=
4,
a
4
=
9,
a
5
=
25, so
a
0
=
F
2
0
,
a
1
=
F
2
1
,
a
2
=
F
2
2
,
a
3
=
F
2
3
,
a
4
=
F
2
4
,
a
5
=
F
2
5
, where
(
F
n
)
n
≥
0
is the Fibonacci sequence.
We induct on
n
to prove that
a
n
=
F
2
n
for all
n
≥
0. Assume that
a
k
=
F
2
k
for
all
k
≤
n
. Hence
a
n
=
F
2
n
,
a
n
−
1
=
F
2
n
−
1
,
a
n
−
2
=
F
2
n
−
2
.
(
1
)
From the given relation we obtain
a
n
+
1
−
3
a
n
+
a
n
−
1
=
2
(
−
1
)
n
and
a
n
−
3
a
n
−
1
+
a
n
−
2
=
2
(
−
1
)
n
−
1
,
n
≥
2
.
Summing up these equalities yields
a
n
+
1
−
2
a
n
−
2
a
n
−
1
+
a
n
−
2
=
0
,
n
≥
2
.
(
2
)
Using the relations (1) and (2) we obtain
a
n
+
1
=
2
F
2
n
+
2
F
2
n
−
1
−
F
2
n
−
2
=
(
F
n
+
F
n
−
1
)
2
+
(
F
n
−
F
n
−
1
)
2
−
F
2
n
−
2
=
F
2
n
+
1
+
F
2
n
−
2
−
F
2
n
−
2
=
F
2
n
+
1
,
as desired.
Problem 9.3.4.
Define the sequence
(
a
n
)
n
≥
0
by a
0
=
0
, a
1
=
1
, a
2
=
2
, a
3
=
6
,
and
a
n
+
4
=
2
a
n
+
3
+
a
n
+
2
−
2
a
n
+
1
−
a
n
,
n
≥
0
.
Prove that n divides a
n
for all n
>
0
.
184
I Fundamentals, 9. Some Special Problems in Number Theory
Solution.
From the hypothesis it follows that
a
4
=
12,
a
5
=
25,
a
6
=
48. We
have
a
1
1
,
a
2
2
=
1,
a
3
3
=
2,
a
4
4
=
3,
a
5
5
=
5,
a
6
6
=
8, so
a
n
n
=
F
n
for all
n
=
1
,
2
,
3
,
4
,
5
,
6, where
(
F
n
)
n
≥
1
is the Fibonacci sequence.
We prove by induction that
a
n
=
n F
n
for all
n
. Indeed, assuming that
a
k
=
k F
k
for
k
≤
n
+
3, we have
a
n
+
4
=
2
(
n
+
3
)
F
n
+
3
+
(
n
+
2
)
F
n
+
2
−
2
(
n
+
1
)
F
n
+
1
−
n F
n
=
2
(
n
+
3
)
F
n
+
3
+
(
n
+
2
)
F
n
+
2
−
2
(
n
+
1
)
F
n
+
1
−
n
(
F
n
+
2
−
F
n
+
1
)
=
2
(
n
+
3
)
F
n
+
3
+
2
F
n
+
2
−
(
n
+
2
)
F
n
+
1
=
2
(
n
+
3
)
F
n
+
3
+
2
F
n
+
2
−
(
n
+
2
)(
F
n
+
3
−
F
n
+
2
)
=
(
n
+
4
)(
F
n
+
3
+
F
n
+
2
)
=
(
n
+
4
)
F
n
+
4
,
as desired.
Additional Problems
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)
Problem 9.3.6.
Prove that for any integer
n
≥
4,
F
n
+
1 is not a prime.
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
.
9.3.2
Problems Involving Linear Recursive Relations
A sequence
x
0
,
x
1
,
x
2
, . . .
of complex numbers is defined recursively by a
linear
recursion of order k
if
x
n
=
a
1
x
n
−
1
+
a
2
x
n
−
2
+ · · · +
a
k
x
n
−
k
,
n
≥
k
,
(
1
)
where
a
1
,
a
2
, . . . ,
a
k
are given complex numbers and
x
0
=
α
0
,
x
1
=
α
1
, . . .
,
x
k
−
1
=
α
k
−
1
are also given.
The main problem is to find a general formula for
x
n
in terms of
a
1
,
a
2
,
. . .
,
a
k
,
α
0
, α
1
, . . . , α
k
−
1
, and
n
. In order to solve this problem we attach to (1) the
algebraic equation
t
k
−
a
1
t
k
−
1
−
a
2
t
k
−
2
− · · · −
a
k
=
0
,
(
2
)
which is called the characteristic equation of (1).
9.3. Sequences of Integers
185
Theorem 9.3.1.
If the characteristic equation (2) has distinct roots t
1
,
t
2
, . . . ,
t
k
,
then
x
n
=
c
1
t
n
1
+
c
2
t
n
2
+ · · · +
c
k
t
n
k
,
(
3
)
where the constants c
1
,
c
2
, . . . ,
c
k
are determined by the initial conditions x
0
=
α
0
, x
1
=
α
1
, . . .
, x
k
−
1
=
α
k
−
1
.
Proof.
Consider the sequence
y
0
,
y
1
,
y
2
, . . .
given by
y
n
=
c
1
t
n
1
+
c
2
t
n
2
+ · · · +
c
n
t
n
n
.
It is not difficult to prove that the sequence
(
y
n
)
n
≥
0
satisfies the linear re-
cursion (1), since
t
1
,
t
2
, . . . ,
t
k
are the roots of the characteristic equation (2).
Consider the following system of linear equations:
c
1
+
c
2
+ · · · +
c
k
=
α
0
,
c
1
t
1
+
c
2
t
2
+ · · · +
c
k
t
k
=
α
1
,
. . .
c
1
t
k
−
1
1
+
c
2
t
k
−
1
2
+ · · · +
c
k
t
k
−
1
k
=
α
k
−
1
,
(4)
whose determinant is the so-called Vandermonde determinant
V
(
t
1
,
t
2
, . . . ,
t
k
)
=
1
≤
i
<
j
≤
k
(
t
j
−
t
i
).
This determinant is nonzero, because
t
1
,
t
2
, . . . ,
t
k
are distinct.
Hence
c
1
,
c
2
, . . . ,
c
k
are uniquely determined as a solution to system (4).
Moreover,
y
0
=
α
0
=
x
0
,
y
1
=
α
1
=
x
1
, . . .
,
y
k
−
1
=
α
k
−
1
=
x
k
−
1
. Using
strong induction, from (1) it follows that
y
n
=
x
n
for all
n
.
The case in which the roots of the characteristic equation (2) are not distinct
is addressed in the following theorem.
Theorem 9.3.2.
Suppose that equation (2) has the distinct roots t
1
, . . . ,
t
h
, with
multiplicities s
1
, . . . ,
s
h
, respectively. Then x
n
is a linear combination of
t
n
1
,
nt
n
1
, . . .
n
s
1
−
1
t
n
1
. . .
t
n
h
,
nt
n
h
, . . . ,
n
s
h
−
1
t
n
h
One can also say that
x
n
=
f
1
(
n
)
t
n
1
+
f
2
(
n
)
t
n
2
+ · · · +
f
h
(
n
)
t
n
h
,
where
f
i
is a polynomial of degree
s
i
, for each
i
.
186
Do'stlaringiz bilan baham: |
