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?

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