A condition for a sequence defined by a recurrence relationship to all be integers I am interested in a specific sequence $\{a_n \}$ defined by a simple recurrence relationship: $$a_n = \frac {a_{n-1} ^2 +c} {b} $$ where $b,c\in \mathbb{Z}$. I want to find all $b,c$ such that there exists some integer $a_1$ such that $\{a_n\} $ are all integers.
I think that this would be a well-known problem, but I have trouble finding it. Even if this is not well-known, I cannot find a way to solve this question.
For example, if $b=3$ and $c=1$, it is fairly trivial that there exists no such $a_1 $. if $b=3$ and $c=2$, we can let $a_1 = 1 $ to make all $\{a_n \}$ be integers. However, I cannot easily work this out even in a single case, such as $b=3, c=17$. Furthermore, how can I find all $(b,c)$ such that there exists some $a_1$ such that $a_n \in \mathbb Z$ for all $n\in \mathbb{N}$?
*I posted this on SEMath, but I did not get any answers nor references. https://math.stackexchange.com/questions/1470398/a-condition-for-a-sequence-defined-by-a-recurrence-relationship-to-all-be-intege
 A: I'm going to change notation a little bit to make it easier to describe things, and to put your problem into the general framework of arithmetic dynamics. Let
$$ f(X) = \frac{X^2+c}{b}, $$
and for each $n\ge0$, let $f^n(X)$ denote the $n$'th iterate of $X$.  Then you are asking which $b,c\in\mathbb Z$ have an $a\in\mathbb Z$ such that $f^n(a)\in\mathbb Z$ for all $n\ge0$.
Some observations.


*

*The only primes that can occur in the denominator of $f^n(a)$ are primes dividing $b$.

*It suffices to find, for each prime $p\mid b$, a starting point $\alpha_p\in\mathbb Z$ so that all of the points $f^n(\alpha_p)$ are $p$-adically integral. Once you do that, you can use the Chinese Remainder Theorem to find an $a\in\mathbb Z$ with $a\equiv\alpha_p\pmod{p}$ for all $p\mid b$ and you're done. 
I am going to consider the case that $b$ is square-free and $\gcd(b,c)=1$ and that $p\mid b$ is an odd prime. Clearly a necessary condition is that $-c$ is a square mod $p$, since you need $a^2+c$ to be divisible by $p$. This means that your $a$ values must satisfy
$$ a^2 \equiv -c \pmod{p}. $$
So let's assume that you can find some $a_1\in\mathbb Z$ such that $a_1^2\equiv-c\pmod{p}$. (Note that there are only two values for $a_1\bmod p$.) The next step is to let 
$$
  u_1=\frac  { (a_1+py)^2+c } {p}
$$
and try to find $y$ so that $u_1^2\equiv-c\pmod{p}$. Then setting $a_2=a_1+py$ ensures that $f(a_2)$ and $f^2(a_2)$ are both in $\mathbb Z$. If you write out the congruence, you'll find that you can solve for $y$. (This is where I need $p\ne2$.) Repeating the process, we get a sequence $a_1,a_2,a_3,\ldots$ with the property $$ a_{n+1}\equiv a_n\pmod{p^n}
   \quad\text{and}\quad
  f^i(a_n)\in\mathbb Z\quad\text{for all $0\le i\le n$.}
