Limit of average of $n^{1/k}$

Define $S_n$ as follows

$$ S_n =   \sum_{k=1}^{n} n^{\frac{1}{k}}$$

For eg 

$$S_{10} = 10 + 10^{1/2} + 10^{1/3} + \dots + 10^{1/10} \approx 25.4211$$

Find

$$ \displaystyle \lim_{n \to \infty} \dfrac{S_n}{n} $$ 

Scroll down for a solution.

We will solve this using the arithmetic mean geometric mean inequality!

For $k \ge 2$ let $$x_1 = x_2 = \dots = x_{k-2} = 1, x_{k-1} = x_k = \sqrt{n}$$

Applying AM GM to these we get 

$$\frac{k-2 + 2\sqrt{n}}{k} \ge n^{1/k} \ge 1$$

Thus 

$$1 - \frac{2}{k} + 2 \frac{\sqrt{n}}{k} \ge n^{1/k} \ge 1$$

Now $\sum_{k=2}^{n} \frac{1}{k} = \log n + O(1)$

Thus

$$ n-1 - 2(\log n + O(1)) + 2\sqrt{n}(\log n + O(1)) \ge \sum_{k=2}^n n^{1/k} \ge n-1$$ 

And so 

$$ 2n-1 - 2(\log n + O(1)) + 2\sqrt{n}(\log n + O(1)) \ge \sum_{k=1}^n n^{1/k} \ge 2n-1$$  

Thus 

$$ 2 + O\left(\frac{\log n}{\sqrt{n}}\right) \ge \frac{S_n}{n} \ge 2 + O\left(\frac{1}{n}\right)$$

Thus $$ \frac{S_n}{n} \to 2$$

A cute problem from Turkish AYT exam

 $P(x)$ is a $4^{th}$ degree polynomial with real coefficients that satisfies

$$P(x) \ge x \quad \forall x \in R$$

$$P(1) = 1, P(2) = 4, P(3) = 3$$

Find the value of $P(4)$.

Scroll down for a solution.

Let $H(x) = P(x) - x$ and so $H(x) \ge 0 \forall x \in R$. Since $H(1) = H(3) = 0$, $H(x)$ has at least two distinct roots.

Now if there was a root of $H$ different from $1$ or $3$, then we can show that $H(c) < 0 $ for some $c \in R$. If the multiplicity of $1$ of $3$ was odd, then we can again show that $H(c) < 0$ for some $c$.

Thus we must have that

$$H(x) = A(x-1)^2(x-3)^2, A > 0$$

Since $H(2) = P(2) - 2 = 2$, we get  $A = 2$.

This gives $P(4) = H(4) + 4 = 2.3^2.1^2 + 4 = 22$.