1
$\begingroup$

I'm looking for an example of a recurrence relation where it provably does not have a closed form.

Does such a thing exist?

For example, I believe $S(n, k)$, or the Stirling numbers of the second type, do not have a closed form -- but I'm not sure if they don't or if they can't.

$\endgroup$
1
  • 6
    $\begingroup$ Because there are sequences with no closed form, there are a fortiori recurrence relations with no closed form. Let $a_0=0$ and $a_n=a_{n-1}$ plus the number of solutions to the $n$th entry on some complete list of diophantine equations. Or do you mean to require a "closed form" for $a_{n+1}-a_n$? What counts as a recurrence relation? And what counts as a closed form? $\endgroup$ Nov 14, 2013 at 5:51

1 Answer 1

8
$\begingroup$

I'm sure you're aware that linear recurrent sequences are well understood and can be solved exactly by a "closed formula". Once you enter the world of non-linear recurrences, even when restricting to constant coefficients, you can get all sorts of strange behavior even with some very simple looking recurrences. One example is the logistic map: $$x_{n+1}=rx_n(1-x_n)$$ which is only exactly solvable for a few special values of the constant $r$. For the complex and chaotic behavior that happens with other values of $r$ you can check the wiki article, which has a nice bifurcation diagram and summary of the qualitative properties of this map.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.