Example of recurrence relation without closed form expression?

Question

Can give an example of a recurrence relation for which there does not exist a closed form expression?

score 2 · Answer 1 · answered Dec 07 '14 at 22:43

2

The quadratic recurrence relation $x_{n+1} = r x_n (1 - x_n)$ (iterating the logistic map) exhibits chaotic behavior for various values of $r$, which at least rules out any straightforward closed forms.

answered Dec 07 '14 at 22:43

Qiaochu Yuan

419,620

1

And of course there is the hailstone sequence (http://en.wikipedia.org/wiki/Collatz_conjecture), but I think the logistic map is a nicer example because it's defined by a polynomial, and hence shows that the theory of linear recurrences doesn't generalize in any straightforward way to polynomial recurrences of any higher degree. – Qiaochu Yuan Dec 07 '14 at 22:45

score 0 · Accepted Answer · answered Dec 07 '14 at 22:49

0

Let $p_1 = 2$ and let $p_i = \min\{x\in\mathbb{Z}\setminus\{1\} \;\colon p_j \nmid x \;\forall j\in [1,i-1] \}$ for $i \geq 2$.

answered Dec 07 '14 at 22:49

Mike Pierce

18,938

I believe that this answer is wrong. Qiaochu Yuan's answer is much better. – Mike Pierce Nov 13 '16 at 01:46

Example of recurrence relation without closed form expression?

2 Answers2