# Show That a Power Of 17 Exists Between $2^{16},2^{17}$

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.)

\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

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

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.

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

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

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

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

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

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