[seqfan] Re: linear recurrence multiples

[Richard J. Mathar]

dg> Date: Sat, 20 Jul 2019 00:34:14 +0200
dg> From: Dale Gerdemann <dale.gerdemann at gmail.com>
dg> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
dg> Subject: [seqfan] linear recurrence multiples
dg> 
dg> I have a question concerning recurrences of the form a(0)=0, a(1)=1,a(n) =
dg> b*a(n-1)+c*a(n-2). When (b,c) is (3,2), for example, we have A007482 and
dg> when (b,c)=(2,3), we have A015518. For A007482, it seems to be possible to
dg> find formulae for m*a(n) for any m. For example, if m=4, we have 4*a(n) =
dg> a(n+1)+a(n-1)+2*a(n-2). For A015518,  however, it seems that no such
dg> formulae can be found. It appears that such formulae can be found just in
dg> case b >= c. Is this correct?

The formula
 4*a(n) = a(n+1)+a(n-1)+2*a(n-2)
is usually rewritten in normalized form by fixing the largest index to be n:
 4*a(n-1) = a(n)+a(n-2)+2*a(n-3)
and that reads in the OEIS "signature" form, where a(n) on the left hand side
and the smaller indices on the right hand side

 a(n) = 4*a(n-1)-a(n-2)-2*a(n-3).
Considering the denominator 1-4*x+x^2-2*x^3 in the associated rational
g.f., we observe the factorization
 1/(1-4*x+x^2-2*x^3) = 1/[(1-x)*(1-3*x-2*x^2)]
so the recurrence of the "original" g.f. 1/(1-3*x-2*x^2) in A007482
has been "lifted" by multiplying the g.f. with (1-x):

  (1-x)/[(1-x)*(1-3*x-2*x^2)] = (1-x)/(1-4*x+x^2-2*x^3) .

So the mechanism at work means that the coefficient "3" in the reccurnce
of A007482 was "boosted" to m=4 by multiplication with (1-x).
So that gives the "recipe" to construct a recurence for m*a(n) by
considering the "leading" factor "b" and multiplying the generating
function by (1-(m-b)*x)/(1-(m-b)*x) for the desired final format.

The example for A015518 and m=4 needs (1-2*x) to move b=2 to m=4::

x/(1-2x-3*x^2) = (1-2*x)*x/[(1-2*x)*(1-2*x-3*x^2)] = (1-2*x)*x/(1-4*x+x^2+6*x^3):
a(n) = 4*a(n-1)-a(n-2)-6*a(n-3) ;
a(n+1) = 4*a(n)-a(n-1)-6*a(n-2) ;
4*a(n) = a(n+1)+a(n-1)+6*a(n-2).