1
$\begingroup$

Any finite sequences can be expressed as a polynomial, but there are many infinite sequences for which we have found no closed form. Is it possible that no closed form exists? Are there sequences in which we've been able to PROVE no closed form exists?

$\endgroup$
1
  • $\begingroup$ Old question, I know, but Komolgorov complexity suggests that there must be, but we probably can't produce a constructive proof. $\endgroup$
    – Brian Tung
    Jan 27, 2017 at 19:36

2 Answers 2

5
$\begingroup$

There are infinite sequences without closed forms, for any reasonable definition of "closed form". There are only countably many closed form expressions and uncountably many sequences.

$\endgroup$
6
  • 1
    $\begingroup$ You are faster:) one comment, the right numbers are $2^c$ and $c$, because the coefficients can be real numbers ;) $\endgroup$
    – N. S.
    Oct 18, 2011 at 18:40
  • $\begingroup$ So there must exist sequences without closed form, that makes sense. Are there specific sequences that you know of where people have proved that that specific sequence has no closed form? $\endgroup$
    – Dan
    Oct 18, 2011 at 18:45
  • $\begingroup$ @Dan: you need to fix a definition of closed form... $\endgroup$ Oct 18, 2011 at 18:50
  • 4
    $\begingroup$ "Closed form" is a very slippery term. As soon as you give a specific example, someone may invent a new named function to give a "closed form" to that example. $\endgroup$ Oct 18, 2011 at 18:52
  • 1
    $\begingroup$ Actually, the cardinality of sequences of real numbers is just $c$. Any sequence of real numbers can be encoded in a single real number. If, for simplicity, we assume $0 \le x_n < 1$, let $w$ be the number in $[0,1]$ whose $({n}^{2}+2\,nm+{m}^{2}-3\,n-m+2)/2$'th decimal digit is the $n$'th decimal digit of $x_m$, for all positive integers $m$ and $n$. $\endgroup$ Oct 18, 2011 at 19:06
2
$\begingroup$

As has been noted, no answer can be given until you define "closed form". You might, however, be interested in the sequence of busy beaver numbers, which is known to grow faster than any computable function (and thus can't be given by any computable function). I'm sure some people would happily accept that as an example for which there is, provably, no closed form.

$\endgroup$
1
  • $\begingroup$ I am one of the people you talk about, so I happily accepted this answer. $\endgroup$ Oct 19, 2011 at 2:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .