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:

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

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

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

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:

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

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

$$\frac{1}{1-cx^{-1}}$$

Are $$c^n$$. 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.