Intereting Posts

Fluids Euler's Equation
Determine whether $f_n(x)=\frac{x^n}{\sqrt{3n}}$ for $x \in $ is uniformly convergent
Every Real number is expressible in terms of differences of two transcendentals
How to count different card combinations with isomorphism?
What is the right way to define a function?
What is the probability that GCD of $(a,b)$ is $b$?
Solve $\tan\left(\arccos\left(\frac{-\sqrt{2}}{2}\right)\right)$ without calculator
How to simplify a square root
How to solve an nth degree polynomial equation
Math Textbooks for High School
Show that $1^k+2^k+…+n^k$ is $O (n^{k+1})$.
Possibly not an acceptable proof for uncountablity of countable product of countable sets
Isomorphic rings or not?
How to conceptualize unintuitive topology?
Why is $1 – \frac{1}{1 – \frac{1}{1 – \ldots}}$ not real?

I came across a non-linear recurrence relation I want to solve, and most of the places I look for help will say things like “it’s hopeless to solve non-linear recurrence relations in general.” Is there a rigorous reason or an illustrative example as to why this is the case? It would seem to me that the correct response would be “we just don’t know how to solve them,” or “there is no solution using elementary functions,” but there might be a solution in the form of, say, an infinite product or a power series or something.

Just for completion, the recurrence relation I’m looking at is (slightly more than just non-linear, and this is a simplified version):

$p_n = a_n b_n\\ a_n = a_{n-1} + c \\ b_n = b_{n-1} + d$

- Mirror algorithm for computing $\pi$ and $e$ - does it hint on some connection between them?
- $T(n) = 4T({n/2}) + \theta(n\log{n})$ using Master Theorem
- What is the most elementary way of proving a sequence is free of non-trivial squares?
- Sequences of sums of Pascal's triangle
- Question about generating function in an article
- This one weird thing that bugs me about summation and the like

And $a_0 > 0, b_0 > 0, c,d$ fixed constants

- Inductive proof of the closed formula for the Fibonacci sequence
- How much weight is on each person in a human pyramid?
- Chain rule for discrete/finite calculus
- Is there any explicit formula for $x_n$?
- $T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer
- Recurrence relation rabbit population
- How prove this nice limit $\lim\limits_{n\to\infty}\frac{a_{n}}{n}=\frac{12}{\log{432}}$
- Explicit formula for Bernoulli numbers by using only the recurrence relation
- For $x_{n+1}=x_n^2-2$, show $\lim_{n\to\infty}\frac{x_n}{x_0x_1\cdots x_{n-1}}=2$
- Find a Recurrence Relation

Although it is possible to solve selected non-linear recurrence relations if you happen to be lucky, in general all sorts of peculiar and difficult-to-characterize things can happen.

One example is found in *chaotic systems*. These are hypersensitive to initial conditions, meaning that the behavior after many iterations is extremely sensitive to tiny variations in the initial conditions, and thus any formula expressing the relationship will grow impossibly large. These recurrence equations can be amazingly simple, with *x _{n+1}* = 4

User @Did has already given the Mandelbrot set example–similarly simple to express, and similarly difficult to characterize analytically (e.g. by giving a finite closed-form solution).

Finally, note that to solve *every* non-linear recurrence relation would imply that one could solve the Halting problem, since one could encode a program as initial states and the workings of the Turing machine as the recurrence relations. So it is certainly hopeless in the most general case. (Which highly restricted cases admit solutions is still an interesting question.)

A rather well-known example is the Mandelbrot set. Consider a sequence $(a_n)$ defined by $a_0=0$ and $a_{n+1}=a_n^2+c$, for some given parameter $c$, and ask the seemingly innocuous question:

For which values of $c$ is the sequence $(a_n)$ bounded?

One may note that the recursion is simply quadratic rather than affine (the degree of $a_n$ in the formula for $a_{n+1}$ is 2 instead of 1). The answer, or rather, some elements of the answer, have opened an entire mathematical field.

But polynomial recurrence can be mapped to linear recurrences. For example for

$a_{n+1} = a_n^2 + c$ let $b_{m,n} =a_n^m$. Then by the binomial formula:

$$b_{m,n} = (a_{n-1}^2+c)^m = \sum_{j = 0}^mc^{m-j}{m \choose j}a_{n-1}^{2j} =

\sum_{j = 0}^mc^{m-j}{m\choose j}b_{2j,n-1}$$

and even though it’s a two variable linear recurrence you can use a lot of the same types of strategies to solve it as if it was one variable (indeed for any number of variables you can use the same approaches as if it were one variable).

So what’s the big deal?

- Proof related to breadth first search
- If $\omega$-chains corresponds to maximality, then $\kappa$-chains corresponds to ???
- What is wrong with this proof that there are no odd perfect numbers?
- Closed-form of $\int_0^1\left(\frac{\arctan x}{x}\right)^n\,dx$
- $AB$ is a chord of a circle $C$. Let there be another point $P$ on the circumference of the circle, optimize $PA.PB$ and $PA+PB$
- analytic solution to definte integral
- Why is $5^{n+1}+2\cdot 3^n+1$ a multiple of $8$ for every natural number $n$?
- Question on a set of subsequential limits
- Show $f$ is primitive recursive, where $f(n) = 1$ if the decimal expansion of $\pi$ contains $n$ consecutive $5$'s
- Homogeneous riemannian manifolds are complete. Trouble understanding proof.
- Deriving the sub-differential of the nuclear norm
- Categorial definition of subsets
- Exact sequences of $SU(N)$ and $SO(N)$
- Factorial of a matrix: what could be the use of it?
- Example of a not recursively enumerable set $A \subseteq \mathbb{N}$