Problem 1729

### Part (a)
We need to prove that for any $m \in \mathbb{N}^*$:
$$\frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{2^m} < m$$

1. Base Case:
For $m = 1$:
$$\frac{1}{2} < 1$$
This is true.

2. Inductive Step:
Assume the statement is true for some $m = k$, i.e.,
$$\frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{2^k} < k$$
We need to show it holds for $m = k + 1$:
$$\frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{2^k} + \frac{1}{2^{k+1}} < k + 1$$
By the inductive hypothesis:
$$\frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{2^k} < k$$
Adding $\frac{1}{2^{k+1}}$ to both sides:
$$\frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{2^k} + \frac{1}{2^{k+1}} < k + \frac{1}{2^{k+1}}$$
Since $\frac{1}{2^{k+1}} < 1$:
$$k + \frac{1}{2^{k+1}} < k + 1$$
Therefore:
$$\frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{2^k} + \frac{1}{2^{k+1}} < k + 1$$
By induction, the statement is true for all $m \in \mathbb{N}^*$.

$\blacksquare$

### Part (b)
We need to prove that for the prime numbers $p_1, p_2, \ldots, p_n$ less than $2^{100}$:
$$\frac{1}{p_1} + \frac{1}{p_2} + \cdots + \frac{1}{p_n} < 10$$

1. Lemma 1:
We have that:
$$\prod_{p \text{ prime} \leq x} p \leq 4^x$$
for any positive integer $x$.

Proof:
We use induction. The base cases are trivial. Passing from an odd integer to an even one is very easy (as LHS remains the same while the RHS increases). So we only show how to pass from an even integer to an odd one (i.e., prove the inequality for $x = 2k + 1$). We will use the binomial coefficient $\binom{2k+1}{k+1}$. It is easy to see that it is divisible by $\prod_{k+1 < p \leq 2k+1} p$ (the product is taken over primes). Therefore:
$$\prod_{p \leq 2k+1} p \leq \left( \prod_{p \leq k+1} p \right) \left( \prod_{k+1 < p \leq 2k+1} p \right) \leq 4^{k+1} \binom{2k+1}{k+1} \leq 4^{2k+1}$$
(we used the induction hypothesis and the fact that $\binom{2k+1}{k+1} \leq 2^{2k}$, which is an easy exercise). The lemma is proved.

2. Lemma 2 (Partial Summation):
Let $a_n$ ($n \in \mathbb{N}$) be a sequence, so that $a_n = 0$ for $n < x_0$, and $S(x) = \sum_{n \leq x} a_n$. Let $f$ be a function with continuous derivative. Then:
$$\sum_{n \leq x} a_n f(n) = S(x) f(x) - \int_{x_0}^{x} S(t) f'(t) \, dt$$

Proof:
Let us note that:
$$\sum_{n \leq x} a_n f(n) = \sum_{n \leq x} (S(n) - S(n-1)) f(n) = S(x) f(x) - \sum_{n \leq x} S(n-1) (f(n) - f(n-1))$$
As $S$ behaves like a step function constant on $[n, n+1)$, we get that:
$$\sum_{n \leq x} a_n f(n) = S(x) f(x) - \int_{0}^x S(t) f'(t) \, dt = S(x) f(x) - \int_{x_0}^x S(t) f'(t) \, dt$$
as $a_n = 0$ for $n < x_0$.

3. Applying Lemmas:
From Lemma 1, we have (by taking logarithms) that:
$$\sum_{p \leq n} \log(p) \leq n \log(4)$$
for any integer $n$, so the relation actually holds even if $n$ is any positive real number. We use Lemma 2 with $a_n = \log(n)$ if $n$ is prime and $a_n = 0$ otherwise. We take $f(x) = \frac{1}{x \log(x)}$. We can take in the lemma $x_0 = 2$. We have that:
$$\sum_{p \leq x} \frac{1}{p} = \sum_{n \leq x} a_n f(n) = S(x) f(x) - \int_{2}^{x} S(t) f'(t) \, dt = \frac{S(x)}{x \log(x)} + \int_{2}^x \frac{S(t)(1 + \log(t))}{t^2 \log^2(t)} \, dt$$
Using that $S(x) \leq x \log(4)$, we get that:
$$\sum_{p \leq x} \frac{1}{p} \leq \frac{\log(4)}{\log(x)} + \int_{2}^x \frac{\log(4)}{t \log^2(t)} \, dt + \int_{2}^x \frac{\log(4)}{t \log(t)} \, dt$$
The antiderivative of the function in the first integral is $\frac{1}{\log(t)}$, so the first integral is at most $\frac{\log(4)}{\log(2)} = 2$, and the antiderivative of the function in the second integral is $\log(\log(x))$. We therefore have that:
$$\sum_{p \leq x} \frac{1}{p} \leq \frac{\log(4)}{\log(x)} + 2 + \log(4) (\log(\log(x)) - \log(\log(2)))$$
For $x = 2^{100}$, we have that:
$$\sum_{p \leq 2^{100}} \frac{1}{p} \leq \frac{1}{50} + 2 + \log(4) \log(100)$$
and the last expression is less than $8.405$ (in an olympiad one might use that $e$ is greater than $2.7$ and use this to estimate $\log(2)$ and $\log(10)$).

$\blacksquare$