Abstract
Jacobi said ‘man muss immer umkehren’. And indeed it takes a genius like Michael Somos to take a specific nonlinear 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 us follow Jacobi's advise and go backwards. Rather than try to shoot a target 50 m away, and most probably miss it, let us shoot first, and then draw the bull's eye. Then we are guaranteed to be champion target-shooters. So let us take a sequence of integers that manifestly and obviously only consists of integers, and ask our beloved computers to find nonlinear recurrences satisfied by the sequence itself, or by well-defined subsequences.
Acknowledgements
We wish to thank the members of the following multiset: {FirstReferee, SecondReferee, Edinah Gnang, Eric Rowland} for insightful remarks that considerably improved the exposition. Eric Rowland raised the intriguing question whether the original Somos-4 sequence is a subsequence of a C-finite sequence. Good question! We are hereby offering to donate $100 to the OEIS Foundation in honour of the first human (or machine) to answer this intriguing question. This work was supported in part by the NSF.
Notes
This article accompanied by Maple package. NesSomos downloadable from Zeilberger's website.