Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have been working with a function that I defined recursively as $$a(n) = (1-a(n-1)^k)^k$$ where $a(0) = x$ and $k$ is an integer $>1$. So really, $a(n)$ returns a function on $x$ and $k$.

I have just stumbled upon the term "recurrence relation" and have been reading up on it and trying some things out. It would be so helpful if I could rewrite $a(n)$ as just a function of $n$, $k$, and $x$ and leave out the recursion. It had never occurred to me before that I could do that.

However, I'm not sure that the recursion relation methods I am reading about apply here, as I don't seem to have coefficients and my function doesn't seem to map to any of the examples I read. I found the RSolve method in Mathematica. It works for $a[n] = a[n-1]^k$, but as soon as I throw in the $ 1- $ part, it doesn't return anything (it just spits back the input).

Before spending a week trying to learn about recurrence relations, can anyone tell me if my equation fits under this umbrella? Or does the way it's written automatically exclude it from the techniques used. Is there another approach I should look into?

share|cite|improve this question
This seems to be a typical recurrence relation. Concrete Mathematics has a good chapter about it, if you are interested. – FUZxxl Oct 6 '11 at 21:29
Definitely a recurrence relation. For some types of recurrence relation, there are standard methods for finding a closed form expression for what you call $a(n)$. That's what you are looking for. For all too many recurrence relations, there is no pleasant closed form for $a(n)$. Your recurrence certainly does not fit trivially into a standard type. – André Nicolas Oct 6 '11 at 21:38
I very much doubt that the general solution of your recurrence can be written in closed form, even for $k=2$. There are of course some special solutions, e.g. alternating 0 and 1. – Robert Israel Oct 6 '11 at 21:44
I doubt you will find a closed form solution to this particular expression. I can see three cases for the limit depending on $k$ and $x$: fixed points, alternating between close to 0 and close to 1, and diverging. – Henry Oct 6 '11 at 21:45
What about if we put $a_n=b_n^k$? – André Nicolas Oct 7 '11 at 0:37
up vote 1 down vote accepted

Linear recurrences have closed formulas and a nice explanation due to linear algebra.

Non-linear recurrences are much harder and in general have no closed formulas.

Even the simple quadratic recurrence $a(n)=a(n-1)^2+c$ does not have a closed formula in general. Moreover, it exhibits chaotic behavior! In the complex plane this recurrence gives rises to wonderful fractals. The Mandelbrot set is a geometric "explanation" for the behavior of these recurrences as a function of $c$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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