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

Question

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!

Answer 1

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