MathDB
Problems
Contests
International Contests
Danube Competition in Mathematics
2005 Danube Mathematical Olympiad
2
Binomial sum is divisible by 2^(n-1) - not that surprising
Binomial sum is divisible by 2^(n-1) - not that surprising
Source:
February 11, 2006
floor function
combinatorics proposed
combinatorics
Problem Statement
Prove that the sum:
S
n
=
(
n
1
)
+
(
n
3
)
⋅
2005
+
(
n
5
)
⋅
200
5
2
+
.
.
.
=
∑
k
=
0
⌊
n
−
1
2
⌋
(
n
2
k
+
1
)
⋅
200
5
k
S_n=\binom{n}{1}+\binom{n}{3}\cdot 2005+\binom{n}{5}\cdot 2005^2+...=\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}\binom{n}{2k+1}\cdot 2005^k
S
n
=
(
1
n
)
+
(
3
n
)
⋅
2005
+
(
5
n
)
⋅
200
5
2
+
...
=
k
=
0
∑
⌊
2
n
−
1
⌋
(
2
k
+
1
n
)
⋅
200
5
k
is divisible by
2
n
−
1
2^{n-1}
2
n
−
1
for any positive integer
n
n
n
.
Back to Problems
View on AoPS