10
$\begingroup$

With minimal computation (i.e., without computing any of the actual quantities), show that $$\exists \; k \in \mathbb Z \; \text{such that} \; 2^{16} \lt 17^{k} \lt 2^{17}$$

My 17th birthday is coming up soon, and one of my friends at school sent me this question- she said that she had made it up for my birthday. I tried solving it by expanding $(2^{16}-1)+1=(2^{15}+2^{14}+2^{13}+...+2^{2}+2^{1}+2^{0})+1$ and $(2^{17}-1)+1=(2^{16}+2^{15}+2^{14}+...+2^{2}+2^{1}+2^{0})+1$, and seeing if "polynomializing" the powers of $2$ in this way helped find the power of $17$ somehow (I know from computation that the power is $17^{4}$).

I also noted that $17=2^{4}+1\gt2^{4}$, so $17^{4}\gt (2^{4})^{4}=2^{16}$, but I don't think I can perform the same sort of trick for the upper bound of $2^{17}$ without exactly the type of computation my friend wants me to avoid.

So my question is: can I actually solve my friend's problem without any sort of heavy calculation, or is she just messing with me? (Note: I would not be shocked if it were to be the latter, because that is exactly the sort of thing I have known her to do in the past.)

$\endgroup$
0

7 Answers 7

13
$\begingroup$

$$\begin{align}&\left[\frac{17}{16}\right]^{\large 4\cdot\color{#c00}4}\!\! = \left[1+\frac{1}{\color{#0a0}{16}}\right]^{\large\color{#0a0}{16}}\!\!<\, \color{#0a0}e\, < \color{c00}2^{\large\color{#c00} 4}\\[.2em] \overset{\large (\ {\phantom{|_|}} )^{\LARGE 1/\color{#c00}4}\!\!\!}\Longrightarrow\ \ \ &\left[\frac{17}{16}\right]^{\large 4}\! <\, \color{c00}2,\ \ {\rm so}\,\ \ \bbox[6px,border:1px solid #c00]{17^{\large 4} <\ 2\cdot 16^{\large 4} =\, 2^{\large17}}\end{align}\qquad$$

$\endgroup$
0
6
$\begingroup$

You suspect (correctly) that $2^{16} < 17^4 < 2^{17}$ since $17=2^4+1$

So try $$17^4=(16+1)^4 $$ $$= 16^4 + 4\times 16^3 +6\times 16^2+4\times 16^1 +1\times 16^0$$ $$< 16^4+4\times 16^3 +6\times 16^3+4\times 16^3 +1\times 16^3$$ $$=16^4+15 \times 16^3 $$ $$< 2 \times 16^4 = 2^{17}$$

and clearly $2^{16} = 16^4 < 17^4 $

$\endgroup$
5
$\begingroup$

Consider the fairly general case of showing, for some positive real numbers $a$, $b$, $c$ and $d$, with $a \neq 1$ and $d \gt c$, that

$$\exists \; k \in \mathbb Z \; \text{such that} \; a^{c} \lt b^{k} \lt a^{d} \tag{1}\label{eq1A}$$

Taking logs, say natural ones, of all of the parts gives

$$c\ln a \lt k \ln b \lt d \ln a \implies \frac{c\ln a}{\ln b} \lt k \lt \frac{d\ln a}{\ln b} \tag{2}\label{eq2A}$$

Thus, you just need to see if there's an integer value $k$ between the lower & upper limit values. In your case, you have $a = 2$, $b = 17$, $c = 16$ and $d = 17$. Plugging these values into \eqref{eq2A} gives

$$\begin{equation}\begin{aligned} & \frac{16\ln 2}{\ln 17} \lt k \lt \frac{17\ln 2}{\ln 17} \\ & 3.914\ldots \lt k \lt 4.159\ldots \end{aligned}\end{equation}\tag{3}\label{eq3A}$$

This shows that just $k = 4$ works, as you've found and the other answers have shown as well. However, this method shown here will work in any more general, difficult cases to fairly easily determine if there's any $k$ and, if so, which value(s) of $k$ will work.

$\endgroup$
1
  • $\begingroup$ or use $e=(1+{1\over n})^n$ as $n$ tends to infinity. $\endgroup$
    – user645636
    Jan 22, 2020 at 0:38
4
$\begingroup$

Similar Isaac YIU Math Studio's answer, we could instead use hexadecimal.

$2^{16}=16^4=10000_{16}$

$2^{17}=2\cdot2^{16}=20000_{16}$

As done in Henry's answer, we can binomially expand (or really just multiply out $11^4$) to see we then have:

$17^4=11_{16}^4=14641_{16}$

which is clearly between $10000_{16}$ and $20000_{16}$.

$\endgroup$
4
$\begingroup$

Note $17^4=(2^4+1)^4=2^{16}+4\cdot2^{12}+6\cdot2^8+4\cdot2^4+1$

$<2^{16}+2^{14}+2^{11}+2^6+1<2^{16}+2^{15}+2^{14}+\dots+2^2+2^1+2^0<2^{17}$.

$\endgroup$
4
$\begingroup$

Just another way, it is enough to compare $17^4 $ and $2\cdot16^4$. By Bernoulli’s inequality, $$\frac{17^4}{16^4} = \frac1{\left(1-\frac{1}{17}\right)^4} < \frac1{1-\frac4{17}}=\frac{17}{13}<2$$

$\endgroup$
0
0
$\begingroup$

You can use binary to find that:

$2^{16}=1000000000000000_{(2)} \\ 2^{17}=10000000000000000_{(2)} \\ 17^4=10001\times10001\times10001\times10001_{(2)}=10100011001000001_{(2)}$

Obvious that $2^{16}<17^4<2^{17}$.

$\endgroup$
3
  • 1
    $\begingroup$ I think you typed $10001$ too many times $\endgroup$ Jan 22, 2020 at 2:03
  • 2
    $\begingroup$ I like the usage of binary, but isn’t multiplying $10001_2$ out four times a bit tedious? And with significantly non-minimal computation? $\endgroup$ Jan 22, 2020 at 2:08
  • 1
    $\begingroup$ @LieutenantZipp Actually, you can use binomial theorem to do this computation, like. $\endgroup$
    – MafPrivate
    Jan 22, 2020 at 2:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .