Expressing recursive sequences explicitly

[Nathanael]

Take, for example, $x_{n+1}=x_n+2+4n\text{ with }x_0=0$. How would you express this explicitly in terms of n?

The only method I've thought of is to assume it's of the form $x_n=an^2+bn+c$ and then write out the first few terms $\{x_0=0,x_1=2,x_2=8\}$ to get a system of equations for the constants a,b,c:

$c=0$
$a+b+c=2$
$4a+2b+c=8$
$\Rightarrow x_n=2n^2$

Does anyone have another method?Suppose I have $x_{n+1}=x_n+2^n$. I can still find $x_n$ explicitly in the same way by assuming it's of the form $a2^n+b$

So, if I had something like $x_{n+1}=x_n+\sqrt{n}+n^{-\pi}$, should I then assume it's of the form $an^{3/2}+bn^{1-\pi}+c$ ?But now what about something with a nonlinear dependence on x_n, like $x_{n+1}=(n^2+n)x_n+1$ or maybe even $x_{n+1}=2^{x_n}+n$. Are there any general methods for solving these types of problems?

 

[S.G. Janssens]

You have brought up an interesting topic. It is field of active research with ties to numerous other fields of pure and applied mathematics, e.g. dynamical systems, number theory, orthogonal polynomials.

But now what about something with a nonlinear dependence on $x_n$, like $x_{n+1}=(n^2+n)x_n+1$

This is still linear in $x_n$. More precisely, it's a one-dimensional, linear non-homogeneous (because of the $1$ on the right) recurrence with non-constant (because of the $n^2 + n$ in front of $x_n$ ) coefficients.

Are there any general methods for solving these types of problems?

You may enjoy: S. Elaydi, An Introduction to Difference Equations, Springer, 3rd Edition, 2005. Incidentally, in general the answer is "no". For example, the famous logistic map $x \mapsto r x(1 - x)$ looks very simple, but may display so-called "chaotic" behavior, depending on the value of the parameter $r$.

 

[geoffrey159]

Try telescoping the terms : $x_n - x_0 = \sum_{k=0}^{n-1} (x_{k+1} - x_k)$