a) $ \frac{1}{2}+\frac{1}{3}+...+\frac{1}{2^m} < 2(\frac{1}{2})+ 4(\frac{1}{4})+...+2^k(\frac{1}{2^k}) + ... + \frac{1}{2^m} = m-1+\frac{1}{2^m} < m$

panamath wrote: a) $ \frac{1}{2}+\frac{1}{3}+...+\frac{1}{2^m} < 2(\frac{1}{2})+ 4(\frac{1}{4})+...+2^k(\frac{1}{2^k}) + ... + \frac{1}{2^m} = m-1+\frac{1}{2^m} < m$ a) $\frac{1}{2}+\frac{1}{3}+...+\frac{1}{{{2}^{m}}}=\sum\limits_{k=1}^{m}{\left( \frac{1}{{{2}^{k-1}}+1}+\frac{1}{{{2}^{k-1}}+2}+...+\frac{1}{{{2}^{k}}} \right)}<$ $\sum\limits_{k=1}^{m}{\left( \underbrace{\frac{1}{{{2}^{k-1}}}+\frac{1}{{{2}^{k-1}}}+...+\frac{1}{{{2}^{k-1}}}}_{{{2}^{k-1}}} \right)}=\sum\limits_{k=1}^{m}{{{2}^{k-1}}\frac{1}{{{2}^{k-1}}}}=m$

ionbursuc wrote: a)Prove that $\frac{1}{2}+\frac{1}{3}+...+\frac{1}{{{2}^{m}}}<m$, for any $m\in {{\mathbb{N}}^{*}}$. That's the worst possible way of showing a pattern, what's coming after the first number that is equal to $\frac{1}{3} $ in that sum?

Of course, the hard part is b). The official solution raises the expression to power 4, and uses the estimate from a). I will give another solution, which uses two arguably well-known lemmas. I'll write the proof of both lemmas. Lemma 1 We have that $\prod_{p\ 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 $\dbinom{2k+1}{k+1}$. It is easy to see that it is divisible by $\displaystyle \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}\dbinom{2k+1}{k+1}\leq 4^{2k+1}$ (we used the induction hypothesis and the fact that $\dbinom{2k+1}{k+1}\leq 2^{2k}$, which is an easy exercise). The lemma is proved. 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)=\displaystyle\sum_{n\leq x} a_n$. Let $f$ be a function with continuous derivative. Then $\sum_{n\leq x} a_nf(n)=S(x)f(x)-\int_{x_0}^{x}S(t)f'(t)\mathrm{d} t$ Proof Let us note that $\sum_{n\leq x} a_nf(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))=S(x)f(x)-\sum_{n\leq x-1} S(n)\int_{n}^{n+1}f'(t)\mathrm{d}t$. As $S$ behaves like a step function constant on $[n,n+1)$, we get that $\sum_{n\leq x}a_nf(n)=S(x)f(x)-\int_{0}^xS(t)f'(t)\ \mathrm{d}t=S(x)f(x)-\int_{x_0}^xS(t)f'(t)\mathrm{d}t$, as $a_n=0$ for $n<x_0$. With these two lemmas we are ready to prove the problem. From the first lemma 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_nf(n)=S(x)f(x)-\int_{2}^{x}S(t)f'(t)\mathrm{d} t=\frac{S(x)}{x\log(x)}+\int_{2}^x\frac{S(t)(1+\log(t))}{t^2\log^2(t)}\mathrm{d}t\] 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)}\mathrm{d}t+\int_{2}^x\frac{\log(4)}{t\log(t)}\mathrm{d}t$. 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)$).

ionbursuc wrote: a)Prove that $\frac{1}{2}+\frac{1}{3}+...+\frac{1}{{{2}^{m}}}<m$, for any $m\in {{\mathbb{N}}^{*}}$. A trivial solution also includes induction. $ \frac{1}{2^m+1}+.... \frac{1}{2^{m+1}}<\frac{2^m}{2^m}<1 $ So the induction on $m$ holds

ionbursuc wrote: a)Prove that $\frac{1}{2}+\frac{1}{3}+...+\frac{1}{{{2}^{m}}}<m$, for any $m\in {{\mathbb{N}}^{*}}$. $\frac{1}{2}+\frac{1}{3}+...+\frac{1}{{{2}^{m}}}<\int_{1}^{2^{m}}\frac{dx}{x}=m\log(2)<m$.

Sorry to revive but could someone write the solution where you raise it to the 4th power (and maybe some motivation).

If we raise inequality to the 4th power we will get that on the left side we counted all numbers, which are the products of four primes $\left (\frac{1}{p_1p_2p_3p_4}\right )$, but $p_1p_2p_3p_4<(2^{100})^4=2^{400}$, so on the left side we have numbers in form $\frac{1}{n}$, where $n<2^{400}$, none of which is counted more than $4!=24$ times and hence their sum is no more than $24\cdot \sum_{i=2}^{2^{400}} \frac{1}{i} < 24\cdot 400=9600<10000=10^4$. Done.

By the same philosophy one can get <9 if raise the expression to 6th power: $6!\cdot \sum_{i=2}^{2^{600}} \frac{1}{i} < 720\cdot 600=432000<531441=9^6$.

Finally, there is one more way to improve bound: using that $\frac{1}{1}+\frac{1}{2}+...+\frac{1}{2^{m}}<m+1$, we prove that $\left(1+\frac{1}{p_1}+...+\frac{1}{p_n}\right)^7<7!\cdot \sum_{i=1}^{2^{700}} \frac{1}{i}<7!\cdot 701=3533040<3594149,993=(8,64)^7$ so $1+\frac{1}{p_1}+...+\frac{1}{p_n}<8.64$ and $\frac{1}{p_1}+...+\frac{1}{p_n}<7.64$

By bertrands postulate $p_n<2^n$ so the second is a consequence of the first one, as the sum of reciprocals of the first n primes is obviously less than the sum of the reciprocals of the first $2^n$ natural nos.

Is there any way to find a lower bound for the sum at b)?

WizardMath wrote: By bertrands postulate $p_n<2^n$ so the second is a consequence of the first one, as the sum of reciprocals of the first n primes is obviously less than the sum of the reciprocals of the first $2^n$ natural nos. Could someone elaborate on this?

Who can explain,clearly,the solution of #10? Pls...

ionbursuc wrote: panamath wrote: a) $ \frac{1}{2}+\frac{1}{3}+...+\frac{1}{2^m} < 2(\frac{1}{2})+ 4(\frac{1}{4})+...+2^k(\frac{1}{2^k}) + ... + \frac{1}{2^m} = m-1+\frac{1}{2^m} < m$ a) $\frac{1}{2}+\frac{1}{3}+...+\frac{1}{{{2}^{m}}}=\sum\limits_{k=1}^{m}{\left( \frac{1}{{{2}^{k-1}}+1}+\frac{1}{{{2}^{k-1}}+2}+...+\frac{1}{{{2}^{k}}} \right)}<$ $\sum\limits_{k=1}^{m}{\left( \underbrace{\frac{1}{{{2}^{k-1}}}+\frac{1}{{{2}^{k-1}}}+...+\frac{1}{{{2}^{k-1}}}}_{{{2}^{k-1}}} \right)}=\sum\limits_{k=1}^{m}{{{2}^{k-1}}\frac{1}{{{2}^{k-1}}}}=m$ I don't know how they understand the pattern it's unclear, the way it's written in the OP, it felt more like, $\sum_{k=2}^{2^{m}} \frac{1}{k}$

You misunderstood. I was referinng to #10.Why is not clearly? I was referinng to the first solution of Nikita Skybytskyi...