FirstWritten: March 21, 2013 ; This version: June 12, 2013.
[Published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, arxiv.org, and also co-published in J. Difference Eq. Appl. v. 20(2014), 852-858.]
Jacobi said ``man muss immer umkehren''. And indeed it takes a genius like Michael Somos to take a specific non-linear recurrence, like
a(n)=(a(n-1)a(n-3)+a(n-2)^2)/a(n-4), subject to a(1)=1, a(2)=1, a(3)=1, a(4)=1,
and observe that surprise, surprise, they always generate integers. Then it takes other geniuses to actually prove this fact (and the more general so-called Laurent phenomenon).
But let's follow Jacobi's advice and go backwards. Rather than try to shoot a target fifty meters away, and most probably miss it, let's shoot first, and then draw the bull'e eye. Then we are guaranteed to be champion target-shooters. So let's take a sequence of integers that manifestly and obviously only consists of integers, and ask our beloved computers to find non-linear recurrences satisfied by the sequence itself, or by well-defined subsequences (e.g. if the original sequence is an, study bn:=an2, or even bn:=a2n.
Doron Zeilberger's Home Page