Let $t_1$, $t_2$,.... $t_n$ is a sequence where $t_1=2$ and $t_{n+1}=t_n{^2}-t_n+1$. Prove that if $m\ne n$, then $t_m$ and $t_n$ are coprime.

Question

Let $t_1$, $t_2$,$\enspace$.... $t_n$ is a sequence of natural numbers. The sequence is defined by these equalities - $t_1=2$ $\enspace$ and $\enspace$ $t_{n+1}=t_n{^2}-t_n+1$. $\enspace$ Prove that if $m\ne n$, $\enspace$ then $t_m$ and $t_n$ are mutually prime (coprime).

What I tried:

the sequence is: 2, 3, 7; 43, 1807 ...

if $t_m$ and $t_n$ are consecutive then $t_n=t_m{^2}-t_m+1$

Let $d|t_m$ and $d|t_n$ $\Rightarrow$ $d|t_m{^2}-t_m$ and $d|t_m{^2}-t_m+1$ $\Rightarrow$ $d=1$ $\Rightarrow$ $t_m$ and $t_n$ are coprime.

Is that enough for proving?

How to prove it if $t_m$ and $t_n$ are not consecutive but arbitrary?

Answer 1

You may prove by induction that $$ t_{n} = 1+ t_{n-1}\cdot t_{n-2}\cdot \ldots\cdot t_1 $$ from which the claim is obvious. This is the Sylvester sequence A000058.

Answer 2

Let $p$ be a prime. Suppose that $t_n\equiv 0 \pmod p$. Then it is easy to see that $t_{k}\equiv 1 \pmod p$ for every $k>n$ so only one (at most) of the $t_i$ can be divisible by $p$.