uniolympiads Ελληνικά

IMC 2019, Day 1, Problem 4

Define the sequence a0,a1,…a_0, a_1, \dots of numbers by the following recurrence:

a0=1,a1=2,(n+3)an+2=(6n+9)an+1−nanfor n≥0.a_0 = 1, \quad a_1 = 2, \quad (n+3)a_{n+2} = (6n+9)a_{n+1} - na_n \quad \text{for } n \ge 0.

Prove that all terms of this sequence are integers.

Original from the official PDFDene the sequence a 0 , a 1 , . . . of numbers by the following recurrence: a 0 = 1, a 1 = 2, (n + 3)a n+2 = (6n + 9)a n+1 − na n Prove that all terms of this sequence are integers. for n ≥ 0 .

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Proposed by Khakimboy Egamberganov, ICTP, Italy

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

Solution. Take the generating function of this sequence

f(x)=∑n=0∞anxn.f(x) = \sum_{n=0}^{\infty} a_n x^n.

It is easy to see that the sequence is increasing and

an+1an=(6n+3)an−(n−1)an−1(n+2)an<6n+3n+2⇒lim sup⁡n→∞an+1an≤6.\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 00. Then, we have

f(x)=1+2x+∑n=2∞anxn=1+2x+∑n=0∞an+2xn+2=1+2x+∑n=0∞6n+9n+3an+1xn+2−∑n=0∞nn+3anxn+2.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 f1(x)=∑n=0∞6n+9n+3an+1xn+2f_1(x) = \sum_{n=0}^{\infty}\frac{6n+9}{n+3}a_{n+1}x^{n+2} and f2(x)=∑n=0∞nn+3anxn+2f_2(x) = \sum_{n=0}^{\infty}\frac{n}{n+3}a_n x^{n+2}. Then

(xf1(x))′=∑n=0∞(6n+9)an+1xn+2=6x2∑n=0∞(n+1)an+1xn+3x∑n=0∞an+1xn+1=6x2f′(x)+3x(f(x)−1)(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
(xf2(x))′=∑n=0∞nanxn+2=x2∑n=0∞(n+1)anxn−x2∑n=0∞anxn=x2(xf(x))′−x2f(x)=x3f′(x).(xf_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(xf(x))' - x^2 f(x) = x^3 f'(x).

Using this relations, we arrive at the following differential equation for ff:

(xf(x))′=1+4x+(xf1(x))′−(xf2(x))′=1+x+(6x2−x3)f′(x)+3xf(x)(xf(x))' = 1 + 4x + (xf_1(x))' - (xf_2(x))' = 1 + x + (6x^2 - x^3)f'(x) + 3xf(x)
or, equivalently,
(x3−6x2+x)f′(x)+(1−3x)f(x)−1−x=0.(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 00. We know that f(0)=1f(0) = 1 and we need a neighbourhood of 00 such that x2−6x+1>0x^2 - 6x + 1 > 0. Then

f′(x)+1−3xx(x2−6x+1)f(x)=1+xx(x2−6x+1)f'(x) + \frac{1-3x}{x(x^2-6x+1)}f(x) = \frac{1+x}{x(x^2-6x+1)}
for x≠0x \ne 0. So the integral multiplier is μ(x)=xx2−6x+1\mu(x) = \dfrac{x}{\sqrt{x^2-6x+1}} and
(f(x)μ(x))′=x+x2(x2−6x+1)32,(f(x)\mu(x))' = \frac{x+x^2}{(x^2-6x+1)^{\frac{3}{2}}},
so
f(x)=(1−x2x2−6x+1−12)x2−6x+1x=1−x−x2−6x+12x.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 (an)(a_n) in some neighbourhood of 00, which x2−6x+1>0x^2 - 6x + 1 > 0. So our series uniformly converges to f(x)=1−x−x2−6x+12xf(x) = \dfrac{1-x-\sqrt{x^2-6x+1}}{2x} in ∣x∣<3−22|x| < 3 - 2\sqrt{2}.

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

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

Then

x(∑n=0∞anxn)2+1=∑n=0∞anxn−∑n=0∞anxn+1⇒∑n=0∞(∑k=0nakan−k)xn+1=∑n=0∞(an+1−an)xn+1x\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} \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
an+1=an+∑k=0nakan−k.a_{n+1} = a_n + \sum_{k=0}^{n}a_k a_{n-k}.

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

Transcribed from the official solutions, pages 3–4. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?