|
II Solutions, 9. Some Special Problems in Number Theory
we have
λ
m
+
μ
m
=
k
(λ
m
−
1
+
μ
m
−
1
)
−
(λ
m
−
2
+
μ
m
−
2
),
leading to an easy proof by induction that
λ
m
+
μ
m
is an integer for all nonnegative
integers
m
. The solution is complete.
9.3.2
Problems Involving Linear Recursive Relations
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)
Solution.
We will show that
x
m
|
x
km
, and then show that
gcd
(
x
m
,
x
m
−
1
)
=
1.
First, consider our sequence modulo
x
m
for some
m
. Each
x
k
+
1
is uniquely
determined by
x
k
,
x
k
−
1
and the parity of
k
. Express each
x
i
as a function
f
i
(
a
,
b
)
.
We have
x
i
≡
f
i
(
a
,
b
)
x
1
(
mod
x
m
)
. Suppose
x
r
≡
0
(
mod
x
m
)
for some
r
.
Since each term is a linear combination of two preceding ones,
x
i
+
r
≡
f
i
(
a
,
b
)
x
r
+
1
(
mod
x
m
)
if
m
is even
,
(1)
x
i
+
r
≡
f
i
(
b
,
a
)
x
r
+
1
(
mod
x
m
)
if
m
is odd
.
(2)
Now we need to prove the following statement.
Lemma.
The function f
i
(
a
,
b
)
is symmetric for any odd i .
Proof.
We will prove also that for
i
even,
f
i
(
a
,
b
)
is a symmetric function multi-
plied by
a
. Now we are to prove that
f
2
k
−
1
(
a
,
b
)
is symmetric and
f
2
k
−
2
(
a
,
b
)
=
ag
2
k
−
2
(
a
,
b
)
, where
g
2
k
−
2
is symmetric too, for any positive integer
k
. Proceed
by induction on
k
. For
k
=
1 we have
f
1
(
a
,
b
)
=
1 and
g
0
(
a
,
b
)
=
0. Suppose
that
f
2
k
−
1
(
a
,
b
)
is symmetric and
f
2
k
−
2
(
a
,
b
)
=
ag
2
k
−
2
(
a
,
b
)
, where
g
2
k
−
2
(
a
,
b
)
is symmetric too. Then we can write
f
2
k
(
a
,
b
)
=
x
2
k
=
ax
2
k
−
1
−
x
2
k
−
2
=
a
(
x
2
k
−
1
−
g
2
k
−
2
(
a
,
b
))
=
a
(
f
2
k
−
1
(
a
,
b
)
−
g
2
k
−
2
(
a
,
b
))
and
f
2
k
+
1
(
a
,
b
)
=
x
2
k
+
1
=
abx
2
k
−
1
−
bx
2
k
−
2
−
x
2
k
−
1
=
abx
2
k
−
1
−
abg
2
k
−
2
−
x
2
k
−
1
=
(
ab
−
1
)
f
2
k
−
1
(
a
,
b
)
−
abg
2
k
−
2
(
a
,
b
).
9.3. Sequences of Integers
339
Thus
f
2
k
+
1
and
g
2
k
are symmetric too, which completes the step of induction.
Remark.
An alternative proof for lemma is the following. Let
y
n
=
√
bx
n
for
n
even and
y
n
=
√
ax
n
for
n
odd. Then one sees that
y
n
=
√
aby
n
−
1
−
y
n
−
2
for all
n
. It follows that
f
2
n
+
1
=
y
2
n
+
1
/
√
a
and
g
2
n
=
y
2
n
/(
a
√
b
)
are symmetric.
Now we are to prove that
x
m
|
x
km
. Proceed by induction on
k
. For
k
=
0 and
k
=
1 this statement is true. Let
x
m
|
x
km
. Then from (1) and (2) putting
r
=
km
and
i
=
m
, we obtain the following. If
km
is even, then
x
m
(
k
+
1
)
≡
f
m
(
a
,
b
)
x
km
+
1
≡
x
m
x
km
+
1
≡
0
(
mod
x
m
).
For
km
odd,
m
is odd too, and
f
m
(
a
,
b
)
=
f
m
(
b
,
a
)
. Hence, we have
x
m
(
k
+
1
)
≡
f
m
(
b
,
a
)
x
km
+
1
≡
f
m
(
a
,
b
)
x
km
+
1
≡
x
m
x
km
+
1
≡
0
(
mod
x
m
).
So, for each pair of nonnegative integers
k
,
m
we have
x
m
|
x
km
.
Since the product
x
n
+
1
x
n
+
2
· · ·
x
n
+
m
has
m
terms, one term’s index is divisi-
ble by
m
and another’s index is divisible by
m
−
1. Thus both
x
m
and
x
m
−
1
divide
the product. If we can show that
x
m
is relatively prime to
x
m
−
1
, we will be done.
We will prove this by induction. For the base case,
x
0
is relatively prime to
x
1
.
Now,
x
2
n
=
ax
2
n
−
1
−
x
2
n
−
2
. Any prime factor common to
x
2
n
and
x
2
n
−
1
must
also divide
x
2
n
−
2
, but because
x
2
n
−
2
is relatively prime to
x
2
n
−
1
, there is no such
prime factor. A similar argument holds for
x
2
n
+
1
because
x
2
n
+
1
=
bx
2
n
−
x
2
n
−
1
.
Thus
x
m
x
m
−
1
|
(
x
n
+
1
x
n
+
2
· · ·
x
n
+
m
)
.
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)
First solution.
The “if” direction of the claim is easily proved by induction on
n
;
we prove the “only if” direction by contradiction. Suppose, to the contrary, that
there exist pairs satisfying the equation but not of the described form; let
(
a
,
b
)
be such a pair with minimal sum
a
+
b
. We claim that
(
c
,
a
)
=
(
m
2
a
−
b
,
a
)
is
another such a pair but with smaller sum
c
+
a
, which leads to a contradiction.
Taking cases on the value of
a
:
(a)
a
=
0. Then
(
a
,
b
)
=
(
0
,
m
)
=
(
a
0
,
a
1
)
, a contradiction.
(b)
a
=
m
. Then
(
a
,
b
)
=
(
m
,
m
3
)
=
(
a
1
,
a
2
)
, a contradiction.
(c)
a
=
1. Then
b
≥
1
=
1 and
(
b
+
1
)
|
(
b
2
+
1
)
; but
(
b
+
1
)
|
(
b
2
−
1
)
,
thus
(
b
+
1
)
| [
(
b
2
+
1
)
−
(
b
2
−
1
)
] =
2. We have
b
=
1, thus
m
=
1 and
(
a
,
b
)
=
(
1
,
1
)
=
(
a
1
,
a
2
)
, a contradiction.
340
Do'stlaringiz bilan baham: |
