Two Nice Berkeley Problems
by djmathman, Nov 22, 2018, 2:53 AM
Why is 2018 not released yet :'(
BMT 2017 Analysis #10. Define
. Evaluate ![\[\sum_{n=1}^{2017}\binom{2017}nH_n(-1)^n.\]](//latex.artofproblemsolving.com/7/a/0/7a05ebcb1788efda69fc3c133e5781aff0c7abf2.png)
BMT 2017 Discrete #10. Let
be the number of positive integers less than or equal to 
that are relatively prime to . Evaluate
![\[
\sum_{n=1}^{64}(-1)^n\phi(n)\left\lfloor\frac{64}n\right\rfloor.
\]](//latex.artofproblemsolving.com/0/5/b/05b75e17d200879778ebcf1755296fb013112b53.png)
BMT 2017 Analysis #10. Define
. Evaluate ![\[\sum_{n=1}^{2017}\binom{2017}nH_n(-1)^n.\]](http://latex.artofproblemsolving.com/7/a/0/7a05ebcb1788efda69fc3c133e5781aff0c7abf2.png)
for ease of typesetting. Rewrite the sum as![\begin{align*}
\sum_{n=1}^{m}\binom mnH_n(-1)^n &= \sum_{n=1}^m\left[\binom {m-1}{n-1} + \binom{m-1}n\right]H_n(-1)^n\\
&= \sum_{n=1}^m\binom{m-1}{n-1}H_n(-1)^n + \sum_{n=1}^{m-1}\binom{m-1}nH_n(-1)^n\\
&= -\sum_{n=0}^{m-1}\binom{m-1}n\left(H_n + \frac 1{n+1}\right)(-1)^n + \sum_{n=1}^{m-1}\binom{m-1}nH_n(-1)^n\\
&= \sum_{n=0}^{m-1}\binom{m-1}n\frac{(-1)^{n+1}}{n+1}.
\end{align*}](http://latex.artofproblemsolving.com/0/b/d/0bd99cced8b07406e1226a770c178008236e209b.png)
With this in mind, denote by 
the sum in the last line, and remark that
It is now readily apparent that 
;
.
and 
cases.BMT 2017 Discrete #10. Let
be the number of positive integers less than or equal to 
that are relatively prime to . Evaluate![\[
\sum_{n=1}^{64}(-1)^n\phi(n)\left\lfloor\frac{64}n\right\rfloor.
\]](http://latex.artofproblemsolving.com/0/5/b/05b75e17d200879778ebcf1755296fb013112b53.png)
,![\[
\sum_{d\mid n}\phi(d) = n.
\]](http://latex.artofproblemsolving.com/6/3/1/631a6d11bbb49f4a238114f47186e931ba8d0cd7.png)
is multiplicative.
be any arithmetic function. Then for all 
,![\[
\sum_{n=1}^N\sum_{d\mid n}f(d) = \sum_{n=1}^Nf(n)\left\lfloor\frac{N}{n}\right\rfloor.
\]](http://latex.artofproblemsolving.com/c/c/5/cc5ed6c6ed7c317e7db61cafd0bb13b7d18491d2.png)
,
appears in the summation for 
;
is precisely 
.
where in the last step we use Lemma 1.
,
denote the odd part of 
such that 
is a power of two. Then![\[
\sum_{d\mid n\text{ odd}}\phi(d) = \sum_{d\mid \operatorname{odd}(n)}\phi(d) = \operatorname{odd}(n),
\]](http://latex.artofproblemsolving.com/9/c/b/9cbe9748b6b7fcbcef9ae08d6cb67b961e71cbfd.png)
where again we use Lemma 1. We will be done upon computing the sum 
,
the odd function when restricted to the interval ![$[2^k + 1,2^{k+1}]$](http://latex.artofproblemsolving.com/6/b/a/6ba65e97b4aa530766f119213a340270e8aa7ad9.png)
is injective. Indeed, suppose 
for such 
and 
,![\[
\frac{n_1}{2^{\nu_2(n_1)}} = \frac{n_2}{2^{\nu_2(n_2)}}\quad\Rightarrow\quad n_1 = n_2\cdot 2^{\nu_2(n_1) - \nu_2(n_2)},
\]](http://latex.artofproblemsolving.com/5/e/c/5ec7a5c4ef1aeecfd872b6a329c13fe26aa343aa.png)
where 
is the 
-
,
.
for all such 
to 
inclusive, meaning that![\[
\sum_{n = 2^k+1}^{2^{k+1}}\operatorname{odd}(n) = \sum_{j=1}^{2^{k-1}}(2j-1) = 4^{k-1}.
\]](http://latex.artofproblemsolving.com/a/0/8/a08013a87de0aff9f96268fa408a88e4d92984b4.png)
Thus 
,![\[
\sum_{n=1}^{64}\left(n - 2\operatorname{odd}(n)\right) = \frac{64\cdot 65}2 - 2\cdot 1366 = \boxed{-652}.
\]](http://latex.artofproblemsolving.com/1/a/3/1a3d5f33b22748e06d05f2eb9b7dd391191e7628.png)
This post has been edited 3 times. Last edited by djmathman, Nov 22, 2018, 2:58 AM
April 2025
November 2024