2019-03-15 15:15:25 8 Comments

My son gave me the following recurrence formula for $x_n$ ($n\ge2$):

$$(n+1)(n-2)x_{n+1}=n(n^2-n-1)x_n-(n-1)^3x_{n-1}\tag{1}$$ $$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=\frac{7}{4}, \ a_5=5, \ a_6=\frac{121}{6}, \ a_7=103, \ a_8=\frac{5041}{8}, \ a_9=\frac{40321}{9}, \\ a_{10}=\frac{362881}{10}, \ a_{11}=329891, \ a_{12}=\frac{39916801}{12}, \ a_{13}=36846277, \ a_{14}=\frac{6227020801}{14}\dots$$

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 $2\le 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 an integer if and only if $n$ is prime.

Interesting primality test, isn't it? The trick is to prove that it's correct. I have started with the 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).

### Related Questions

#### Sponsored Content

#### 1 Answered Questions

### [SOLVED] Find values of $a$ for which the function is periodic.

**2019-01-12 16:44:37****Yellow****65**View**1**Score**1**Answer- Tags: number-theory recurrence-relations

#### 1 Answered Questions

### [SOLVED] How to evaluate series based on recurrence equation

**2018-03-06 17:38:13****lfmc****34**View**0**Score**1**Answer- Tags: sequences-and-series recurrence-relations

#### 0 Answered Questions

### On integer sequences of the form $\sum_{n=1}^N (a(n))^2H_n^2,$ where $H_n$ is the $n$th harmonic number: refute my conjecture and add yourself example

**2018-02-08 12:19:52****user243301****44**View**1**Score**0**Answer- Tags: sequences-and-series number-theory elementary-number-theory conjectures harmonic-numbers

#### 0 Answered Questions

### A recurrence involving the radical of an integer

**2017-12-22 14:42:24****user243301****63**View**0**Score**0**Answer- Tags: elementary-number-theory recurrence-relations asymptotics analytic-number-theory prime-factorization

#### 1 Answered Questions

### [SOLVED] Series over $ x_n^2 $ diverges. Find sequence $ y_n^2 $ such that series over $ y_n^2 $ converges and series over $ x_n y_n $ diverges

**2016-10-25 15:50:07****Cyianor****107**View**3**Score**1**Answer- Tags: sequences-and-series convergence divergence

#### 4 Answered Questions

### [SOLVED] A man died. Let's divide the estate!!! How?

**2015-06-23 10:14:59****anonymous****241**View**0**Score**4**Answer- Tags: algebra-precalculus elementary-number-theory

#### 2 Answered Questions

### [SOLVED] Proving a Pellian connection in the divisibility condition $(a^2+b^2+1) \mid 2(2ab+1)$

**2014-05-26 12:48:24****Kieren MacMillan****188**View**4**Score**2**Answer- Tags: elementary-number-theory divisibility

#### 3 Answered Questions

### [SOLVED] Proof that $x^2 - 2y^2 = -1$ has a recurring solution for $x$

**2013-12-25 23:37:40****jamaicanworm****346**View**2**Score**3**Answer- Tags: recurrence-relations diophantine-equations

#### 3 Answered Questions

### [SOLVED] A good way to find $a_{50000}$ where $a_n$ is a number in the form of $2^j\cdot 3^k$

**2013-11-01 14:45:09****mathlove****98**View**3**Score**3**Answer- Tags: sequences-and-series computational-mathematics

#### 2 Answered Questions

### [SOLVED] Generalized Fibonacci Sequence Question

**2011-12-28 01:40:35****itdoesntwork****416**View**17**Score**2**Answer- Tags: sequences-and-series limits convergence recurrence-relations fibonacci-numbers

## 4 comments

## @Trebor 2019-03-20 03:52:24

My process to find the solution probably involves too far a leap of faith, but I will post it anyway.

First, after writing out at least 8 terms, I noticed that, apart from integers, all terms are of the form $a_n=?/n$. So naturally I turned towards the sequence $b_n\equiv a_n\cdot n$, which goes like $3, 7, 25, 121, 721, 5041, 40321, \dots$.

Now my intuition senses the number sequence $504*, 4032*$, which resembles the factorial of 7&8, moreover, a lot of them seems to end in $1$. So I made a further conjecture that

A quick check of Wilson's theorem shows that it is compatible with the original conjecture. Thus, we seem to be on the right track. This can be easily proved by induction.

## @Lucian 2019-03-16 03:14:45

Too long for a comment:Actually, they do !:-) Just take a closer look at the sequence's composite-index denominators, and notice the following:Let us now rewrite the sequence's prime-indexed elements in a similar manner, for a more uniform approach:

At this point, we might be able to cheat, and use

OEISto identify the afferent sequence $\color{blue}{b_n=n\cdot 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:In short, $\color{blue}{r_n=\dfrac{b_{n+1}}{b_n}\simeq n}.~$ A type of “modified geometric progression”, as it were, with a

variableratio 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 $\color{blue}{b_{n+1}=n\cdot b_n-(n-1)}.~$ Now we are left with showing that, for prime values of the indexp,$~\color{blue}{a_p=\dfrac{b_p}p\in\mathbb N},~$ starting from $\color{blue}{b_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 ? :-)## @YiFan 2019-03-16 03:22:24

I'm confused. What does this add to the existing answers which already give the explicit formula $x_n=((n-1)!+1)/n$?

## @Lucian 2019-03-16 03:23:51

@YiFan: Clarity, perhaps ? Maybe a bit of intuition ?

## @TreFox 2019-03-17 01:25:39

+1. These types of answers are by far the most helpful IMO. They encourage discovery and intuitive thinking rather than just giving the answer.

## @Song 2019-03-15 15:54:58

The given difference equation can be solved in the following way. We have for $n\ge 3$, $$ (n-2)(y_{n+1}-y_n) = (n-1)^2(y_n-y_{n-1}),\\ \frac{y_{n+1}-y_n}{n-1}=(n-1)\frac{y_{n}-y_{n-1}}{n-2}. $$ If we let $\displaystyle z_n=\frac{y_{n}-y_{n-1}}{n-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)!\frac{3x_3-2x_2}{1}=(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)!+1}{n}.$$

## @FredH 2019-03-15 15:22:20

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

## @Oldboy 2019-03-15 15:35:55

Yes, but it is not obvious. Can you prove it?

## @FredH 2019-03-15 15:38:00

I can and I did. The algebra is tedious but not difficult.

## @Oldboy 2019-03-15 19:48:00

I have upvoted your answer but I accepted the one with the whole solution. :)