|
9.3. Sequences of Integers
189
so the claim holds for
n
=
k
as well, and the induction is complete.
For
n
≥
1,
a
n
+
1
a
n
a
n
+
2
a
n
+
1
=
0 1
1 2
a
n
a
n
−
1
a
n
+
1
a
n
and
a
n
+
1
a
n
a
n
+
2
a
n
+
1
=
0 1
1 2
a
n
a
n
−
1
a
n
+
1
a
n
= −
a
n
a
n
−
1
a
n
+
1
a
n
.
Thus, for
n
≥
0,
c
2
n
+
1
−
c
n
c
n
+
2
=
(
−
1
)
n
(
c
2
1
−
c
0
c
2
)
=
(
−
1
)
n
(
1
2
−
2
·
4
)
=
(
−
1
)
n
(
−
7
).
In particular, for all
n
≥
0,
c
2
2
n
+
1
−
c
2
n
a
n
=
c
2
2
n
+
1
−
c
2
n
c
2
n
+
2
=
(
−
1
)
2
n
(
−
7
)
= −
7
and
a
n
=
c
2
2
n
+
1
+
7
c
2
n
.
We may therefore take
y
n
=
c
2
n
+
1
and
x
n
=
c
2
n
+
y
n
.
Problem 9.3.11.
The sequence a
1
,
a
2
, . . .
is defined by the initial conditions a
1
=
20
, a
2
=
30
and the recursion a
n
+
2
=
3
a
n
+
1
−
a
n
for n
≥
1
. Find all positive
integers n for which
1
+
5
a
n
a
n
+
1
is a perfect square.
(2002 Balkan Mathematical Olympiad)
Solution.
The only solution is
n
=
3. We can check that 20
·
30
·
5
+
1
=
3001 and
30
·
70
·
5
+
1
=
10501 are not perfect squares, while 70
·
180
·
5
+
1
=
63001
=
251
2
is a perfect square. Then we have only to prove that 1
+
5
a
n
a
n
+
1
is not a perfect
square for
n
≥
4. First, we will prove a lemma.
Lemma.
For any integer n
≥
2
,
a
2
n
+
500
=
a
n
−
1
a
n
+
1
.
Proof.
We will prove this by induction on
n
. In the base case, 30
2
+
500
=
1400
=
20
·
70. Now assume that
a
2
n
+
500
=
a
n
−
1
a
n
+
1
. Then
a
n
a
n
+
2
=
(
3
a
n
+
1
−
a
n
)(
a
n
)
=
3
a
n
+
1
a
n
−
a
2
n
=
3
a
n
+
1
a
n
−
(
a
n
−
1
a
n
+
1
−
500
)
=
500
+
a
n
+
1
(
3
a
n
−
a
n
−
1
)
=
500
+
a
2
n
+
1
,
proving the inductive step. Therefore the desired statement is true from in-
duction.
190
I Fundamentals, 9. Some Special Problems in Number Theory
Now, for
n
≥
4,
(
a
n
+
a
n
+
1
)
2
=
a
2
n
+
a
2
n
+
1
+
2
a
n
a
n
+
1
. But
a
2
n
+
1
=
9
a
2
n
+
a
2
n
−
1
−
6
a
n
−
1
a
n
,
so
(
a
n
+
a
n
+
1
)
2
=
2
a
n
a
n
+
1
+
3
a
n
(
3
a
n
−
a
n
−
1
)
+
a
2
n
−
1
+
a
2
n
−
3
a
n
a
n
−
1
=
5
a
n
a
n
+
1
+
a
2
n
−
1
−
a
n
a
n
−
2
=
5
a
n
a
n
+
1
+
a
2
n
−
1
−
(
a
2
n
−
1
+
500
)
=
5
a
n
a
n
+
1
−
500
,
by the lemma and the definition of
a
.
Therefore
(
a
n
+
a
n
+
1
)
2
=
5
a
n
a
n
+
1
−
500
<
5
a
n
a
n
+
1
+
1. Since
a
n
is increas-
ing and
n
≥
4,
a
n
+
a
n
+
1
≥
180
+
470
=
650
,
so
(
a
n
+
a
n
+
1
+
1
)
2
=
(
a
n
+
a
n
+
1
)
2
+
2
(
a
n
+
a
n
+
1
)
+
1
> (
a
n
+
a
n
+
1
)
2
+
501
=
5
a
n
a
n
+
1
+
1
.
Because two adjacent integers have squares above and below 5
a
n
a
n
+
1
+
1,
that value is not a perfect square for
n
≥
4.
Additional Problems
Problem 9.3.12.
Let
a
,
b
be integers greater than 1. The sequence
x
1
,
x
2
, . . .
is
defined by the initial conditions
x
0
=
0,
x
1
=
1 and the recursion
x
2
n
=
ax
2
n
−
1
−
x
2
n
−
2
,
x
2
n
+
1
=
bx
2
n
−
x
2
n
−
1
for
n
≥
1. Prove that for any natural numbers
m
and
n
, the product
x
n
+
m
x
n
+
m
−
1
· · ·
x
n
+
1
is divisible by
x
m
x
m
−
1
.
(2001 St. Petersburg City Mathematical Olympiad)
Problem 9.3.13.
Let
m
be a positive integer. Define the sequence
{
a
n
}
n
≥
0
by
a
0
=
0,
a
1
=
m
, and
a
n
+
1
=
m
2
a
n
−
a
n
−
1
for
n
≥
1. Prove that an ordered pair
(
a
,
b
)
of nonnegative integers, with
a
≤
b
, is a solution of the equation
a
2
+
b
2
ab
+
1
=
m
2
if and only if
(
a
,
b
)
=
(
a
n
,
a
n
+
1
)
for some
n
≥
0.
(1998 Canadian Mathematical Olympiad)
9.3. Sequences of Integers
191
Problem 9.3.14.
Let
b
,
c
be positive integers, and define the sequence
a
1
,
a
2
, . . .
by
a
1
=
b
,
a
2
=
c
, and
a
n
+
2
= |
3
a
n
+
1
−
2
a
n
|
for
n
≥
1. Find all such
(
b
,
c
)
for which the sequence
a
1
,
a
2
, . . .
has only a finite
number of composite terms.
(2002 Bulgarian Mathematical Olympiad)
9.3.3
Nonstandard Sequences of Integers
Problem 9.3.15.
Let k be a positive integer. The sequence a
n
is defined by a
1
=
1
,
and for n
≥
2
, a
n
is the nth positive integer greater than a
n
−
1
which is congruent
to n modulo k. Find a
n
is closed form.
(1997 Austrian Mathematical Olympiad)
Solution.
We have
a
n
=
n
(
2
+
(
n
−
1
)
k
)
2
. If
k
=
2, then
a
n
=
n
2
. First, observe
that
a
1
≡
1
(
mod
k
)
. Thus, for all
n
,
a
n
≡
n
(
mod
k
)
, and the first positive
integer greater than
a
n
−
1
which is congruent to
n
modulo
k
must be
a
n
−
1
+
1. The
n
th positive integer greater than
a
n
−
1
that is congruent to
n
modulo
k
is simply
(
n
−
1
)
k
more than the first positive integer greater than
a
n
−
1
which satisfies that
condition. Therefore,
a
n
=
a
n
−
1
+
1
+
(
n
−
1
)
k
. Solving this recursion gives
a
n
=
n
+
(
n
−
1
)
n
2
k
.
Problem 9.3.16.
Let a
1
=
19
, a
2
=
98
. For n
≥
1
, define a
n
+
2
to be the remainder
of a
n
+
a
n
+
1
when it is divided by
100
. What is the remainder when
a
2
1
+
a
2
2
+ · · · +
a
2
1998
is divided by 8?
(1998 United Kingdom Mathematical Olympiad)
Solution.
The answer is 0. Consider
a
n
(
mod 4
)
which is not changed by taking
the remainder divided by 100, there’s the cycle 3, 2, 1, 3, 0, 3 which repeats 333
times. Then
a
2
1
+
a
2
2
+ · · · +
a
2
1998
≡
333
(
1
+
4
+
1
+
1
+
0
+
1
)
≡
0
(
mod 8
),
as claimed.
Problem 9.3.17.
A sequence of integers
{
a
n
}
n
≥
1
satisfies the following recursion
relation:
a
n
+
1
=
a
3
n
+
1999
for
n
=
1
,
2
, . . . .
Prove that there exists at most one n for which a
n
is a perfect square.
(1999 Austrian–Polish Mathematics Competition)
192
Do'stlaringiz bilan baham: |
