Serbian Mathematical Olympiad

Solution:

Let us define the sequence $\left(c_{m, n}\right)\left(m, n \in \mathbb{N}_{0}\right)$ by the conditions
$$c_{m, 0}=0, \quad c_{m, 1}=1, \quad c_{m, n+1}=\frac{2 m}{n} c_{m, n}+c_{m, n-1} \quad \text{ for } n \geqslant 1$$
Then $a_{n}=c_{1010, n}$ and $b_{n}=c_{1009, n}$.
We see that e.g. $c_{1, n}=n, c_{2, n}=n^{2}$ and $c_{3, n}=\frac{2 n^{3}+n}{3}$. We claim that for every $m \in \mathbb{N}$ there exists a monic polynomial $P_{m}(x)$ such that
$$P_{m}(x+1)=\frac{2 m}{x} P_{m}(x)+P_{m}(x-1)$$
since obviously $P_{m}(0)=0$, by induction it will follow that $c_{m, n}=P_{m}(n) / P_{m}(1)$.

Lemma. Let us define the sequence of polynomials $P_{k}$ by the conditions $P_{0}(x)=0, P_{1}(x)=x$ and
$$P_{k+1}(x)=x P_{k}(x)+\frac{k(k-1)}{4} \cdot P_{k-1}(x)$$
Then the polynomials $P_{k}$ satisfy (1).
Moreover, the following holds $P_{k}(x+1)-2 P_{k}(x)+P_{k}(x-1)=\frac{k(k-1)}{x} \cdot P_{k-1}(x)$.

Proof. If we denote
$$\begin{aligned} & A_{k}(x)=P_{k+1}(x)-x P_{k}(x)-\frac{k(k-1)}{4} P_{k-1}(x) \equiv 0 \\ & B_{k}(x)=P_{k}(x+1)-2 P_{k}(x)+P_{k}(x-1)-\frac{k(k-1)}{x} P_{k-1}(x) \\ & C_{k}(x)=P_{k}(x+1)-P_{k}(x-1)-\frac{2 k}{x} P_{k}(x) \end{aligned}$$
and assume that $B_{i}(x) \equiv C_{i}(x) \equiv 0$ for all $i \leqslant k$, then
$$\begin{aligned} & B_{k+1}(x)-x B_{k}(x)-\frac{k(k-1)}{4} B_{k-1}(x)= \\ & C_{k}(x)+A_{k}(x+1)+A_{k}(x-1)-2 A_{k}(x)-\frac{k(k-1)}{x} A_{k-1}(x)=0 \end{aligned}$$
so $B_{k+1} \equiv 0$. On the other hand,
$$\begin{aligned} & C_{k+1}(x)-x C_{k}(x)-\frac{k(k-1)}{4} C_{k-1}(x)= \\ & B_{k}(x)+A_{k}(x+1)-A_{k}(x-1)-\frac{2(k+1)}{x} A_{k}(x)=0 \end{aligned}$$
so $C_{k+1} \equiv 0$ as well.

From (2) it follows that the polynomials $Q_{0}(x)=0$ and $Q_{k}(x)=\frac{2^{k-1}}{(k-1)!} P_{k}(x)$ satisfy the relation $Q_{k+1}(x)=\frac{2 x}{k} Q_{k}(x)+Q_{k-1}(x)$, so by induction we obtain $Q_{k}(x)=x c_{x, k}$ for all $x \in \mathbb{N}$. Hence $P_{k}(x)=\frac{(k-1)!}{2^{k-1}} \cdot x c_{x, k}$ and
$$\frac{c_{m, n}}{n}=\frac{1}{n} \cdot \frac{P_{m}(n)}{P_{m}(1)}=\frac{c_{n, m}}{c_{1, m}}=\frac{c_{n, m}}{m}$$
The claim of the problem is obtained for $m=1010$ and $n=1009$.

Second solution. For given $m \geqslant 0$ let us consider the generating function of the sequence $c_{m, n}$ given by the conditions $(*)$:
$$f_{m}(x)=\frac{1}{2 m}+\sum_{n=1}^{\infty} \frac{c_{m, n}}{n} x^{n}$$
From the recurrence relation $(*)$ it follows that the function $f_{m}$ satisfies the differential equation $\left(1-x^{2}\right) f_{m}^{\prime}(x)=2 m \cdot f_{m}(x)$. This equation is easily solved: if we write it as $\frac{f_{m}^{\prime}(x)}{f_{m}(x)}=\frac{2 m}{1-x^{2}}$, integration with respect to $x$ gives $\ln \left|f_{m}(x)\right|=\int \frac{2 m}{1-x^{2}} d x=$
$m \ln \frac{1+x}{1-x}+$ const, i.e. $f_{m}(x)=C \cdot\left(\frac{1+x}{1-x}\right)^{m}$. The condition $f_{m}(0)=\frac{1}{2 m}$ finally gives $C=1$, so
$$\begin{aligned} f_{m}(x) & =\frac{1}{2 m}\left(\frac{1+x}{1-x}\right)^{m}=\frac{1}{2 m}(1+x)^{m}(1-x)^{-m}= \\ & =\frac{1}{2 m} \sum_{i=0}^{m}\binom{m}{i} x^{i} \cdot \sum_{j=1}^{\infty}\binom{m-1+j}{m-1} x^{j} \end{aligned}$$
The coefficient of $x^{n}$ is
$$\frac{c_{m, n}}{n}=\frac{1}{2 m} \sum_{i=0}^{m}\binom{m}{i}\binom{m+n-1-i}{m-1}=\frac{1}{2} \sum_{i} \frac{(m+n-1-i)!}{i!(m-i)!(n-i)!}$$
This expression is symmetric in $m$ and $n$, so $\frac{c_{m, n}}{n}=\frac{c_{n, m}}{m}$.