Recurring Styles #9 - Integers for a Condition!

Number Theory Level 5

$\large{(n+1)(n-2)x_{n+1} = n(n^2 - n - 1)x_n - (n-1)^3 x_{n-1}}$

Let $(x_n)_{n \geq 2}$ be a sequence such that $x_2 = 1, x_3 = 1$ , and for all $n \geq 3$ , the above recurrence relation satisfies.

For which all values of $n, \ n \geq 4$ is every $x_n$ an integer?

Only when

n

is an odd number. Only when

n

is an even number. Only when

n

is a prime number. Only when

n \equiv 1 \pmod 4

. Only when

n \equiv 1 \pmod 6

. Only when

n \equiv -1 \pmod 4

. Only when

n \equiv -1 \pmod 6

1 solution

Satyajit Mohanty
Aug 23, 2015

Let $y_n = nx_n - 1$ . Then $y_2 = 1, y_3 = 2$ and for $n \geq 3$ ,

$\large{(n-2)y_{n+1} = (n^2 - n - 1)y_n - (n-1)^2 y_{n-1}}$

thus, $(n-2)(y_{n+1} - y_n) = (n-1)^2 (y_n - y_{n-1})$

Let $z_n = y_n - y_{n-1}$ . Then $z_3 = 1$ and $z_{n+1} = \dfrac{(n-1)^2}{n-2} z_n$ for $n \geq 3$ .

It follows easily that $z_n = (n-2) \cdot (n-2)!$ for all $n \geq 3$ . Then:

$\large{y_n = (y_n - y_{n-1}) + (y_{n-1} - y_{n-2}) + (y_{n-2} - y_{n-3}) + \ldots + (y_3 - y_2) + y_2 }$

$\large{= z_n + z_{n-1} + z_{n-2} + \ldots + z_3 + y_2 = 1 + \sum_{k=1}^{n-2} k \cdot k! = (n-1)! }$

And the last equality can be obtained by Induction or telescoping series, etc.

Therefore for $n \geq 2$ , we have $x_n = \dfrac{(n-1)! +1}{n}$ .

Thus, $x_n$ is an integer if and only if $n$ divides $(n-1)! +1$ , which is equivalent to $n$ being prime, according to Wilson's Theorem .