|
5.2. Mathematical Induction
95
(where
d
1
,
d
2
, . . . ,
d
n
are the
n
divisors arranged in increasing order), namely,
multiplying the above relation by
n
+
1. This yields
(
n
+
1
)
! =
(
n
+
1
)
d
1
+
(
n
+
1
)
d
2
+ · · · +
(
n
+
1
)
d
n
=
d
1
+
nd
1
+
(
n
+
1
)
d
2
+ · · · +
(
n
+
1
)
d
n
.
We split
(
n
+
1
)
d
1
into
d
1
+
nd
1
, thus getting
n
+
1 summands, as needed. Of
them, only the second one might not be a divisor of
(
n
+
1
)
!
. We would like to
ensure that it is such a divisor, too. Hence the idea of insisting that
d
1
=
1.
Problem 5.2.3.
Prove that there are infinitely many numbers not containing the
digit
0
that are divisible by the sum of their digits.
Solution.
Let us prove by induction that 11
. . .
1
3
n
is a good choice. The base case
is easily verified, and for the inductive step we have
11
. . .
1
3
n
+
1
=
10
3
−
1
9
=
(
10
3
n
)
3
−
1
9
=
10
3
n
+
1
−
1
9
(
10
2
·
3
n
+
10
3
n
+
1
)
=
11
. . .
1
3
n
·
N
,
where
N
is a multiple of 3, and the conclusion follows.
Problem 5.2.4.
Let n be a positive integer. Let O
n
be the number of
2
n-tuples
(
x
1
, . . . ,
x
n
,
y
1
, . . . ,
y
n
)
with values in
0
or
1
for which the sum x
1
y
1
+· · ·+
x
n
y
n
is odd, and let E
n
be the number of
2
n-tuples for which the sum is even. Prove
that
O
n
E
n
=
2
n
−
1
2
n
+
1
.
(1997 Iberoamerican Mathematical Olympiad)
Solution.
We prove by induction that
O
n
=
2
2
n
−
1
−
2
n
−
1
and
E
n
=
2
2
n
−
1
+
2
n
−
1
,
which will give the desired ratio.
The base case is
n
=
1. This case works because
O
1
=
1
=
2
1
−
2
0
and
E
1
=
3
=
2
1
+
2
0
.
For the inductive step, we assume that this is true for
n
=
k
; then
x
1
y
1
+ · · · +
x
k
y
k
is even for
(
2
2
k
−
1
+
2
k
−
1
)
2
k
-tuples and odd for
(
2
2
k
−
1
−
2
k
−
1
)
2
k
-tuples.
Now,
x
1
y
1
+ · · · +
x
k
+
1
y
k
+
1
is odd if and only if either
x
1
y
1
+ · · · +
x
k
y
k
is odd
96
I Fundamentals, 5. Basic Principles in Number Theory
and
x
k
+
1
y
k
+
1
is even or
x
1
y
1
+ · · · +
x
k
y
k
is even and
x
k
+
1
y
k
+
1
is odd. Clearly
x
k
+
1
y
k
+
1
can be odd in one way and even in three ways, so
O
k
+
1
=
3
(
2
2
k
−
1
−
2
k
−
1
)
+
2
2
k
−
1
+
2
k
−
1
=
2
2
(
k
+
1
)
−
1
−
2
(
k
+
1
)
−
1
and
E
k
+
1
=
2
2
(
k
+
1
)
−
O
k
+
1
, which completes the induction.
Problem 5.2.5.
Prove that for all integers n
≥
3
, there exist odd positive integers
x
,
y such that
7
x
2
+
y
2
=
2
n
.
(1996 Bulgarian Mathematical Olympiad)
Solution.
We will prove that there exist odd positive integers
x
n
,
y
n
such that
7
x
2
n
+
y
2
n
=
2
n
,
n
≥
3.
For
n
=
3, we have
x
3
=
y
3
=
1. Now suppose that for a given integer
n
≥
3
we have odd integers
x
n
,
y
n
satisfying 7
x
2
n
+
y
2
n
=
2
n
. We shall exhibit a pair
(
x
n
+
1
,
y
n
+
1
)
of odd positive integers such that 7
x
2
n
+
1
+
y
2
n
+
1
=
2
n
+
1
. In fact,
7
x
n
±
y
n
2
2
+
7
x
n
∓
y
n
2
2
=
2
(
7
x
2
n
+
y
2
n
)
=
2
n
+
1
.
Precisely one of the numbers
x
n
+
y
n
2
and
|
x
n
−
y
n
|
2
is odd (since their sum is the
larger of
x
n
and
y
n
, which is odd). If, for example,
x
n
+
y
n
2
is odd, then
7
x
n
−
y
n
2
=
3
x
n
+
x
n
−
y
n
2
is also odd (as the sum of an odd and an even number); hence in this case we may
choose
x
n
+
1
=
x
n
+
y
n
2
and
y
n
+
1
=
7
x
n
−
y
n
2
.
If
x
n
−
y
n
2
is odd, then
7
x
n
+
y
n
2
=
3
x
n
+
x
n
+
y
n
2
,
so we can choose
x
n
+
1
=
|
x
n
−
y
n
|
2
and
y
n
+
1
=
7
x
n
+
y
n
2
.
This problem goes back to Euler.
Problem 5.2.6.
Let f
(
x
)
=
x
3
+
17
. Prove that for each natural number n, n
≥
2
,
there is a natural number x for which f
(
x
)
is divisible by
3
n
but not by
3
n
+
1
.
(1999 Japanese Mathematical Olympiad)
5.2. Mathematical Induction
97
Solution.
We prove the result by induction on
n
. If
n
=
2, then
x
=
1 suffices.
Now suppose that the claim is true for some
n
≥
2, that is, there is a natural
number
y
such that
y
3
+
17 is divisible by 3
n
but not 3
n
+
1
. We prove that the
claim is true for
n
+
1.
Suppose we have integers
a
,
m
such that
a
is not divisible by 3 and
m
≥
2.
Then
a
2
≡
1
(
mod 3
)
and thus 3
m
a
2
≡
3
m
(
mod 3
m
+
1
)
. Also, because
m
≥
2
we have 3
m
−
3
≥
2
m
−
1
≥
m
+
1. Hence
(
a
+
3
m
−
1
)
3
≡
a
3
+
3
m
a
2
+
3
2
m
−
1
a
+
3
3
m
−
3
≡
a
3
+
3
m
(
mod 3
m
+
1
).
Because
y
3
+
17 is divisible by 3
n
, it is congruent to either 0, 3
n
, or 2
·
3
n
mod-
ulo 3
n
+
1
. Because 3 does not divide 17, 3 cannot divide
y
either. Hence applying
our result from the previous paragraph twice, once with
(
a
,
m
)
=
(
y
,
n
)
and once
with
(
a
,
m
)
=
(
y
+
3
n
−
1
,
n
)
, we find that 3
n
+
1
must divide either
(
y
+
3
n
−
1
)
3
+
17
or
(
y
+
2
·
3
n
−
1
)
3
+
17.
Hence there exists a natural number
x
not divisible by 3 such that 3
n
+
1
|
x
3
+
17. If 3
n
+
2
does not divide
x
3
+
17, we are done. Otherwise, we claim that
the number
x
=
x
+
3
n
suffices. Because
x
=
x
+
3
n
−
1
+
3
n
−
1
+
3
n
−
1
, the
result from the previous paragraphs tells us that
x
3
≡
x
3
+
3
n
+
3
n
+
3
n
≡
x
3
(
mod 3
n
+
1
)
. Thus 3
n
+
1
|
x
3
+
17 as well. On the other hand, because
x
=
x
+
3
n
,
we have
x
3
≡
x
3
+
3
n
+
1
≡
x
3
(
mod 3
n
+
2
)
. It follows that 3
n
+
2
does not divide
x
3
+
17, as desired. This completes the inductive step.
Additional Problems
Problem 5.2.7.
Let
p
be an odd prime. The sequence
(
a
n
)
n
≥
0
is defined as fol-
lows:
a
0
=
0,
a
1
=
1
, . . .
,
a
p
−
2
=
p
−
2, and for all
n
≥
p
−
1,
a
n
is the least
positive integer that does not form an arithmetic sequence of length
p
with any of
the preceding terms. Prove that, for all
n
,
a
n
is the number obtained by writing
n
in base
p
−
1 and reading the result in base
p
.
(1995 USA Mathematical Olympiad)
Problem 5.2.8.
Suppose that
x
,
y
, and
z
are natural numbers such that
x y
=
z
2
+
1. Prove that there exist integers
a
,
b
,
c
, and
d
such that
x
=
a
2
+
b
2
,
y
=
c
2
+
d
2
, and
z
=
ac
+
bd
.
(Euler’s problem)
Problem 5.2.9.
Find all pairs of sets
A
,
B
that satisfy the following conditions:
(i)
A
∪
B
=
Z
;
(ii) if
x
∈
A
, then
x
−
1
∈
B
;
(iii) if
x
∈
B
and
y
∈
B
, then
x
+
y
∈
A
.
(2002 Romanian International Mathematical Olympiad Team Selection Test)
98
Do'stlaringiz bilan baham: |
