Let $(a_n)^{+\infty}_{n=1}$ be a sequence defined recursively as follows: $a_1=1$ and $$a_{n+1}=1 + \sum\limits_{k=1}^{n}ka_k$$For every $n > 1$, prove that $\sqrt[n]{a_n} < \frac {n+1}{2}$.
Problem
Source: Macedonian National Olympiad 2021 P1
Tags: Sequence, recursive, Inequality, factorial, AM-GM, inequalities
19.05.2021 23:19
$a_{n+1}=1+\sum_{k=1}^\infty ka_k$ is nonsensical; did you mean $a_{n+1}=1+\sum_{k=1}^n ka_k$?
19.05.2021 23:22
jasperE3 wrote: $a_{n+1}=1+\sum_{k=1}^\infty ka_k$ is nonsensical; did you mean $a_{n+1}=1+\sum_{k=1}^n ka_k$? yes, fixed it.
20.05.2021 05:34
Cute problem. Since $a_n = 1+\sum_{1\le k\le n-1}ka_k$, we find that $a_{n+1}-a_n=na_n$, that is $a_{n+1}/a_n = (n+1)$. Iterating this, we find that $a_n = n!$ for $n\ge 1$. With this in hand, observe now that taking logarithm of both sides, \[ \sqrt[n]{a_n}<\frac{n+1}{2} \Leftrightarrow \frac1n\sum_{1\le k\le n}\ln(k) \le \ln\left(\frac{n+1}{2}\right). \]Clearly, $k\mapsto \ln(k)$ has second derivative $-k^{-2}$, which is negative. Thus $\ln(\cdot)$ is concave. Applying Jensen's inequality \[ \frac1n\sum_{1\le k\le n}\ln(k)\le \ln\left(\frac1n\sum_{1\le k\le n}k\right) = \ln\left(\frac{n+1}{2}\right), \]as requsted.
20.05.2021 12:25
My proposal
21.05.2021 02:11
We can also finish the problem after finding $a_n = n!$ by using AM-GM like this: $$\frac{n+1}{2} = \frac{1}{n} \cdot \frac{n(n+1)}{2} = \frac{1}{n} \cdot (1+2+\dots+n) \geq \sqrt[n]{1\cdot 2 \cdot \dots \cdot n} = \sqrt[n]{n!} = \sqrt[n]{a_{n}}$$
21.05.2021 02:17
Other finishes in this thread. My solution: Note that $a_n=na_{n-1}$. Coupled with $a_1=1$, this means that just $a_n=n!$ by induction. Then $\frac{n+1}2=\frac{1+2+\ldots+n}n\ge\sqrt[n]{n!}$ by AM-GM. $\square$
21.05.2021 02:54
this is kinda off topic but my name is 'clair' spell c-l-a-i-r not c-l-a-i-r-e which is kind of rare
21.05.2021 06:17
Thank you for that, clair.