1
$\begingroup$

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
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It might be serve OP better if you look at already posted solutions to avoid repetition of the same idea. $\endgroup$ – Anurag A Jan 8 '17 at 8:46
  • $\begingroup$ What if s does not lie between two consecutive powers of 2? $\endgroup$ – Math4life Jan 8 '17 at 9:11
  • $\begingroup$ @Math4life That's never possible. $s$ has only two possibilities: to be a power of two or not to be a power of two. $\endgroup$ – Rohan Jan 8 '17 at 9:13
  • $\begingroup$ @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$. $\endgroup$ – John Gowers Jan 14 '17 at 15:53
1
$\begingroup$

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}$?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.