Crthuky

My son gave me the following recurrence formula for $x_n$ ($nge2$):

$$(n+1)(n-2)x_n+1=n(n^2-n-1)x_n-(n-1)^3x_n-1tag1$$
$$x_2=x_3=1$$

The task I got from him:

• The sequence has an interesting property, find it out.


• Make a conjecture and prove it.

Obviously I had to start with a few values and calculating them by hand turned out to be difficult. So I used Mathematica and defined the sequence as follows:

b[n_] := b[n] = n (n^2 - n - 1) a[n] - (n - 1)^3 a[n - 1];
a[n_] := a[n] = b[n - 1]/(n (n - 3));
a[2] = 1;
a[3] = 1;

And I got the following results:

$$ a_4=frac74, a_5=5, a_6=frac1216, a_7=103, a_8=frac50418, a_9=frac403219, \ a_10=frac36288110, a_11=329891, a_12=frac3991680112, a_13=36846277, a_14=frac622702080114dots$$

Numbers don't make any sense but it's strange that the sequence produces integer values from time to time. It's not something that I expected from a pretty complex definition like (1).

So I decided to find the values of $n$ producing integer values of $a_n$. I did an experiment for $2le n le 100$:

table = Table[i, a[i], i, 2, 100];
integers = Select[table, (IntegerQ[#[[2]]]) &];
itegerIndexes = Map[#[[1]] &, integers]

...and the output was:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 
59, 61, 67, 71, 73, 79, 83, 89, 97

Conjecture (pretty amazing, at least to me):

$a_n$ is integer iff $n$ is prime.

Interesting primality test, isn't it? The trick is to prove that it's correct. I have started with substitution:

$$y_n=n x_n$$

...which simplifies (1) a bit:

$$(n-2)y_n+1=(n^2-n-1)y_n-(n-1)^2y_n-1$$

...but I did not get much further (the next step, I guess, should be rearrangement).

The given difference equation can be solved in the following way. We have for $nge 3$,
$$
(n-2)(y_n+1-y_n) = (n-1)^2(y_n-y_n-1),\
fracy_n+1-y_nn-1=(n-1)fracy_n-y_n-1n-2.
$$ If we let $displaystyle z_n=fracy_n-y_n-1n-2$, it follows that
$$
z_n+1=(n-1)z_n=(n-1)(n-2)z_n-1=cdots =(n-1)!z_3=(n-1)!frac3x_3-2x_21=(n-1)!
$$ This gives
$$
y_n+1-y_n=(n-1)(n-1)!=n!-(n-1)!,
$$ hence $y_n = nx_n = (n-1)!+c$ for some $c$. Plugging $n=2$ yields $2=1!+c$, thus we have that $$displaystyle x_n =frac(n-1)!+1n.$$

The $n^rmth$ term of the sequence is $dfrac(n-1)! + 1n$, which is an integer if and only if $n$ is prime (according to Wilson's Theorem).