MathDB
Problems
Contests
Undergraduate contests
Putnam
1984 Putnam
B5
B5
Part of
1984 Putnam
Problems
(1)
parity of #1s in binary expansion
Source: Putnam 1984 B5
9/10/2021
For each nonnegative integer
k
k
k
, let
d
(
k
)
d(k)
d
(
k
)
denote the number of
1
1
1
's in the binary expansion of
k
k
k
. Let
m
m
m
be a positive integer. Express
∑
k
=
0
2
m
−
1
(
−
1
)
d
(
k
)
k
m
\sum_{k=0}^{2^m-1}(-1)^{d(k)}k^m
k
=
0
∑
2
m
−
1
(
−
1
)
d
(
k
)
k
m
in the form
(
−
1
)
m
a
f
(
m
)
g
(
m
)
!
(-1)^ma^{f(m)}g(m)!
(
−
1
)
m
a
f
(
m
)
g
(
m
)!
, where
a
a
a
is an integer and
f
f
f
and
g
g
g
are polynomials.
number theory