| $\displaystyle \sum_{n \le x} 2^{\Omega(n)}$ |
$\displaystyle =\sum_{\substack{2^km \le x \\ m { is odd}}} 2^{\Omega(2^km)}$ |
| |
|
| |
$\displaystyle =\sum_{2^k \le x} 2^{\Omega(2^k)} \sum_{\substack{m \le \frac{x}{2^k} \\ m { is odd}}} 2^{\Omega(m)}$ since $2^{\Omega}$ is multiplicative |
| |
|
| |
$\displaystyle \ge \sum_{k \le \frac{\log x}{\log 2}} 2^k \sum_{\substack{m \le \frac{x}{2^k} \\ m { is odd}}} \tau(m)$ |
| |
|
| |
$\displaystyle \ge \sum_{k \le \frac{\log x}{\log 2}} 2^k \sum_{\substack{d \le \frac{x}{2^k} \\ d { is odd}}} \, \sum_{\substack{\ell \le \frac{x}{2^kd} \\ \ell { is odd}}} 1$ by the convolution method |
| |
|
| |
$\displaystyle \ge \sum_{k \le \frac{\log x}{\log 2}} 2^k \sum_{\substack{d \le \frac{x}{2^k} \\ d { is odd}}} \frac{x}{2^{k+2}d}$ |
| |
|
| |
$\displaystyle \ge \frac{x}{4} \sum_{k \le \frac{\log x}{\log 2}} \sum_{\substack{d \le \frac{x}{2^k} \\ d { is odd}}} \frac{1}{d}$ |
| |
|
| |
$\displaystyle \ge \frac{x}{4} \sum_{k \le \frac{\log x}{\log 2}} \left( \frac{1}{x} \sum_{\substack{d \le \frac{x}{2^k} \\ d { is odd}}} 1-\int_1^{\frac{x}{2^k}} \frac{-1}{t^2} \left( \sum_{\substack{d \le t \\ d { is odd}}} 1 \right) \, dt \right)$ by summation by parts |
| |
|
| |
$\displaystyle \ge \frac{x}{4} \sum_{k \le \frac{\log x}{\log 2}} \left( \frac{1}{x} \cdot \frac{x}{2^{k+2}}+\int_1^{\frac{x}{2^k}} \frac{1}{t^2} \cdot \frac{t}{2} \, dt \right)$ |
| |
|
| |
$\displaystyle \ge \frac{x}{4} \sum_{k \le \frac{\log x}{\log 2}} \left( \frac{1}{2^{k+2}}+\frac{1}{2}\int_1^{\frac{x}{2^k}} \frac{1}{t} \, dt \right)$ |
| |
|
| |
$\displaystyle \ge \frac{x}{4} \sum_{k \le \frac{\log x}{\log 2}} \left( \frac{1}{2^{k+2}}+\frac{1}{2}\log\left( \frac{x}{2^k} \right) \right)$ |
| |
|
| |
$\displaystyle \ge \frac{x}{16} \sum_{k \le \frac{\log x}{\log 2}} \left( \frac{1}{2^k}+\log x-k\log 2 \right)$ |
| |
|
| |
$\displaystyle \ge \frac{x}{16} \left( \frac{1}{2} \left( \frac{1-\left( \frac{1}{2} \right)^{\left\lfloor \frac{\log x}{\log 2} \right\rfloor +1}}{1-\frac{1}{2}} \right)+\log x \left\lfloor \frac{\log x}{\log 2} \right\rfloor -\log 2 \left( \frac{ \left\lfloor \frac{\log x}{\log 2} \right\rfloor^2+\left\lfloor \frac{\log x}{\log 2} \right\rfloor }{2} \right) \right)$ |
| |
|
| |
$\displaystyle \ge \frac{x}{16} \left\lfloor \frac{\log x}{\log 2} \right\rfloor \left( \log x-\frac{1}{2}\log 2 \left( \left\lfloor \frac{\log x}{\log 2} \right\rfloor +1 \right) \right)$ |
| |
|
| |
$\displaystyle \ge \frac{x}{16} \left\lfloor \frac{\log x}{\log 2} \right\rfloor \left( \log x-\frac{1}{2}\log 2 \left( \frac{\log x}{\log 2}+1 \right) \right)$ |
| |
|
| |
$\displaystyle \ge \frac{x}{16} \left\lfloor \frac{\log x}{\log 2} \right\rfloor \left( \log x-\frac{1}{2}\log x-\frac{1}{2}\log 2 \right)$ |
| |
|
| |
$\displaystyle \ge \frac{x}{32} \left\lfloor \frac{\log x}{\log 2} \right\rfloor \log \left( \frac{x}{2} \right)$ |
![[parent]](http://images.planetmath.org:8080/images/uparrow.png)
