An explicitly defined integer sequence is one in which the $n^{\text{th}}$ term can be calculated as a function of $n$.
An implicitly defined integer sequence is one in which the $n^{\text{th}}$ term can be calculated as a function of some previous terms of the series.
For instance, the Fibonacci sequence $(0,1,1,2,3,5,8,\dotsc)$ is defined implicitly as $F(n) = F(n-1) + F(n-2)$. The Fibonacci sequence can also be defined explicitly, as $$F(n) = \frac{G^n - (1-G)^n}{\sqrt{5}}\quad \text{where}\ G = \frac{\sqrt{5}+1}{2}$$
My questions are:
Can all explicitly defined integer sequences be defined implicitly? If not, how can we tell which ones can?
Can all implicitly defined integer sequences be defined explicitly? If not, how can we tell which ones can?
For (1), my conjecture is that all explicitly defined integer sequences can be defined implicitly. For instance, the sequence $F(x) = x^2$ can be defined implicitly as $F(x) = 2F(x-1) - F(x-2) + 2$. Similar expressions can be found for any polynomial function. I presume that implicit definitions can also be found for exponential, periodic and other types of explicitly defined sequences.
For (2), I have not much idea here.
See what you can do with, say, $F(0) = 0,$ followed by $$ F(x) = 1 + \left( F(x -1) \right)^2 $$