1

Suppose $k \leq {c \times \log n}/{\log \log n}$ where $c$ is a constant.

Then we have the following reasoning:

$\log k^k = k \log k \leq (c \log n/\log \log n)(\log c + \log \log n)\leq (c+1)\log n$

The two steps here that seem like magic are:

$k \log k \leq (c \log n/\log \log n)(\log c + \log \log n)$

and

$(c \log n/\log \log n)\times(\log c + \log \log n)\leq (c+1)\log n$

Can anyone break them down please?

MPW
  • 43,638
John Smith
  • 33

1 Answers1

1

The underlying meaning is the following: The quantity $k=k(n)$ depends on $n$, and we have an estimate of the form $$k(n)\leq{c\log n\over\log\log n}\qquad(n\to\infty)\ .$$ Then for sufficiently large $n$ we can say that $$\log k^k\leq(c+1)\log n\ .$$ Proof. We may write $$\eqalign{\log k^k&=k\log k\leq{c\log n\over\log\log n}(\log c+\log\log n-\log\log\log n)\cr &\leq c\log n\left({\log c\over\log\log n}+1\right)\leq c\log n\left({1\over c}+1\right)\qquad(n>n_0)\ .\cr}$$

Christian Blatter
  • 226,825