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$.

| cite | improve this answer | |
  • $\begingroup$ Is there any proof that $a_n$ can only be calculated using recursion? $\endgroup$ – vauge Feb 2 '15 at 15:20
  • $\begingroup$ @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. $\endgroup$ – John Bentin Feb 3 '15 at 0:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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