1
$\begingroup$

Inspired by this question, I'd like to know how one would go about proving the below more general equation?

$$n \in \mathbb{N},\;a \in \mathbb{N},\;b \in \mathbb{N}$$ $$b^n+1 \notin a^{\mathbb{N}+1}$$

$$\left\lfloor n\frac{\log (b)}{\log (a)}\right\rfloor =\left\lfloor \frac{\log \left(b^n+1\right)}{\log (a)}\right\rfloor$$

Empirically the above appears, prima facie, to be the case. If it's not, apologies, I tried quite a few values of $a$, $b$ and $n$ and came up with the above assumptions.

$\endgroup$
  • $\begingroup$ Here's an idea: can you prove $\lfloor \log(b^n)\rfloor = \lfloor \log(b^n+1)\rfloor$? If yes, then you can use $\lfloor x/n\rfloor =\lfloor \lfloor x\rfloor /n\rfloor$ given certain conditions I don't remember exactly at the moment. It shouldn't be too difficult to prove it altogether. $\endgroup$ – Ian Mateus Feb 24 '14 at 1:44
  • $\begingroup$ Hmm... what about $(a,b,n)=(2,3,1)$? ;-) Maybe you wanted to ask for $b^n+1$ not being a power of $a$? $\endgroup$ – Peter Košinár Feb 24 '14 at 2:25
  • $\begingroup$ @PeterKošinár Oops, thanks for pointing that out! Fixed. $\endgroup$ – Max Feb 24 '14 at 2:41
2
$\begingroup$

Even more is actually true for positive integers $x$ and $a>1$, such that $(x+1)$ is not a power of $a$:

$$\left\lfloor\frac{\log x}{\log a}\right\rfloor = \left\lfloor\frac{\log (x+1)}{\log a}\right\rfloor$$

In order to see why this is so, let $m$ be the largest power of $a$ which doesn't exceed $x$. This means that we have $$a^m \leq x < a^{m+1}$$ and also $$m \leq \log_a x < m + 1$$ Since $\log_a x = \frac{\log x}{\log a}$, we have $$\left\lfloor\frac{\log x}{\log a}\right\rfloor = m$$

The right-hand side floor expression is clearly not smaller than $m$, so we only need to prove it cannot be larger either. Assume (for a proof by contradiction) that this was the case to get $$\frac{\log(x+1)}{\log a} \geq \left\lfloor \frac{\log(x+1)}{\log a}\right\rfloor \geq m+1$$ In the light of inequality $x<a^{m+1}$, the only possibility would be $x+1=a^{m+1}$. But that's precisely what we've forbidden by the not-a-power condition, thus completing our proof.

$\endgroup$
  • $\begingroup$ Brilliant, thank you very much @Peter! $\endgroup$ – Max Feb 24 '14 at 2:58

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.