|
9.3. Sequences of Integers
195
Problem 9.3.32.
Define the sequence
{
x
n
}
n
≥
0
by
x
0
=
0 and
x
n
=
⎧
⎪
⎨
⎪
⎩
x
n
−
1
+
3
r
+
1
−
1
2
,
if
n
=
3
r
(
3
k
+
1
),
x
n
−
1
−
3
r
+
1
+
1
2
,
if
n
=
3
r
(
3
k
+
2
),
where
k
and
r
are nonnegative integers. Prove that every integer appears exactly
once in this sequence.
(1999 Iranian Mathematical Olympiad)
Problem 9.3.33.
Suppose that
a
1
,
a
2
, . . .
is a sequence of natural numbers such
that for all natural numbers
m
and
n
, gcd
(
a
m
,
a
n
)
=
a
gcd
(
m
,
n
)
. Prove that there
exists a sequence
b
1
,
b
2
, . . .
of natural numbers such that
a
n
=
d
|
n
b
d
for all
integers
n
≥
1.
(2001 Iranian Mathematical Olympiad)
10
Problems Involving
Binomial Coefficients
10.1
Binomial Coefficients
One of the main problems leading to the consideration of binomial coefficients is
the expansion of
(
a
+
b
)
n
, where
a
,
b
are complex numbers and
n
is a positive
integer. It is well known that
(
a
+
b
)
n
=
n
0
a
n
+
n
1
a
n
−
1
b
+ · · · +
n
n
−
1
ab
n
−
1
+
n
n
b
n
,
where
n
k
=
n
!
k
!
(
n
−
k
)
!
,
k
=
0
,
1
, . . . ,
n
with the convention 0
! =
1. The integers
n
0
,
n
1
, . . . ,
n
n
are called
binomial coefficients
. They can be obtained recursively
by using
Pascal’s
1
triangle
,
1
1
1
1
2
1
1
3
3
1
1
4
6
4
1
1
5
10
10
5
1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
in which every entry different from 1 is the sum of the two entries above and
adjacent to it.
The fundamental properties of the binomial coefficients are the following:
1
Blaise Pascal (1623–1662) was a very influential French mathematician and philosopher who
contributed to many areas of mathematics.
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
T. Andreescu and D. Andrica,
Number Theory
,
DOI: 10.1007/b11856_10,
197
198
I Fundamentals, 10. Problems Involving Binomial Coefficients
(1) (symmetry)
n
k
=
n
n
−
k
;
(2) (Pascal’s triangle property)
n
k
+
1
=
n
−
1
k
+
1
+
n
−
1
k
;
(3) (monotonicity)
n
0
<
n
1
<
· · ·
<
n
#
n
−
1
2
$
+
1
=
n
n
2
;
(4) (sum of binomial coefficients)
n
0
+
n
1
+ · · · +
n
n
=
2
n
;
(5) (alternating sum)
n
0
−
n
1
+ · · · +
(
−
1
)
n
n
n
=
0,
n
≥
1;
(6) (Vandermonde property)
"
k
i
=
0
m
i
n
k
−
i
=
m
+
n
k
;
(7) If
p
is a prime, then
p
|
p
k
,
k
=
1
, . . . ,
p
−
1.
Problem 10.1.1.
Let n be an odd positive integer. Prove that the set
n
1
,
n
2
, . . . ,
n
n
−
1
2
contains an odd number of odd numbers.
Solution.
For
n
=
1 the claim is clear, so let
n
≥
3.
Define
S
n
=
n
1
+
n
2
+ · · · +
n
n
−
1
2
. Then
2
S
n
=
n
1
+
n
2
+ · · · +
n
n
−
1
=
2
n
−
2
,
or
S
n
=
2
n
−
1
−
1. Because
S
n
is odd it follows that the sum
S
n
contains an odd
number of odd terms, as desired.
Problem 10.1.2.
Determine all positive integers n
≥
3
such that
2
2000
is divisible
by
1
+
n
1
+
n
2
+
n
3
.
(1998 Chinese Mathematical Olympiad)
Solution.
The solutions are
n
=
3
,
7
,
23. Since 2 is a prime,
1
+
n
1
+
n
2
+
n
3
=
2
k
for some positive integer
k
≤
2000. We have
1
+
n
1
+
n
2
+
n
3
=
(
n
+
1
)(
n
2
−
n
+
6
)
6
,
10.1. Binomial Coefficients
199
i.e.,
(
n
+
1
)(
n
2
−
n
+
6
)
=
3
×
2
k
+
1
. Let
m
=
n
+
1; then
m
≥
4 and
m
(
m
2
−
3
m
+
8
)
=
3
×
2
k
+
1
. We consider the following two cases:
(a)
m
=
2
s
. Since
m
≥
4,
s
≥
2. We have
2
2
s
−
3
×
2
s
+
8
=
m
2
−
3
m
+
8
=
3
×
2
t
for some positive integer
t
. If
s
≥
4, then
8
≡
3
×
2
t
(
mod 16
)
⇒
2
t
=
8
⇒
m
2
−
3
m
+
8
=
24
⇒
m
(
m
−
3
)
=
16
,
which is impossible. Thus either
s
=
3,
m
=
8,
t
=
4,
n
=
7, or
s
=
2,
m
=
4,
t
=
2,
n
=
3.
(b)
m
=
3
×
2
u
. Since
m
≥
4,
m
>
4 and
u
≥
1. We have
9
×
2
2
u
−
9
×
2
u
+
8
=
m
2
−
3
m
+
8
=
2
v
for some positive integer
v
. It is easy to check that there is no solution for
v
when
u
=
1
,
2. If
u
≥
4, we have 8
≡
2
v
(
mod 16
)
⇒
v
=
3 and
m
(
m
−
3
)
=
0,
which is impossible. So
u
=
3,
m
=
3
×
2
3
=
24,
v
=
9,
n
=
23.
Problem 10.1.3.
Let m and n be integers such that
1
≤
m
≤
n. Prove that m is a
divisor of
n
m
−
1
k
=
0
(
−
1
)
k
n
k
.
(2001 Hungarian Mathematical Olympiad)
Solution.
We can write the given expression as follows:
n
m
−
1
k
=
0
(
−
1
)
k
n
k
=
n
m
−
1
k
=
0
(
−
1
)
k
n
−
1
k
+
n
−
1
k
−
1
=
n
m
−
1
k
=
0
(
−
1
)
k
n
−
1
k
+
n
m
−
1
k
=
1
(
−
1
)
k
n
−
1
k
−
1
=
n
m
−
1
k
=
0
(
−
1
)
k
n
−
1
k
−
n
m
−
2
k
=
0
(
−
1
)
k
n
−
1
k
=
n
(
−
1
)
m
−
1
n
−
1
m
−
1
=
m
(
−
1
)
m
−
1
n
m
.
The final expression is clearly divisible by
m
.
200
I Fundamentals, 10. Problems Involving Binomial Coefficients
Problem 10.1.4.
Show that for any positive integer n, the number
S
n
=
2
n
+
1
0
·
2
2
n
+
2
n
+
1
2
·
2
2
n
−
2
·
3
+ · · · +
2
n
+
1
2
n
·
3
n
is the sum of two consecutive perfect squares.
(1999 Romanian International Mathematical Olympiad Team Selection Test)
Solution.
It is easy to see that:
S
n
=
1
4
7
(
2
+
√
3
)
2
n
+
1
+
(
2
−
√
3
)
2
n
+
1
8
.
The required property says that there exists
k
>
0 such that
S
n
=
(
k
−
1
)
2
+
k
2
,
or, equivalently,
2
k
2
−
2
k
+
1
−
S
n
=
0
.
The discriminant of this equation is
=
4
(
2
S
n
−
1
)
, and, using
1
+
√
3
√
2
2
=
2
+
√
3, after the usual computations, we obtain
=
(
1
+
√
3
)
2
n
+
1
+
(
1
−
√
3
)
2
n
+
1
2
n
2
.
After solving the equation, we find that
k
=
2
n
+
1
+
(
1
+
√
3
)
2
n
+
1
+
(
1
−
√
3
)
2
n
+
1
2
n
+
2
.
Therefore, it is sufficient to prove that
k
is an integer. Let us set
E
m
=
(
1
+
√
3
)
m
+
(
1
−
√
3
)
m
, where
m
is a positive integer. Clearly,
E
m
is an integer. We
shall prove that 2
m
2
divides
E
m
. For
E
0
=
2,
E
1
=
2,
E
2
=
8, the assertion is
true. Moreover, the numbers
E
m
satisfy the relation
E
m
=
2
E
m
−
1
+
2
E
m
−
2
.
The property now follows by induction.
Problem 10.1.5.
Prove that for every pair m
,
k of natural numbers, m has a
unique representation in the form
m
=
a
k
k
+
a
k
−
1
k
−
1
+ · · · +
a
t
t
,
where
a
k
>
a
k
−
1
>
· · ·
>
a
t
≥
t
≥
1
.
(1996 Iranian Mathematical Olympiad)
Do'stlaringiz bilan baham: |
