Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursive series for sum of 2 powers

  1. Jan 21, 2010 #1
    Has anyone seen this before? It must have been noted before!

    Let c = a+b and d = ab Then the series [tex] S_{n} = c*S_{n-1} - d*S_{n-2}[/tex] having the values 2 and c for [tex]S_0[/tex] and [tex]S_1[/tex] has the explicit formula
    [tex]S_{n} = a^{n} + b^{n}[/tex].


    The Explicit formula for the above recursive series is found by finding the roots e and f of the equation [tex]u^{2} - c*u + d = 0[/tex] and solving the set of equations:

    [tex] 2 = A + B[/tex] and
    [tex] c = Ae + Bf[/tex] from which we determine that
    [tex] S_{n} = Ae^{n} + Bf^{n}[/tex]

    We need to show that A = B = 1, e = a and f = b.

    Now e,f = (c +/- Sq root[(c)^{2} - 4ab])/2 = (a+b +/- (a-b))/2 = a,b

    Solving the set of equations we also see that A=B=1. Q.E.D.

    Most likely the proof could be done by induction also, but I wanted to focus on the general theory of recursive series.
    Last edited: Jan 21, 2010
  2. jcsd
  3. Jan 21, 2010 #2
    It can be done using the generating function for the sequence [tex]S_n[/tex]. It's defined as:

    S\left(x\right) = \sum_{n=0}^{\infty}S_{n}x^{-n}

    An explicit expression for [tex]S\left(x\right)[/tex] may be obtained from the recursion plus a few properties:

    S_0 = 2, S_1=c

    S_{n+2} = cS_{n+1}-dS_{n}

    From this, we have:

    x^{2}\left(S\left(x\right)-cx^{-1}-2\right)=cx\left(S\left(x\right)-2\right)-dS\left(x\right) \Leftrightarrow S\left(x\right)-cx^{-1}-2=cx^{-1}\left(S\left(x\right)-2\right)-dx^{-2}S\left(x\right)\Leftrightarrow S\left(x\right)\left(dx^{-2}-cx^{-1}+1\right)=-cx^{-1}+2 \Leftrightarrow

    Now, if [tex]c=a+b[/tex] and [tex]d = ab[/tex], then the denominator roots' are [tex]a[/tex] and [tex]b[/tex]; therefore [tex]S\left(x\right)[/tex] can be split as:

    S\left(x\right) = \frac{A}{1-ax^{-1}}+\frac{B}{1-bx^{-1}}

    Where [tex]A=\frac{2a-c}{a-b}[/tex] and [tex]B=\frac{2b-c}{b-a}[/tex]. Furthermore, the sequences corresponding to a factor with the form:


    Are [tex]c^n[/tex]. Therefore, the general form of your sequence is:

    S_n = \frac{2a-c}{a-b}\times a^n + \frac{2b-c}{b-a}\times b^n

    Now, from c=a+b and the initial terms, you may deduce the rest.
    Last edited: Jan 21, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook