Ggtkuk

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).

Too long for a comment:

Numbers don't make any sense

Actually, they do ! :-) Just take a closer look at the sequence's composite-index denominators, and notice the following:

$$
a_colorblue4=frac7colorblue4,quad
a_5=5,quad
a_colorblue6=frac121colorblue6,quad
a_7=103,quad
a_colorblue8=frac5041colorblue8,quad
a_colorblue9=frac40321colorblue9,quad
\~\~\
a_colorblue10=frac362881colorblue10,
a_11=329891,quad
a_colorblue12=frac39916801colorblue12,quad
a_13=36846277,quaddots
$$

Let us now rewrite the sequence's prime-indexed elements in a similar manner, for a more uniform approach:

$$
a_colorblue4=frac7colorblue4,quad
a_colorblue5=frac25colorblue5,quad
a_colorblue6=frac121colorblue6,quad
a_colorblue7=frac721colorblue7,quad
a_colorblue8=frac5041colorblue8,quad
a_colorblue9=frac40321colorblue9,quad
\~\~\
a_colorblue10=frac362881colorblue10,
a_colorblue11=frac3628801colorblue11,quad
a_colorblue12=frac39916801colorblue12,quad
a_colorblue13=frac479001601colorblue13,quaddots
$$

At this point, we might be able to cheat, and use OEIS to identify the afferent sequence $colorblueb_n=ncdot a_n$ by its first few elements, yielding three possible suspects: but let's say that our mathematical virtue and intellectual integrity will prevail over our base urges of rampant curiosity, and we might resist the temptation to do so. Could we then, without any outside aide, still manage to deduce an expression for $b_n$ ? Indeed, even a superficial glance will undoubtedly reveal the growth to resemble what one might otherwise expect to see in a geometric progression, rather than an arithmetic one. We then have:

$$
r_colorblue4=frac257simeqcolorblue4,quad
r_colorblue5=frac12125simeqcolorblue5,quad
r_colorblue6=frac721121simeqcolorblue6,quad
r_colorblue7=frac5041721simeqcolorblue7,quaddots
$$

In short, $colorbluer_n=dfracb_n+1b_nsimeq n.~$ A type of “modified geometric progression”, as it were, with a variable ratio equal to the index itself: Does this sound in any way familiar ? If no, there is still no need to worry: We'll get to the bottom of it soon enough, anyway. More precisely, we have $colorblueb_n+1=ncdot b_n-(n-1).~$ Now we are left with showing that, for prime values of the index p, $~colorbluea_p=dfracb_ppinmathbb N,~$ starting from $colorblueb_2=2.~$ Could mathematical induction work in this case, or does the seemingly random distribution of primes throw a wrench into such an approach ? And, if so, could we then maybe slightly modify it, to fit the new conditions ? What would you say ? :-)