# Any interval $[s,2s]$ contains power of $2$

I've been trying to find the solution for this problem for a long time... but I can't seem to do it. I'm not asking for the full solution, maybe just a hint or where to start off from. I never know where to begin with these type of problems.

Let $s \geq 1$ be a positive integer, prove that in the interval $[s,2s]$ contains a power of 2.

• I didn't know how to write a less than or equal sign

If $s$ is a power of $2$, then there is nothing to prove. If $s$ is not a power of $2$ then it must lie between two consecutive powers of $2$, i.e., there is an integer $r$ for which $2^r < s < 2^{r+1}$. This yields $2^{r+1} < 2s$. Hence $s < 2^{r+1} < 2s$, which gives the required result.

Hope it helps.

• It might be serve OP better if you look at already posted solutions to avoid repetition of the same idea. – Anurag A Jan 8 '17 at 8:46
• What if s does not lie between two consecutive powers of 2? – Math4life Jan 8 '17 at 9:11
• @Math4life That's never possible. $s$ has only two possibilities: to be a power of two or not to be a power of two. – Rohan Jan 8 '17 at 9:13
• @Math4life Let $S$ be the set of all $r$ such that $s<2^r$. We have $s<2^s$, and so $S$ is non-empty. Therefore, $S$ has a least element $r$. We then have $2^{r-1}\le s<2^r$ by minimality of $r$. – John Gowers Jan 14 '17 at 15:53

Hint: Let $k \geq 0$ be an integer such that $2^k$ is the highest power of $2$ which is less than or equal to $s$. If $s=2^k$, then we are done, otherwise $2^k <s$, so what can be said about $2^{k+1}$?

If you want greater than or less than, put %\geq% %\leq% but instead of % use $. As to your question, I assume you mean that for all$s\in\mathbb{N}$, there exist an$n\in\mathbb{N}$such that$s<2^n\leq2s$. We proceed by strong induction: Base Case: This is true for$1$since$1<2^1\leq2$. Strong Inductive Step: We assume that for all naturals$1,2,...s$that the proposition is true. In order to prove this, me must show there exists$n\in\mathbb{N}$such that$s+1<2^n\leq2(s+1)$. Now, if$s+1$is even, then there exists$w\in\{1,2,...s\}$and$m\in\mathbb{N}$such that$2w=s+1$and $$w<2^m\leq2w.$$ Multiplying be$2$, we have $$2w<2*2^m\leq2*2w$$ $$s+1<2^{m+1}\leq2(s+1)$$ and the proposition is true. Now, consider the case where$s+1$is odd. Note that $$s<2^n\leq2s$$ is true (from our assumption). Also, since$2^n$is even and$s$is even,$2^n>s$implies$2^n>s+1$. Also, using$2s+2>2s\geq2^n\$, we see $$s+1<2^n<2s+2$$ $$s+1<2^n\leq2(s+1)$$ which is what we were originally trying to show.