|
I Fundamentals, 9. Some Special Problems in Number Theory
The proof of this result uses the so-called Hermite interpolation polynomial
or formal series.
The most frequent situation is with
k
=
2. Then the linear recursion becomes
x
n
=
a
1
x
n
−
1
+
a
2
x
n
−
2
,
n
≥
2
,
where
a
1
,
a
2
are given complex numbers and
x
0
=
α
0
,
x
1
=
α
1
.
If the characteristic equation
t
2
−
a
1
t
−
a
2
=
0 has distinct roots
t
1
,
t
2
, then
x
n
=
c
1
t
n
1
+
c
2
t
n
2
,
n
≥
0
,
where
c
1
,
c
2
are solutions to the system of linear equations
c
1
+
c
2
=
α
0
,
c
1
t
1
+
c
2
t
2
=
α
1
,
that is,
c
1
=
α
1
−
α
0
t
2
t
1
−
t
2
,
c
2
=
α
0
t
1
−
α
1
t
1
−
t
2
.
If the characteristic equation has the nonzero double root
t
1
, then
x
n
=
c
1
t
n
1
+
c
2
nt
n
1
=
(
c
1
+
c
2
n
)
t
n
1
,
where
c
1
,
c
2
are determined from the system of equations
x
0
=
α
0
,
x
1
=
α
1
,
that is,
c
1
=
α
0
,
c
2
=
α
1
−
α
0
t
1
t
1
.
Example.
Let us find the general term of the sequence
P
0
=
0
,
P
1
=
1
, . . . ,
P
n
=
2
P
n
−
1
+
P
n
−
2
,
n
≥
2
.
The characteristic equation is
t
2
−
2
t
−
1
=
0, whose roots are
t
1
=
1
+
√
2
and
t
2
=
1
−
√
2. We have
P
n
=
c
1
t
n
1
+
c
2
t
n
2
,
n
≥
0, where
c
1
+
c
2
=
0 and
c
1
(
1
+
√
2
)
+
c
2
(
1
−
√
2
)
=
1; hence
P
n
=
1
2
√
2
(
1
+
√
2
)
n
−
(
1
−
√
2
)
n
,
n
≥
0
.
This sequence is called
Pell’s sequence
, and it plays an important part in Dio-
phantine equations.
In some situations we encounter inhomogeneous recursions of order
k
of the
form
x
n
=
a
1
x
n
−
1
+
a
2
x
n
−
2
+ · · · +
a
k
x
n
−
k
+
b
,
n
≥
k
,
where
a
1
,
a
2
, . . . ,
a
k
,
b
are given complex numbers and
x
1
=
α
1
,
x
2
=
α
2
, . . .
,
x
k
−
1
=
α
k
−
1
. The method of attack consists in performing a translation
x
n
=
y
n
+
β
, where
β
is the solution to the equation
(
1
−
a
1
−
a
2
−· · ·−
a
k
)β
=
b
when
a
1
+
a
2
+ · · · +
a
k
=
1. The sequence
(
y
n
)
n
≥
0
satisfies the linear recursion (1).
9.3. Sequences of Integers
187
Example.
Let us find
x
n
if
x
0
=
α
,
x
n
=
ax
n
−
1
+
b
,
n
≥
1.
If
a
=
1, we have an arithmetic sequence whose first term is
α
and whose
common difference is
b
. In this case
x
n
=
α
+
nb
.
If
a
=
1, we perform the translation
x
n
=
y
n
+
β
, where
β
=
b
1
−
a
. In this
case
(
y
n
)
n
≥
0
satisfies the recursion
y
0
=
α
−
β
,
y
n
=
ay
n
−
1
,
n
≥
1, which is
a geometric sequence whose first term is
α
−
β
and whose ratio is
a
. We obtain
y
n
=
(α
−
β)
a
n
; hence
x
n
=
α
−
b
1
−
a
a
n
+
b
1
−
a
,
n
≥
0
.
Problem 9.3.8.
Let a and b be positive integers and let the sequence
(
x
n
)
n
≥
0
be
defined by x
0
=
1
and x
n
+
1
=
ax
n
+
b for all nonnegative integers n. Prove
that for any choice of a and b, the sequence
(
x
n
)
n
≥
0
contains infinitely many
composite numbers.
(1995 German Mathematical Olympiad)
Solution.
The case
a
=
1 gives
x
n
=
1
+
b
+ · · · +
b
n
−
1
=
b
n
−
1
b
−
1
,
n
≥
0. If
n
is
even,
n
=
2
k
, then
x
n
=
(
b
k
+
1
)
b
k
−
1
b
−
1
=
(
b
k
+
1
)
x
k
,
k
≥
0
and we are done.
Let
a
=
1.
Assume to the contrary that
x
n
is composite for only finitely many
n
. Take
N
larger than all such
n
, so that
x
m
is prime for all
n
>
N
. Choose such a prime
x
m
=
p
not dividing
a
−
1 (this excludes only finitely many candidates). Let
t
be
such that
t
(
1
−
a
)
≡
b
(
mod
p
)
; then
x
n
+
1
−
t
≡
ax
n
+
b
−
b
=
a
(
x
n
−
t
) (
mod
p
).
In particular,
x
m
+
p
−
1
=
t
+
(
x
m
+
p
−
1
−
t
)
≡
t
+
a
p
−
1
(
x
m
−
t
)
≡
(
1
−
a
p
−
1
)
t
≡
0
(
mod
p
).
However,
x
m
+
p
−
1
is a prime greater than
p
, yielding a contradiction. Hence
infinitely many of the
x
n
are composite.
Problem 9.3.9.
Find a
n
if a
0
=
1
and a
n
+
1
=
2
a
n
+
3
a
2
n
−
2
, n
≥
0
.
Solution.
We have
(
a
n
+
1
−
2
a
n
)
2
=
3
a
2
n
−
2, so
a
2
n
+
1
−
4
a
n
+
1
a
n
+
a
2
n
+
2
=
0
,
n
≥
0
.
Then
a
2
n
−
4
a
n
a
n
−
1
+
a
2
n
−
1
+
2
=
0
,
n
≥
1
;
188
I Fundamentals, 9. Some Special Problems in Number Theory
hence, by subtraction,
a
2
n
+
1
−
a
2
n
−
1
−
4
a
n
(
a
n
+
1
−
a
n
−
1
)
=
0
for all
n
≥
1. Because it is clear that
(
a
n
)
n
≥
0
is increasing, we have
a
n
+
1
−
a
n
−
1
=
0, for all
n
≥
1, so
a
n
+
1
+
a
n
−
1
−
4
a
n
=
0
,
n
≥
1
,
that is,
a
n
+
1
=
4
a
n
−
a
n
−
1
,
n
≥
1. Moreover,
a
0
=
1 and
a
1
=
3. The character-
istic equation is
t
2
−
4
t
+
1
=
0, whose roots are
t
1
=
2
+
√
3 and
t
2
=
2
−
√
3.
We obtain
a
n
=
1
2
√
3
7
(
1
+
√
3
)(
2
+
√
3
)
n
−
(
1
−
√
3
)(
2
−
√
3
)
n
8
,
n
≥
0
.
We can also write
a
n
as follows:
a
n
=
1
√
3
1
+
√
3
2
2
n
+
1
−
1
−
√
3
2
2
n
+
1
,
n
≥
0
.
Note that from
a
0
=
1,
a
1
=
3, and
a
n
+
1
=
4
a
n
−
a
n
−
1
it follows by strong
induction that
a
n
is a positive integer for all
n
.
Problem 9.3.10.
Consider the sequence
{
a
n
}
such that a
0
=
4
, a
1
=
22
, and
a
n
−
6
a
n
−
1
+
a
n
−
2
=
0
for n
≥
2
. Prove that there exist sequences
{
x
n
}
and
{
y
n
}
of positive integers such that
a
n
=
y
2
n
+
7
x
n
−
y
n
for any n
≥
0
.
(2001 Bulgarian Mathematical Olympiad)
Solution.
Consider the sequence
{
c
n
}
of positive integers such that
c
0
=
2,
c
1
=
1, and
c
n
=
2
c
n
−
1
+
c
n
−
2
for
n
≥
2.
We prove by induction that
a
n
=
c
2
n
+
2
for
n
≥
0. We check the base cases
of
a
0
=
4
=
c
2
and
a
1
=
9
=
c
4
. Then, for any
k
≥
2, assuming that the claim
holds for
n
=
k
−
2 and
n
=
k
−
1,
c
2
k
+
2
=
2
c
2
k
+
1
+
c
2
k
=
2
(
2
c
2
k
+
c
2
k
−
1
)
+
a
k
−
1
=
4
c
2
k
+
(
c
2
k
−
c
2
k
−
2
)
+
a
k
−
1
=
6
a
k
−
1
−
a
k
−
2
=
a
k
,
Do'stlaringiz bilan baham: |
