Solution from contest: As usual let $p_\infty$ denote a large enough prime and $L=lcm(n+1,n+2,...,n+k)$. Claim: For a polinomial $P$ (with $deg\neq0$) there $\exists$ $N$ such that $P$ is unbounded and stricly increasing or strictly decreasing in $[N,+\infty)$ Proof: We will proof this by induction on $n=deg(P)$ Base: $n=1$: $f$ is linear $\Rightarrow$ $f$ is strictly increasing or decreasing and unbounded Induction step: $P(x+1)-P(x)=(a(x+1)^{n+1}+Q(x+1))-(ax^{n+1}+Q(x))=$$a((n+1)x^n+...+1)+Q(x+1)-Q(x)$ which is $=$ to a polynomial of $deg \leq n$ which from the induction hyphotesis we know is unbounded $\Rightarrow$ for a large enough $n$ it will be $<0$ or $>0$ $\Rightarrow$ $P(x+1)-P(x)>0$ or $<0$ with which the induction is complete. (Here the fact that it's strictly decreasing/increasing implies that it's unbounded as we're in $\mathbb{Q}$ and $x \in \mathbb{N}$) This means that our polinomial should be strictly increasing unbounded as it cannot be decreasing as $L>0$ So we have $f(p_\infty-1)<f(p_\infty)$. Let $k\geq3$: We can choose a prime $q$ such that $q<k$ and $q\nmid k$ (We can do this because there exists a prime between $y$ and $2y$) From Dirichlet's theorem we can take $p_\infty\equiv-k (mod q) \Rightarrow $ Let $S=lcm(p_\infty+1,p_\infty+2,..,p_\infty+k-1)$ $f(p_\infty-1)=lcm(p_\infty,p_\infty+1,...,p_\infty+k-1)=lcm(p_\infty,S)=\frac{Sp_\infty}{gcd(p_\infty,S)}=Sp_\infty$ We have that $q\mid(p_\infty+k)$ and $q\mid S \Rightarrow$ $gcd(p_\infty+k,S)\geq q \Rightarrow f(p_\infty)=lcm(p_\infty+1,p_\infty+2,...,p_\infty+k)=lcm(p_\infty+k,S)=\frac{(p_\infty+k)S}{gcd(p_\infty+k,S)}\leq\frac{(p_\infty+k)S}{q}$ But we know that $f(p_\infty-1)<f(p_\infty) \Rightarrow Sp_\infty<\frac{(p_\infty+k)S}{q} \Rightarrow p_\infty(q-1)<k$ which is a contradiction for a large enough $p$. We are left with the case $k\leq2$: Here we get the two solutions $\boxed{k=1, f(n)=n+1}$ and $\boxed{k=2, f(n)=n^2+3n+2}$

Great solution @GeorgeRP! You seem to even solve the problem for any eventually increasing function. This problem, proposed by Aleksandar Ivanov, is definitely my favourite in the competition.

Very standard problem, I guess? I will first prove a very crucial claim: Claim: For any natural numbers $x, k$, we have $$ k\left(\begin{array}{c} x+k \\ k \end{array}\right) \mid \operatorname{lcm}(x+1, \ldots, x+k) $$ Proof: First, notice that: $$ \frac{k !}{(x+1) \cdots(x+k)}=\sum_{i=1}^{k} \frac{(-1)^{i}\left(\begin{array}{c} k \\ i \end{array}\right)}{x+i} $$ because, if we consider the polynomial $$ f(x)=\sum_{i=1}^{k}(-1)^{i}(x+1) \cdots(x+i-1)(x+i+1) \cdots(x+k)\left(\begin{array}{c} k \\ i \end{array}\right)-k ! $$ this polynomial has roots $-1, \ldots,-k$, but it also has degree at most $k-1$, so this is the zero polynomial. Now, getting back to the problem, note that we can actually re-write this identity as: $$ \frac{1}{\left(\begin{array}{c} x+k \\ k \end{array}\right)}=\sum_{i=1}^{k} \frac{(-1)^{i}\left(\begin{array}{c} k \\ i \end{array}\right)}{x+i} $$ But now note that we have $\left(\begin{array}{l}k \\ i\end{array}\right)=\frac{k}{i} \cdot\left(\begin{array}{c}k-1 \\ i-1\end{array}\right)$, so we get that: $$ \frac{1}{k\left(\begin{array}{c} x+k \\ k \end{array}\right)}=\sum_{i=1}^{k} \frac{(-1)^{i}\left(\begin{array}{c} k-1 \\ i-1 \end{array}\right)}{i(x+i)}=\frac{T}{\operatorname{lcm}(x+1, \ldots, x+k)} $$ because, for each $1\le i\le k$, we have $i\mid\operatorname{lcm}(x+1,\ldots,x+k)$, where $T$ is some integer, this readily proves the claim. Back to the problem, note that if $P(x)$ is the polynomial aforementioned in the problem, we would have that: $$ k\left(\begin{array}{c} x+k \\ k \end{array}\right) \mid P(x) $$ so, we would have $$ \frac{(x+1) \cdots(x+k)}{(k-1) !}|P(x)|(x+1) \cdots(x+k) $$ This proves that, $P(x)$ takes the form $$ \frac{(x+1) \cdots(x+k)}{c} $$ where $c \mid(k-1)$ ! is a constant. Now, if $k\geq 3$, then, \[\frac{\text{lcm}(2,3,\ldots,k+1)}{\text{lcm}(3,4,\ldots,k+2)}=\frac{2}{k+2}\]but note that if $k+2$ is not a prime, the left hand side is $1$ and if it is, then it i $\frac{1}{k+2}$, therefore $k\le 2$, and these obviously work, so the answers are $k=1,2$ only. Remarks: Another way to solve this problem, which is much easier, is to prove that $p$-adic valuation of \[\frac{(x+1)\ldots(x+k)}{\operatorname{lcm}(x+1,\ldots,x+k)}\]is bounded for all $x\in\mathbb{N}$ for each prime $p$ and by doing this we can completely avoid my claim, but I think this solution is quite instructive which is why I decided to post it.