I'm trying to prove (or disprove and improve if possible) that the sequence $a_{n+1}=\frac{a_n^2+1}{2}$, where $a_0$ is an odd number greater than 1 contains an infinite number of primes. However, I am having trouble finding a closed form solution to this non-linear recursive definition. I know that if we were dealing with a linear recurrence relation, we would find the roots of the characteristic polynomial and solve it that way. So I tried to do a similar thing this time by letting $2f(x+1)=f(x)^2+1$ $=>$ $f'(x+1)=f'(x)f(x)$ and if we assume that f(x) is of the form $c_1 r_1^x+c_2 r_2^x+…+c_n r_n^x$ we could take the derivative and perhaps do something useful? I'm not sure of what I should try.
[Math] Non-linear Recursion
prime numbersrecurrence-relationsrecursion
Best Answer
It has never been proved there are infinitely many primes of the form $(t^2+1)/2$, and not for want of trying, so proving that your sequence contains an infinity of primes is hopeless. It might be possible to find some $a_0\ge3$ such that your sequence provably fails to contain an infinity of primes. For example, taking $a_0=3$, you will get $a_n$ a multiple of $5$ for all odd $n$. If you can find some other primes that handle other sequences of subscripts, maybe you could find enough to cover all sufficiently large $n$. And if not for $a_0=3$, maybe for some other $a_0$. It can't hurt to do a few calculations to see what turns up.