FW: A101368

[Ralf Stephan]

> As an example, I will prove that for n>2,
> a(n) = 5a(n-1)-a(n-2)-1.     (*)

1. There is the thumb rule that any constant in a pure recursion
adds the factor (1-x) to the GF.
2. Again, GFs and pure recursion can always be read off from each other:

a(n) = Ca(n-1) + Da(n-2) + Ea(n-3)  <==> GF: (polynomial)/(1-Cx-Dx^2-Ex^3)

(I will go on mentioning this until you all are dreaming about it ;-)

So the above (*) has GF: P/[(1-x)(1-5x+x^2)]) = P/(1-6x+6x^2-x^3) which is
a(n) = 6a(n-1) - 6a(n-2) + a(n-3)      (**)

1+2 also means that ANY constant in (*) will give the recursion in (**),
just with different start values.


ralf