Matrix Representation of Second Degree Linear Recurrence Equations

Question

I can calculate the Matrix representation of first degree Linear recurrence equations. And I calculate for higher order by using fast matrix exponentiation. I learnt this from this tutorial http://fusharblog.com/solving-linear-recurrence-for-programming-contest/

But I am facing problem in calculating the matrix representation of Second Degree Linear recurrence equations. For example -

S(n) = a * (S(n - 1))^2 + b * S(n - 1) + c
where S(0) = d

Can you help me to figure out the matrix representation of the above equation or give me some insights? Thanks in advance.

Answer 1

This is polynomial of second degree. The well-known recurrence

 x_(n+1) = (x_n)^2 + c

that is often called the quadratic map is not in general solvable in closed form. Quadratic iteration

x_(n+1) = a (x_n)^2 + b x_n + c

is iteration of the Mandelbrot fractals. This is the real version of the complex map defining the Mandelbrot set.