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
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 '20 at 0:38
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$

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$

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 '20 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 '20 at 2:08
  • 1
    $\begingroup$ @LieutenantZipp Actually, you can use binomial theorem to do this computation, like. $\endgroup$
    – MafPrivate
    Jan 22 '20 at 2:42

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.