Proposed by Khakimboy Egamberganov, ICTP, Italy
Hint: Determine the generating function ∑ a n x n \sum a_n x^n ∑ a n x n .
Solution. Take the generating function of this sequence
f ( x ) = ∑ n = 0 ∞ a n x n . f(x) = \sum_{n=0}^{\infty} a_n x^n. f ( x ) = n = 0 ∑ ∞ a n x n .
It is easy to see that the sequence is increasing and
a n + 1 a n = ( 6 n + 3 ) a n − ( n − 1 ) a n − 1 ( n + 2 ) a n < 6 n + 3 n + 2 ⇒ lim sup n → ∞ a n + 1 a n ≤ 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. a n a n + 1 = ( n + 2 ) a n ( 6 n + 3 ) a n − ( n − 1 ) a n − 1 < n + 2 6 n + 3 ⇒ n → ∞ lim sup a n a n + 1 ≤ 6.
So the generating function converges in some neighbourhood of 0 0 0 . Then, we have
f ( x ) = 1 + 2 x + ∑ n = 2 ∞ a n x n = 1 + 2 x + ∑ n = 0 ∞ a n + 2 x n + 2 = 1 + 2 x + ∑ n = 0 ∞ 6 n + 9 n + 3 a n + 1 x n + 2 − ∑ n = 0 ∞ n n + 3 a n x n + 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}. f ( x ) = 1 + 2 x + n = 2 ∑ ∞ a n x n = 1 + 2 x + n = 0 ∑ ∞ a n + 2 x n + 2 = 1 + 2 x + n = 0 ∑ ∞ n + 3 6 n + 9 a n + 1 x n + 2 − n = 0 ∑ ∞ n + 3 n a n x n + 2 .
Let f 1 ( x ) = ∑ n = 0 ∞ 6 n + 9 n + 3 a n + 1 x n + 2 f_1(x) = \sum_{n=0}^{\infty}\frac{6n+9}{n+3}a_{n+1}x^{n+2} f 1 ( x ) = ∑ n = 0 ∞ n + 3 6 n + 9 a n + 1 x n + 2 and f 2 ( x ) = ∑ n = 0 ∞ n n + 3 a n x n + 2 f_2(x) = \sum_{n=0}^{\infty}\frac{n}{n+3}a_n x^{n+2} f 2 ( x ) = ∑ n = 0 ∞ n + 3 n a n x n + 2 . Then
( x f 1 ( x ) ) ′ = ∑ n = 0 ∞ ( 6 n + 9 ) a n + 1 x n + 2 = 6 x 2 ∑ n = 0 ∞ ( n + 1 ) a n + 1 x n + 3 x ∑ n = 0 ∞ a n + 1 x n + 1 = 6 x 2 f ′ ( x ) + 3 x ( 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) ( x f 1 ( x ) ) ′ = n = 0 ∑ ∞ ( 6 n + 9 ) a n + 1 x n + 2 = 6 x 2 n = 0 ∑ ∞ ( n + 1 ) a n + 1 x n + 3 x n = 0 ∑ ∞ a n + 1 x n + 1 = 6 x 2 f ′ ( x ) + 3 x ( f ( x ) − 1 )
and
( x f 2 ( x ) ) ′ = ∑ n = 0 ∞ n a n x n + 2 = x 2 ∑ n = 0 ∞ ( n + 1 ) a n x n − x 2 ∑ n = 0 ∞ a n x n = x 2 ( x f ( x ) ) ′ − x 2 f ( x ) = x 3 f ′ ( 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). ( x f 2 ( x ) ) ′ = n = 0 ∑ ∞ n a n x n + 2 = x 2 n = 0 ∑ ∞ ( n + 1 ) a n x n − x 2 n = 0 ∑ ∞ 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 f f :
( x f ( x ) ) ′ = 1 + 4 x + ( x f 1 ( x ) ) ′ − ( x f 2 ( x ) ) ′ = 1 + x + ( 6 x 2 − x 3 ) f ′ ( x ) + 3 x f ( x ) (xf(x))' = 1 + 4x + (xf_1(x))' - (xf_2(x))' = 1 + x + (6x^2 - x^3)f'(x) + 3xf(x) ( x f ( x ) ) ′ = 1 + 4 x + ( x f 1 ( x ) ) ′ − ( x f 2 ( x ) ) ′ = 1 + x + ( 6 x 2 − x 3 ) f ′ ( x ) + 3 x f ( x )
or, equivalently,
( x 3 − 6 x 2 + x ) f ′ ( x ) + ( 1 − 3 x ) f ( x ) − 1 − x = 0. (x^3 - 6x^2 + x)f'(x) + (1-3x)f(x) - 1 - x = 0. ( x 3 − 6 x 2 + x ) f ′ ( x ) + ( 1 − 3 x ) f ( x ) − 1 − x = 0.
So, we need solve this differential equation in some sufficiently smaller neighbourhood of 0 0 0 . We know that f ( 0 ) = 1 f(0) = 1 f ( 0 ) = 1 and we need a neighbourhood of 0 0 0 such that x 2 − 6 x + 1 > 0 x^2 - 6x + 1 > 0 x 2 − 6 x + 1 > 0 . Then
f ′ ( x ) + 1 − 3 x x ( x 2 − 6 x + 1 ) f ( x ) = 1 + x x ( x 2 − 6 x + 1 ) f'(x) + \frac{1-3x}{x(x^2-6x+1)}f(x) = \frac{1+x}{x(x^2-6x+1)} f ′ ( x ) + x ( x 2 − 6 x + 1 ) 1 − 3 x f ( x ) = x ( x 2 − 6 x + 1 ) 1 + x
for
x ≠ 0 x \ne 0 x = 0 . So the integral multiplier is
μ ( x ) = x x 2 − 6 x + 1 \mu(x) = \dfrac{x}{\sqrt{x^2-6x+1}} μ ( x ) = x 2 − 6 x + 1 x and
( f ( x ) μ ( x ) ) ′ = x + x 2 ( x 2 − 6 x + 1 ) 3 2 , (f(x)\mu(x))' = \frac{x+x^2}{(x^2-6x+1)^{\frac{3}{2}}}, ( f ( x ) μ ( x ) ) ′ = ( x 2 − 6 x + 1 ) 2 3 x + x 2 ,
so
f ( x ) = ( 1 − x 2 x 2 − 6 x + 1 − 1 2 ) x 2 − 6 x + 1 x = 1 − x − x 2 − 6 x + 1 2 x . 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}. f ( x ) = ( 2 x 2 − 6 x + 1 1 − x − 2 1 ) x x 2 − 6 x + 1 = 2 x 1 − x − x 2 − 6 x + 1 .
We found the generating function of ( a n ) (a_n) ( a n ) in some neighbourhood of 0 0 0 , which x 2 − 6 x + 1 > 0 x^2 - 6x + 1 > 0 x 2 − 6 x + 1 > 0 . So our series uniformly converges to f ( x ) = 1 − x − x 2 − 6 x + 1 2 x f(x) = \dfrac{1-x-\sqrt{x^2-6x+1}}{2x} f ( x ) = 2 x 1 − x − x 2 − 6 x + 1 in ∣ x ∣ < 3 − 2 2 |x| < 3 - 2\sqrt{2} ∣ x ∣ < 3 − 2 2 .
Instead of computing the coefficients of the Taylor series of f ( x ) f(x) f ( x ) directly, we will find another recurrence relation for ( a n ) (a_n) ( a n ) . It is easy to see that f ( x ) f(x) f ( x ) satisfies the quadratic equation x t 2 − ( 1 − x ) t + 1 = 0 xt^2 - (1-x)t + 1 = 0 x t 2 − ( 1 − x ) t + 1 = 0 . So
x f ( x ) 2 − ( 1 − x ) f ( x ) + 1 = 0. xf(x)^2 - (1-x)f(x) + 1 = 0. x f ( x ) 2 − ( 1 − x ) f ( x ) + 1 = 0.
Then
x ( ∑ n = 0 ∞ a n x n ) 2 + 1 = ∑ n = 0 ∞ a n x n − ∑ n = 0 ∞ a n x n + 1 ⇒ ∑ n = 0 ∞ ( ∑ k = 0 n a k a n − k ) x n + 1 = ∑ n = 0 ∞ ( a n + 1 − a n ) x n + 1 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} \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} x ( n = 0 ∑ ∞ a n x n ) 2 + 1 = n = 0 ∑ ∞ a n x n − n = 0 ∑ ∞ a n x n + 1 ⇒ n = 0 ∑ ∞ ( k = 0 ∑ n a k a n − k ) x n + 1 = n = 0 ∑ ∞ ( a n + 1 − a n ) x n + 1
and from here, we get
a n + 1 = a n + ∑ k = 0 n a k a n − k . a_{n+1} = a_n + \sum_{k=0}^{n}a_k a_{n-k}. a n + 1 = a n + k = 0 ∑ n a k a n − k .
If a 0 , a 1 , … , a n a_0, a_1, \dots, a_n a 0 , a 1 , … , a n be integers, then a n + 1 a_{n+1} a n + 1 is also integer. We know that a 0 = 1 a_0 = 1 a 0 = 1 , a 1 = 2 a_1 = 2 a 1 = 2 are integer numbers, so all terms of the sequence ( a n ) (a_n) ( 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.