# Sequences that can only be specified by recursion

As the title says, I wonder whether there are sequences that can only be specified by recursion. In other words, are there any sequences $a_k$ where there is no other way to calculate $a_n$ than calculating $a_0$, $a_1$, ..., $a_{n-1}$ before? If so, can this be proven?

Let $a_n$ be the least prime greater than $a_{n-1}^2$ $\;(n=1,2,...$ ), with $a_0=2$.
• Is there any proof that $a_n$ can only be calculated using recursion? – vauge Feb 2 '15 at 15:20
• @vauge: My best guess for this sequence $(a_n:n=0,1,...)$ is the following claim: (A1) generally $a_n$ can be calculated only by knowing $a_{n-1}$. I would further conjecture: (A2) claim A1, while true, can be neither proved nor disproved. Moreover, I hazard that: (A3) claim A2, while true, can be neither proved nor disproved; (A4) likewise for A3; (A5) etc. – John Bentin Feb 3 '15 at 0:41