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.

• Isn't this just $S_n - S_1$?
– Guy
Mar 8, 2014 at 17:25
• @Sabyasachi: Yes but how do you propose to get $S_n$ without computing $S_{n-1}$? Mar 8, 2014 at 18:47
• I have no idea. Before this it was $x_n$ in the first equation and I might have misinterpreted.
– Guy
Mar 8, 2014 at 18:50

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.

• I've been trying to show the result you gave in pink, but I think it requires methods I'm unfamiliar with. Could you point me to a resource? Jun 19, 2015 at 0:16
• @MattR., once you know the result in this form, proof is just induction on $n.$ $AB=1,$ and any $A^k B^k = 1.$ Some background material is at en.wikipedia.org/wiki/Lucas_sequence but is not needed for this proof. Jun 19, 2015 at 1:34
• That's certainly true, but I don't like pulling results out of thin air :D Jun 19, 2015 at 1:49
• @MattR., I had answered with these results several times over the years, and will not be able to find the first question that got me looking into this. I think the pink fact above is equivalent to the line in the table en.wikipedia.org/wiki/Lucas_sequence#Other_relations that says $$V_{2n} = V_n^2 - 2 Q^n$$ but, as I say, it has been a long time. Jun 19, 2015 at 1:58
• I will look into it myself some more, but thank you for your thoughts. Jun 19, 2015 at 5:53