To elaborate: You can define "simplest program", for instance, as "shortest string consisting of [0-9], plus, minus, times, parentheses, and the symbol 'n' that when evaluated as a mathematical expression yields the given sequence for n=1, 2, 3...". You can then find a suitable string, like "((8 * n + 4) * n - 4) * n + 1", and do an exhaustive search of shorter strings to show that no better string exists. That would be 16^16, or less than a year on a computer that can knock off a trillion strings per second -- less if you use logic to constrain the search space.
However, realistically, a person asking such a question is merely looking for a "good" solution, not necessarily a proven-optimal one, as there may be multiple reasonable explanations for a given sequence. Rather, the value of the "simplest program" criteria is that it allows you to compare proposed solutions. So, yes, for any given number, there is a formula to make it next in the sequence. But by applying the "simplest program" criteria, we see that some formulas -- and hence some values -- are better than others.
You can simply modify your definition of "simplest" to be "shortest that completes in a million steps" or some such. A program that takes so long to finish that you're not sure it will return your desired value is probably not the simplest.
It only takes a counter-example (an example of a shorter program) to show that an answer is incorrect, but you could probably pick up a Turing Award or two if you find a way to put a tight bound on the Kolmogorov complexity of a bit string.
Sure, there's a bunch of trivial/easy ones for programs that do almost nothing, but I really wonder if are there any interesting programs for which tight bounds are known?
Even if we limit it to primitive recursive functions, how can we put a bound on the Kolmogorov complexity of one? We'd need some way of coming up with bounds on the smallest Turing machine to compute that function.
Is it defined well enough to allow you to draw that kind of conclusions without any context?
What if that question was meant to find people who think about what is the real goal and asking "are we thinking about the same thing, or should we agree on more details" instead of attacking the problem at hand. Otherwise "0" is a perfectly good answer (for any reason).
This discussion has as much sense as a typical IQ test... (~nil)
You would still need to define precisely what you mean by a closed-form solution and this definition needs to be part of the question.
But even then you would be faced with the difficult task of proving that your answer is correct.
This kind of ill-defined question might be a fun diversion but it should never be used for any serious purpose (e.g. in any test/assighnment that matters)
Note, that I said "reasonable people." Reasonable people know what is being asked. If, for example, I asked someone how much they weigh, they are not going to respond "I don't know. I weighed myself five minutes ago, but I must have a different weight right now."
Again, reasonable people. If we had to precisely define every question and interaction, we would never get anything done. Instead we rely on shared assumptions and clarify only when actual confusion occurs. (Yours is not an actual confusion.)
There's no reason to not allow arbitrary programs.
Moreover, even if we agree to use a certain form of closed expression, you will still need to define how we measure the size of such an expression and you will need to find a way to prove that an answer has the smallest possible expression size.
