6
$\begingroup$

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.

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

1 Answer 1

9
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ 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? $\endgroup$
    – Matt R.
    Jun 19, 2015 at 0:16
  • $\begingroup$ @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. $\endgroup$
    – Will Jagy
    Jun 19, 2015 at 1:34
  • $\begingroup$ That's certainly true, but I don't like pulling results out of thin air :D $\endgroup$
    – Matt R.
    Jun 19, 2015 at 1:49
  • $\begingroup$ @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. $\endgroup$
    – Will Jagy
    Jun 19, 2015 at 1:58
  • $\begingroup$ I will look into it myself some more, but thank you for your thoughts. $\endgroup$
    – Matt R.
    Jun 19, 2015 at 5:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .