Intereting Posts

an example for $\pi$-quasinormal subgroup but is not normal
Roots of a polynomial
Calculate which day of the week a date falls in using modular arithmetic
Is bijection mapping connected sets to connected homeomorphism?
Without the Axiom of Choice, does every infinite field contain a countably infinite subfield?
Prove that a group of order 30 has at least three different normal subgroups
Finding the all roots of a polynomial by using Newton-Raphson method.
discrete math>Recurrence relation>how find the general function of $a(n)=2a(n-1)+n^2$
On a certain morphism of schemes from affine space to projective space.
Khan academy for abstract algebra
Find an infinite set of positive integers such that the sum of any two distinct elements has an even number of distinct prime factors
Are all projection maps in a categorical product epic?
If $A\subset\mathbb{R^2}$ is countable, is $\mathbb{R^2}\setminus A$ path connected?
What is the reasoning behind why the ratio test works?
Fourier transform of unit step?

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$

- Number of ways of walking up $6$ steps taking $1, 2,$ or $3$ at a time, and a recurrence relation
- What is the recurrence relation in this problem?
- Newton's method for square roots 'jumps' through the continued fraction convergents
- Solving a recurrence by using characteristic equation method
- Recurrence for random walk
- Solving the recurrence relation $T(n)=2T(n/4)+\sqrt{n}$

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

- Question about generating function in an article
- recurrence relation concrete way to solve it
- Prove that $\displaystyle\int_{x=-1}^{1}P_L(x)P_{L-1}\acute (x)\,\mathrm{d}x=\int_{x=-1}^{1}P_L\acute(x)P_{L+1} (x)\,\mathrm{d}x=0$
- Explicit formula for Bernoulli numbers by using only the recurrence relation
- Prove the following (algebra of polynomials)
- What is the solution to the following recurrence relation with square root: $T(n)=T (\sqrt{n}) + 1$?
- Solving a recursion relation: $a_{n+1}=-3a_n+4a_{n-1}+2$
- Number of ways of walking up $6$ steps taking $1, 2,$ or $3$ at a time, and a recurrence relation
- Intuitive explanation for Derangement
- General formula of Fibonacci look alike series

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?

- Number Of races needed?
- If I flip a coin 1000 times in a row and it lands on heads all 1000 times, what is the probability that it's an unfair coin?
- The preimage of a maximal ideal is maximal
- Convergence of Riemann Zeta Function for Normed Arguments
- An awful identity
- $f$ is irreducible $\iff$ $G$ act transitively on the roots
- Proof that $\sum\limits_{j,k=1}^N\frac{a_ja_k}{j+k}\ge0$
- If a group is the union of two subgroups, is one subgroup the group itself?
- Erf squared approximation
- Is the image of a Borel subset of $$ under a differentiable map still a Borel set?
- Approaching a contour integral with singularities on each axis
- Peano arithmetic with the second-order induction axiom
- Limit comparison test proof
- Prove that $f(z)=\frac{1}{2\pi}\int_0^{2\pi} f(Re^{i\phi})Re(\frac{Re^{i\phi}+z}{Re^{i\phi}-z}) d\phi$
- Showing $\int_{0}^{\infty} \frac{\sin{x}}{x} \ dx = \frac{\pi}{2}$ using complex integration