# Non-linear Recursion

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.

-
Nonlinear recurrences are much, much harder to deal with than linear recurrences, and in general you shouldn't expect anything like a reasonable close form. For example, the logistic map (en.wikipedia.org/wiki/Logistic_map) exhibits chaotic behavior. –  Qiaochu Yuan Apr 25 '12 at 0:05
Even having a closed form wouldn't help much. For example, it's an open problem whether any of the sequences $a_n = n^2 + 1$ or $a_n = 2^n + 1$ or $a_n = 2^n - 1$ contain infinitely many primes (en.wikipedia.org/wiki/Bunyakovsky_conjecture, en.wikipedia.org/wiki/Fermat_number, en.wikipedia.org/wiki/Mersenne_prime). –  Qiaochu Yuan Apr 25 '12 at 0:47
Hmm, would going the other way using number theory be more productive? Such as looking for primes such that 2p-1 is a square and working backwards from there? –  Alexander L Apr 25 '12 at 1:07

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.