Pell numbers

[Max]

Creighton Dement wrote:

> The conversation had to do with sequences of the form 
> c(2n) = a(n), c(2n+1) = a(n) (or c(2n+1) = -a(n)) and that, apparently,
> such sequences may often be used in relating two or more sequences. See,
> for ex. my comment for A061547 or A100434 (this case is very similar to
> the one at hand as it also involves Pell numbers) .
> 
> Define: (a(n)) =  (0, -1, -1, -8, -8, -49, -49, -288, -288, -1681,)
> http://www.research.att.com/projects/OEIS?Anum=A001108
> a(n)-th triangular number is a square: a(n+1) = 6*a(n)-a(n-1)+2.

The generating function for A001108 is
GA(x) = (x+x^2)/((1-6*x+x^2)*(1-x))
So the generating function for the derived sequence (a(n)) is
A(x) = -(GA(x^2)/x + GA(x^2)) = -GA(x^2) * (1+x)/x
= -(x^2+x^4)/((1-6*x^2+x^4)*(1-x^2)) * (1+x)/x
= -(x+x^3)/((-1-2*x+x^2)(-1+2*x+x^2)*(1-x))

> Define (b(n)) =  (0, 0, 3, 3, 20, 20, 119, 119, 696, 696, 4059, 4059,)
>  http://www.research.att.com/projects/OEIS?Anum=A001652
> a(n)=6a(n-1)-a(n-2)+2 with a(0) = 0, a(1) = 3.

The generating function for A001652 is
GB(x) = (3*x-x^2)/((1-6*x+x^2)*(1-x))
So the generating function for the derived sequence (b(n)) is
B(x) = GB(x^2) + GB(x^2)*x = GB(x^2) * (1+x)
= (3*x^2-x^4)/((1-6*x^2+x^4)*(1-x^2)) * (1+x)
= (3*x^2-x^4)/((-1-2*x+x^2)(-1+2*x+x^2)*(1-x))

> Conjecture: a(n) + b(n) = ((-1)^n)*A000129(n)

The generating function for a(n)+b(n) is
AB(x) = A(x) + B(x)
= (-x+3*x^2-x^3-x^4)/((-1-2*x+x^2)(-1+2*x+x^2)*(1-x))
= x/(-1-2*x+x^2)
and the generating function for (-1)^n*(a(n)+b(n)) is
AB(-x) = x/(1-2*x-x^2)
which coincides with the generating function for A000129(n).
Since the initial values for (-1)^n*(a(n)+b(n)) and A000129(n) are equal we conclude that
(-1)^n*(a(n)+b(n)) = A000129(n).

> I know this is an abstract question, but does anyone see a reason
> (geometric or otherwise) why these sequences choose to "double up on
> themselves" ?

One of important reasons is that substitution x -> x^2 makes the polynomial (1-6*x+x^2) reducible over Z.

Max