Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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 ( 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 (,, – 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
up vote 3 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.