$$
Hence the $a_n$ converge in $\mathbb Z_p$ to a $p$-adic number $a$ satisfying $f^n(a)\in\mathbb Z_p$ for all $n$. (Further, aside from that initial choice of $\pm a_1$, the sequence $a_n\bmod p^{n+1}$ is uniquely determined.)
Okay, now for the hard part. Is $a=\lim a_n$ in $\mathbb Z$?  If it is, you win, and if not, then there is no $\mathbb Z$ starting point that works.  Possibly $a\in\mathbb Z$ follows from the initial assumption that $b$ and $c$ are in $\mathbb Z$, but I don't see why. And my instinct says that the opposite should be true, and indeed that the value of $a$ will be transcendental over $\mathbb Q$, but again, I don't know how to prove that. 
For $p=2$, or if $p\mid\gcd(b,c)$, the analysis will be somewhat different.  And it seems easier to get your condition for $p=2$ because of the extra $2$ in the middle term when you expand $(a_n+2y)^2$.  But at the end of the day, I think it's going to come down to determining whether a certain $p$-adic limit is in $\mathbb Z$.
Addendum There are results which say that if $f(X)\in\mathbb Q(X)$ is not a polynomial and also $f^2(X)$ is not a polynomial, then $\{f^n(a):n\ge0\}$ contains only finitely many integers.
A: $\let\eps\varepsilon$This is not an answer, but just an attempt to summarize flaming (at least inspired by myself, sorry) appeared in the comments to the answer by @Joe Silverman. I would kindly ask Joe's permission to delete those comments, if all of them are correctly reflected here. It is not that convenient to walk through all of them... 
On the other hand, I may easily delete this if it disturbes someone.
So, following Joe's approach, we fix an odd $p\mid b$ (assuming $b$ is odd and square-free, and $b\nmid c$) and search for $p$-adic integers $a$ such that for $a_1=a$ the whole sequence consists of $p$-adic integers. Surely, we assume that $-c\equiv \mu^2\pmod{p}$ for some integer $\mu$. Then it is easy to see that if $(a_n)$ is as desired, then $a_n\equiv\pm \mu\pmod p$ for all $n$.
We claim that for every sequence $\eps=(\eps_1,\dots,\eps_n)$ with $\eps_i\in\{-1,1\}$, there exists a unique residue $r_{\eps}$ such that for $a_1\equiv r\pmod{p^n}$ all $a_1,\dots,a_n$ are ($p$-adic) integers with $a_i\equiv\eps_i\mu\pmod p$. The base $n=1$ is clear. For the step, apply the inductive hypothesis to $a_2,\dots,a_{n+1}$; we find that $a_2\equiv r_{\bar\eps}\pmod{p^n}$, where $\bar\eps=(\eps_2,\dots,\eps_{n+1})$. Now, from $a_1^2=ba_2-c$ we obtain two possible residues for $a_1\pmod {p^{n+1}}$ corresponding to $a_1\equiv \pm \mu\pmod p$, as required. The claim is proved.
Thus, for every infinite sequence $\eps_1,\eps_2,\dots$ there exists a sequence $r_{\eps_1},r_{\eps_1,\eps_2},\dots$ converging to some $p$-adic integer $R_{\eps_1,\eps_2,\dots}$ (obviously, these residues agree).
Now again comes the hard part. We need to find out whether one of these $p$-adic numbers is actually an integer. 
An easy case is when the sequence $\eps_1,\eps_2,\dots$ is periodic. Then, due to the uniqueness, the sequence starting from $R_\eps$ is periodic as well.  This sequence may indeed be constant, e.g. 
$$
  a_n=\frac{a_{n-1}^2+b-1}b, \quad a_1=1.
$$ 
It may also be cyclic with longer period, e.g., 
$$
  a_n=\frac{a_{n-1}^2-(1+b+b^2)}b, \quad a_1=1, \quad a_2=-(b+1).
$$ 
I am almost sure that arbitrarily long periods may appear; but for every fixed choice for $b$ and $c$ they can be found easily: since $\frac{x^2+c}b>x$ for all sufficiently large $x$, it suffices to check only the sequences consistinc of small numbers.
The case when $\eps$ is an aperiodic sequence seems to be, eh, much harder (and, perhaps, not approachable by such elementary methods). But still, some heuristics: all the $R_\eps$ form some Cantor set in $p$-adic numbers, and it has zero measure, so it is quite improbable that one of these numbers is integer. Nevertheless, it is not clear why it cannot happen (if it really cannot).
Notice also that in any case, some of the $R_\eps$ are algebraic (two of them satisfies $x^2-bx+c=0$, and some generate longer cycles), while some are transcendent (since there are continuum many of them).
