Explain the thought process to a given solution for $ \frac{1+n}{2^n} =\frac{3}{16} $ please

Question

Part of the given solution to a question leaves me baffled:

"...solve the equation $$ \frac{1+n}{2^n} =\frac{3}{16} $$ We can check (simply by plugging in values of $n$) that if $ \leq n \leq 5$, then $n=5$ is the only solution. Now we show that $n\geq 6$ cannot be a solution to the equation. Observe that $n\geq 6$ implies $n<2^{n-3}$ ......"

I cannot see how $n\geq 6$ implies $n<2^{n-3}$. Can somebody please explain?

Answer 1

The answers have given you proofs of the fact you asked about, but they haven't given you much insight into how anyone thought of this solution. You did not ask that in your post, but your title sort of asks it, so I thought it would be helpful to explain, nonetheless.

The point is that as $n$ gets big, $1+n$ will be much smaller than $2^n$. So much smaller, in fact, that their ratio will be much smaller than $3/16$, so that for all $n$ beyond a certain point, there cannot be any solutions to your equation. Indeed, if you know any calculus, you know the ratio of a polynomial to an exponential function tends to zero at infinity. This is the key idea of the solution, even though it is not explicitly stated: we can make this ratio $\frac{1+n}{2^n}$ as small as we want -- therefore, smaller than $3/16$ -- if we choose $n$ big enough.

To prove this, it would help to have $n<2^{n-a}$ for all large $n$, for some positive $a$. Then we could argue

$$\frac{1+n}{2^n}=\frac{1}{2^n}+\frac{n}{2^n}<\frac{1}{2^n}+\frac{2^{n-a}}{2^n}=\frac{1}{2^n}+\frac{1}{2^a}$$

By trial and error we can find an $a$ that works for sufficiently large $n$ so that this last expression must be less than $3/16$.

But after checking the first few positive integer values of $n$ in the original equation, we know $5$ is a solution. So we might hope that for all $n\geq6$ we can find a large enough $a$ to make the proof work. And indeed, if you try out various values of $a$ you'll see the first that works is 3: 6 is indeed less than $2^{6-3}$, and 7 is less than $2^{7-3}$, etc. To rigorously justify the "etc." you can use an argument from one of the other answers.

Note, by the way, that if we want to find positive integer solutions to your equation rather than rule them out as we were doing above, we don't have to do guess and check totally blindly. We only need to check values of $n$ that are equivalent to $2\mod 3$ and greater than or equal to 4. That's because your equation implies that $1+n$ must be a multiple of 3 and $2^n$ must be a multiple of 16. The first statement means $n$ must have remainder 2 when we divide it by 3, and the second statement means $n\geq4$.

So in fact, we only need to check $n=5$ and $n=8$ and $n=11$, etc. But our earlier argument shows we can stop checking after $n=5$.

Answer 2

You can remark that $2^{n-3}-n > 0$ for $n=6$. For $n \geqslant 6$ remark that $$2^{(n+1)-3}-(n+1) > 2^{n-3}-n.$$

Answer 3

You can do it by induction. $6 \lt 2^{6-3}$ If $k \lt 2^{k-3}$, then $k+1 \lt 2k \lt 2(2^{k-3})=2^{(k+1)-3}$

Answer 4

A long-ish proof, relying on analysis instead of induction. The trick can be useful in other situations: to prove a statement about integers, it is sometimes simpler (more systematic) to prove it for the reals, as then one can use all the nice available tools from real analysis.

Consider the function $f\colon [0,\infty)\to \mathbb{R}$ defined by $f(x) = 2^{x-3} - x = \frac{1}{8}\left( e^{x \ln 2} - 8x \right)$.

You can study $f$, which is in particular differentiable on its domain, and $$ f^\prime(x) = \frac{1}{8}\left( \ln 2 \cdot e^{x\ln 2} - 8 \right) = \frac{1}{8}\left( \ln 2 \cdot 2^x - 8 \right). $$ Since $2^4 \ln 2 = 16 \ln 2 > 8$ (as $\ln 2 \simeq 0.69 > \frac{1}{2}$), we have $f^\prime(x) > 0$ for all $x \geq 4$. So $f$ is strictly increasing on $[, \infty)$.

Now, $f(6) = 2^{3}-8 = 0$; so by monotonicity we have $f(x) \geq 0$ for all $x\geq 6$, which is equivalent to $2^{x-3} \geq x$ for all $x\geq 6$.

In particular, this also applies to integer values $n\geq 6$.