Defining irreducible polynomials recursively: how far can we go? Fix $n\in\mathbb N$ and a starting polynomial $p_n=a_0+a_1x+\dots+a_nx^n$ with $a_k\in\mathbb Z\ \forall k$ and $a_n\ne0$.
Define $p_{n+1},p_{n+2},\dots$ recursively by $p_r = p_{r-1}+a_rx^r$ such that $a_r\in \mathbb N$ is the smallest such that $p_r$ is irreducible over $\mathbb Q$. It should not be too hard to prove (but how?) that there will always be an $r_0$ such that $a_r=1\ \forall r>r_0$. Let $r_0$ be smallest possible. E.g. for $n=0$ and $p_0\equiv 1$, we have to go as far as $r_0=11$, getting before that $(a_0,\dots,a_{11})=(1,1,1,2,2,3,1,2,1,3,1,2)$.
Questions (apart from proving the existence of $r_0$): 

  
*
  
*Is it possible to construct, for a certain $n$, a polynomial $p_n$ such that $a_{n+1}$ is bigger than $3$ or even arbitrarily large?

(From the above example, for $n=4$ and $p_n=1+x+x^2+2x^3+2x^4$, we get $a_5=3$, likewise for $n=8$ and $p_n=1+x+x^2+2x^3+2x^4+3x^5+x^6+2x^7+x^8$, we get $a_9=3$.)

  
*
  
*Is it possible to construct, for a certain $n$, a polynomial $p_n$ such that $r_0-n$ is bigger than $11$? If so, how big can $r_0-n$ be?


The answer to your first question is YES (and a similar
method can probably answer positively your second
question as well). One can use the following lemma :
Lemma Let $n,g$ be positive integers. Then there is a polynomial
$Q_{n,g}\in {\mathbb Z}[X]$ of degree $\leq n$ such that 
$Q_{n,g}(i)=i^g$ for any integer $i$ between $1$ and $n+1$.
Answer to question 1 using the lemma. Take $p_n=-Q_{n,n+2}$, so that
$p_n(x)=-x^{n+2}$ for $1\leq x \leq n+1$. 
Then for $a\leq n+1$, the polynomial $ax^{n+1}+p_n(x)$ is zero
when $x=a$, so it is not irreducible. We deduce $a_{n+1} \geq n+2$
for this $p_n$.
Proof of lemma By Lagrange interpolation, we know that
there is a unique polynomial $Q_{n,g}\in {\mathbb Q}[X]$ satisfying the
conditions. What we need to show is that the coefficients of $Q_{n,g}$
are integers. 
   If $g\leq n$, then $Q_{n,g}(x)=x^g$ and we are done. For $g>n$,
 the identity
$$
 \frac{x^g-1}{x-1}=\sum_{k=0}^{g-1} \binom{g}{k+1} (x-1)^k
 $$  
shows that when $2 \leq x \leq n+1$, we have
$$
x^g=1+(x-1)\bigg( \sum_{k=0}^{g-1} \binom{g}{k+1} Q_{n-1,k}(x-1)\bigg)
$$
and so we may take
 $$
 Q_{n,g}(x)=1+(x-1)\bigg(\sum_{k=0}^{g-1} \binom{g}{k+1} Q_{n-1,k}(x-1)\bigg)
 $$
and we are done by induction.   
