International Mathematics Competition
for University Students
2019

IMC2019: Day 1, Problem 4

Problem 4. Define the sequence \(\displaystyle a_0,a_1,\ldots\) of numbers by the following recurrence:

\(\displaystyle a_0=1, \quad a_1=2, \quad (n+3)a_{n+2}=(6n+9)a_{n+1}- na_n \quad \text{for \(\displaystyle n\ge 0\).} \)

Prove that all terms of this sequence are integers.

Proposed by Khakimboy Egamberganov, ICTP, Italy

Solution. Take the generating function of this sequence

\(\displaystyle f(x) = \sum_{n=0}^{\infty} a_nx^n. \)

It is easy to see that the sequence is increasing and

\(\displaystyle \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\rightarrow \infty} \frac{a_{n+1}}{a_n} \le 6.\)

So the generating function converges in some neighbourhood of \(\displaystyle 0\). Then, we have

\(\displaystyle f(x) = 1+2x+\sum_{n=2}^{\infty} a_nx^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_nx^{n+2}. \)

Let \(\displaystyle \displaystyle f_1(x) = \sum_{n=0}^{\infty} \frac{6n+9}{n+3}a_{n+1}x^{n+2}\) and \(\displaystyle \displaystyle f_2(x) = \sum_{n=0}^{\infty} \frac{n}{n+3}a_nx^{n+2} \). Then

\(\displaystyle (xf_1(x))' = \sum_{n=0}^{\infty} (6n+9)a_{n+1}x^{n+2} = 6x^2\sum_{n=0}^{\infty} (n+1)a_{n+1}x^n + 3x\sum_{n=0}^{\infty} a_{n+1}x^{n+1} = 6x^2 f'(x)+3x(f(x)-1) \)

and

\(\displaystyle (xf_2(x))' = \sum_{n=0}^{\infty} na_nx^{n+2} = x^2 \sum_{n=0}^{\infty} (n+1)a_nx^{n} - x^2\sum_{n=0}^{\infty} a_nx^{n} = x^2(xf(x))' - x^2f(x) = x^3f'(x). \)

Using this relations, we arrive at the following differential equation for \(\displaystyle f\):

\(\displaystyle (xf(x))'= 1+4x+(xf_1(x))' - (xf_2(x))' = 1+x+(6x^2 - x^3)f'(x) +3xf(x) \)

or, equivalently,

\(\displaystyle (x^3-6x^2+x)f'(x)+(1-3x)f(x)-1-x=0. \)

So, we need solve this differential equation in some sufficiently smaller neighbourhood of \(\displaystyle 0\). We know that \(\displaystyle f(0)=1\) and we need a neighbourhood of \(\displaystyle 0\) such that \(\displaystyle x^2-6x+1>0\). Then

\(\displaystyle f'(x) + \frac{1-3x}{x(x^2-6x+1)}f(x) =\frac{1+x}{x(x^2-6x+1)} \)

for \(\displaystyle x\neq 0\). So the integral multiplier is \(\displaystyle \displaystyle \mu (x) = \frac{x}{\sqrt{x^2-6x+1}}\) and

\(\displaystyle (f(x)\mu (x))' = \frac{x+x^2}{(x^2-6x+1)^{\frac{3}{2}}}, \)

so

\(\displaystyle f(x) = \left( \frac{1-x}{2\sqrt{x^2-6x+1}} - \frac{1}{2} \right) \frac{\sqrt{x^2-6x+1}}{x} = \frac{1-x-\sqrt{x^2-6x+1}}{2x}. \)

We found the generating function of \(\displaystyle (a_n)\) in some neighbourhood of \(\displaystyle 0\), which \(\displaystyle x^2-6x+1 > 0\). So our series uniformly converges to \(\displaystyle \displaystyle f(x) = \frac{1-x-\sqrt{x^2-6x+1}}{2x}\) in \(\displaystyle |x|<3-2\sqrt{2}\).

Instead of computing the coefficients of the Taylor series of \(\displaystyle f(x)\) directly, we will find another recurrence relation for \(\displaystyle (a_n)\). It is easy to see that \(\displaystyle f(x)\) satisfies the quadratic equation \(\displaystyle xt^2-(1-x)t+1=0\). So

\(\displaystyle xf(x)^2-(1-x)f(x)+1 = 0. \)

Then

\(\displaystyle x\left( \sum_{n=0}^{\infty} a_nx^n \right)^2 +1 = \sum_{n=0}^{\infty} a_nx^n - \sum_{n=0}^{\infty} a_nx^{n+1} \quad \Rightarrow \quad \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

\(\displaystyle a_{n+1} = a_n + \sum_{k=0}^{n} a_{k}a_{n-k}. \)

If \(\displaystyle a_0,a_1,...,a_{n}\) be integers, then \(\displaystyle a_{n+1}\) is also integer. We know that \(\displaystyle a_0 = 1, a_1=2\) are integer numbers, so all terms of the sequence \(\displaystyle (a_n)\) are integers by induction.