# Prove: if $n = \frac{k^k-1}{k-1}$ then $k=\Omega\left(\frac{\log{n}}{\log{\log{n}}}\right)$

I have to prove that for integers $n$ and $k$, $k\geq2$, and $$n = \frac{k^k-1}{k-1}$$ follows, that $$k=\Omega\left(\frac{\log{n}}{\log{\log{n}}}\right).$$

So it would be sufficient to show, that for some constant $c>0$ following inequality holds: $$k \geq c\cdot\frac{\log{n}}{\log{\log{n}}}$$

In detail it would look like: $$\frac{\log{n}}{\log{\log{n}}} = \frac{\log{\left(k^k-1\right)}-\log{\left(k-1\right)}}{\log{\left(\log{\left(k^k-1\right)}-\log{\left(k-1\right)}\right)}} \leq \ldots \leq c\cdot k$$

I'm trying to find an upper bound for the numerator and an lower bound for the denominator of the above fraction, but I haven't worked it out yet. The estimation for the nominator looks e.q. like this: $$\log{\left(k^k-1\right)}-\log{\left(k-1\right)} \leq \log{k^k} - \log{\left(k-1\right)} = k\cdot\log{k} - \log{\left(k-1\right)} \leq k^2 - \left(1-\frac{1}{k-1}\right) = k^2 - \frac{k-2}{k-1}$$

It would be nice if somebody could help me with this assignment!

Geometric series:

$$\frac{k^k-1}{k-1}=1+k+k^2+k^3+\dots+k^{k-1}<k^{k-1}+k^{k-1}+k^{k-1}+\dots+k^{k-1}=k^k$$

Thus,

$$n<k^k$$

$$\log n<\log k^k=k\log k$$

$$k>\frac{\log n}{\log k}$$

if $k\ge3$,

$$1+k+k^2+\dots+k^{k-1}>1+2+2^2+\dots+2^{k-1}>2+2+2+\dots+2=2^k$$

$$n>2^k$$

$$k<\log_2n$$

One can adjust this to see that for any base, the following is eventually true for large enough $k$.

$$k<\log n$$

Combining these, we have

$$k>\frac{\log n}{\log k}>\frac{\log n}{\log\log n}$$

• @IraRe No problem, your welcome! Commented Dec 18, 2016 at 23:40
• Hello @SimpleArt, unfortunately I found a mistake in your solution I don't know how to solve it. The step $\sum_{i=0}^{k-1}{2^i} = 2^k$ isn't correct. As a result the inequality $k<\log{n}$ isn't true. Do you have any other ideas how to solve this? Commented Dec 22, 2016 at 7:00
• You've appeared to miss the fact that I used an inequality:$$\sum_{i=0}^{k-1}2^i<\sum_{i=0}^{k-1}2=2^k$$ @IraRe Commented Dec 22, 2016 at 13:20
• Not the inequality, but the equation is false. It holds $\sum_{i=0}^{k-1}{2} = k\cdot 2 \neq 2^k$ Commented Dec 26, 2016 at 15:32
• @IraRe Oh no, that's quite silly of me, I'll see what I can do to fix it up. Commented Dec 26, 2016 at 15:35