IMC 2019 · Day 1 · P4

Hint: Determine the generating function $\sum a_n x^n$.

Take the generating function of this sequence $$f(x) = \sum_{n=0}^{\infty} a_n x^n.$$ It is easy to see that the sequence is increasing and $$\frac{a_{n+1}}{a_n} = \frac{(6n + 3) a_n - (n - 1) a_{n-1}}{(n + 2) a_n} < \frac{6n + 3}{n + 2} \quad \Rightarrow \quad \limsup_{n \to \infty} \frac{a_{n+1}}{a_n} \le 6.$$ So the generating function converges in some neighbourhood of 0. Then, we have $$f(x) = 1 + 2x + \sum_{n=2}^{\infty} a_n x^n = 1 + 2x + \sum_{n=0}^{\infty} a_{n+2} x^{n+2} = 1 + 2x + \sum_{n=0}^{\infty} \frac{6n + 9}{n + 3} a_{n+1} x^{n+2} - \sum_{n=0}^{\infty} \frac{n}{n + 3} a_n x^{n+2}.$$ Let $f_1(x) = \sum\limits_{n=0}^{\infty} \frac{6n + 9}{n + 3} a_{n+1} x^{n+2}$ and $f_2(x) = \sum\limits_{n=0}^{\infty} \frac{n}{n + 3} a_n x^{n+2}$. Then $$(x f_1(x))' = \sum_{n=0}^{\infty} (6n + 9) a_{n+1} x^{n+2} = 6 x^2 \sum_{n=0}^{\infty} (n + 1) a_{n+1} x^n + 3x \sum_{n=0}^{\infty} a_{n+1} x^{n+1} = 6 x^2 f'(x) + 3x (f(x) - 1)$$ and $$(x f_2(x))' = \sum_{n=0}^{\infty} n a_n x^{n+2} = x^2 \sum_{n=0}^{\infty} (n + 1) a_n x^n - x^2 \sum_{n=0}^{\infty} a_n x^n = x^2 (x f(x))' - x^2 f(x) = x^3 f'(x).$$ Using this relations, we arrive at the following differential equation for $f$: $$(x f(x))' = 1 + 4x + (x f_1(x))' - (x f_2(x))' = 1 + x + (6 x^2 - x^3) f'(x) + 3x f(x)$$ or, equivalently, $$(x^3 - 6 x^2 + x) f'(x) + (1 - 3x) f(x) - 1 - x = 0.$$ So, we need solve this differential equation in some sufficiently smaller neighbourhood of 0. We know that $f(0) = 1$ and we need a neighbourhood of 0 such that $x^2 - 6x + 1 > 0$. Then $$f'(x) + \frac{1 - 3x}{x (x^2 - 6x + 1)} f(x) = \frac{1 + x}{x (x^2 - 6x + 1)}$$ for $x \ne 0$. So the integral multiplier is $\mu(x) = \dfrac{x}{\sqrt{x^2 - 6x + 1}}$ and $$(f(x) \mu(x))' = \frac{x + x^2}{(x^2 - 6x + 1)^{\frac32}},$$ so $$f(x) = \left( \frac{1 - x}{2 \sqrt{x^2 - 6x + 1}} - \frac12 \right) \frac{\sqrt{x^2 - 6x + 1}}{x} = \frac{1 - x - \sqrt{x^2 - 6x + 1}}{2x}.$$ We found the generating function of $(a_n)$ in some neighbourhood of 0, which $x^2 - 6x + 1 > 0$. So our series uniformly converges to $f(x) = \dfrac{1 - x - \sqrt{x^2 - 6x + 1}}{2x}$ in $|x| < 3 - 2\sqrt{2}$.

Instead of computing the coefficients of the Taylor series of $f(x)$ directly, we will find another recurrence relation for $(a_n)$. It is easy to see that $f(x)$ satisfies the quadratic equation $x t^2 - (1 - x) t + 1 = 0$. So $$x f(x)^2 - (1 - x) f(x) + 1 = 0.$$ Then $$x \left( \sum_{n=0}^{\infty} a_n x^n \right)^2 + 1 = \sum_{n=0}^{\infty} a_n x^n - \sum_{n=0}^{\infty} a_n x^{n+1} \ \Rightarrow \ \sum_{n=0}^{\infty} \left( \sum_{k=0}^{n} a_k a_{n-k} \right) x^{n+1} = \sum_{n=0}^{\infty} (a_{n+1} - a_n) x^{n+1}$$ and from here, we get $$a_{n+1} = a_n + \sum_{k=0}^{n} a_k a_{n-k}.$$ If $a_0, a_1, \dots, a_n$ be integers, then $a_{n+1}$ is also integer. We know that $a_0 = 1, a_1 = 2$ are integer numbers, so all terms of the sequence $(a_n)$ are integers by induction.