Let 2 \leq k<\log n. Prove that \operatorname{KColoR}(\cdot, k) is an \left(2\left\lceil n^{1-1 /(k-1)}\right\rceil\right)-approximation algorithm. It may be helpful to recall Jensen’s Inequality: if f: \mathbb{R} \rightarrow \mathbb{R} is a concave function, then for any real numbers x_{1}, \ldots, x_{k},
\frac{f\left(x_{1}\right)+f\left(x_{2}\right)+\cdots+f\left(x_{k}\right)}{k} \geq f\left(\frac{x_{1}+x_{2}+\cdots+x_{k}}{k}\right)