Solve a Quadratic map

Question

I read this on Wolfram Alpha. It states that: a quadratic recurrence relation uses a second degree polynomial to express $x_{n+1}$ as a function of $x_n$. A "quadratic map", then, is a recurrence relation: $$S_{n+1} = a S_n^2 + b S_n + c$$ My question is if, $$S_0=d$$ what is$$\sum_{i=1}^nS_i-S_{i-1}=?$$ I was wondering is there a closed form for this? How to solve this? I have been trying z-transform and method of undetermined coefficients, but no progress.

Answer 1

If you begin with $S_{n+1} = a S_n^2 + b S_n + c,$ define $T_n$ so that $$ S_n = \frac{1}{a} \left( T_n - \frac{b}{2} \right), $$ $$ T_n = a S_n + \frac{b}{2}. $$ The outcome is that $$ T_{n+1} = T_n^2 + \left( \frac{b}{2} + ac - \frac{b^2}{4} \right). $$

You can absorb your coefficient $a$ into the variable by a multiplication ($\sqrt a$ somewhere) and eliminate $b$ by a translation. When done, you have $x_{n+1} = x_n^2 + c.$ These have predictable behavior as far as size.

however, there are only two cases that can be solved in closed form: if $$\color{green}{y_{n+1} = y_n^2 ,}$$ then $$\color{green}{ y_n = y_0^{\left( 2^n \right)}}. $$

If $\color{magenta}{x_0 > 2}$ and $$\color{magenta}{x_{n+1} = x_n^2 -2 ,}$$ then $$ \color{magenta}{x_n = A^{\left( 2^n \right)} + B^{\left( 2^n \right)},} $$ with $$ \color{magenta}{ A = \frac{x_0 + \sqrt{x_0^2 - 4}}{2},} $$ $$ \color{magenta}{ B = \frac{x_0 - \sqrt{x_0^2 - 4}}{2}.} $$ Note that $\color{magenta}{A+B = x_0}$ and $\color{magenta}{AB = 1.}$

For any other value of the constant $c,$ one can find and approximate value for the larger $A,$ just take logarithm of the recurrence, but no explicit formula. The case with $c=-2$ comes under the heading of Lucas Sequences, and is instrumental in the Lucas-Lehmer primality test.