Recursive series for sum of 2 powers

[ramsey2879]

Has anyone seen this before? It must have been noted before!

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

Proof

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

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

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.

 

[JSuarez]

It can be done using the generating function for the sequence S_n. It's defined as:

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

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

<br /> S_0 = 2, S_1=c<br /> <br /> S_{n+2} = cS_{n+1}-dS_{n}<br />

From this, we have:

<br /> 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<br /> S\left(x\right)=\frac{-cx^{-1}+2}{dx^{-2}-cx^{-1}+1}=x\frac{2x-c}{d-cx+x^{2}}<br />

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

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

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

<br /> \frac{1}{1-cx^{-1}}<br />

Are c^n. Therefore, the general form of your sequence is:

<br /> S_n = \frac{2a-c}{a-b}\times a^n + \frac{2b-c}{b-a}\times b^n<br />

Now, from c=a+b and the initial terms, you may deduce the rest.