4
$\begingroup$

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?

  • 1
    This seems to be a typical recurrence relation. *Concrete Mathematics* has a good chapter about it, if you are interested.2011-10-06
  • 7
    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.2011-10-06
  • 3
    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.2011-10-06
  • 4
    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.2011-10-06
  • 0
    What about if we put $a_n=b_n^k$?2011-10-07

1 Answers 1

1

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$.