1
$\begingroup$

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!

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ @IraRe No problem, your welcome! $\endgroup$ Commented Dec 18, 2016 at 23:40
  • $\begingroup$ 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? $\endgroup$
    – Ira Re
    Commented Dec 22, 2016 at 7:00
  • $\begingroup$ 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 $\endgroup$ Commented Dec 22, 2016 at 13:20
  • $\begingroup$ Not the inequality, but the equation is false. It holds $\sum_{i=0}^{k-1}{2} = k\cdot 2 \neq 2^k$ $\endgroup$
    – Ira Re
    Commented Dec 26, 2016 at 15:32
  • $\begingroup$ @IraRe Oh no, that's quite silly of me, I'll see what I can do to fix it up. $\endgroup$ Commented Dec 26, 2016 at 15:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .