[seqfan] Re: Cassini transformation of linear recursion of order 3

[Andrew N W Hone]

Dear Vladimir, 

>From the argument I gave before, and from the explicit form of g_n, I think it is straightforward to check that R(N) is just the 
sequence of triangular numbers 

R(N) = N(N-1)/2 

for all N greater than or equal to 3. (However, R(2) =3.) I just did some numerical experiments and verfiied this for N=3,4,5,6,7. 

To prove it, write a_n = \sum_j C_j  x_j^n, so that 

g_n =  \sum_{j,k} C_j C_k ( (x_j x_k)^n - x_j^{n+1} x_k^{n-1}). 

Now observe that the terms with j=k cancel from the above sum, so it can be rewritten as 

g_n = \sum_{j<k} C_j C_k ( 2 - x_j / x_k - x_k /x_j ) (x_j x_k)^n  

and there are precisely N(N-1)/2 distinct exponential terms in this sum, which implies that 
g_n satisfies a linear relation of order R(N) =N(N-1)/2. 

(Note that we are assuming this is a "generic" recurrence with N distinct characteristic roots x_j. The argument could be modified 
to cover the non-generic case, but it might happen that R(N) < N(N-1)/2 for some very special cases; I would have to think about this 
a bit more.)

As for exactly what recurrence R(N) satisfies, I think it might be possible to do something using the Dodgson condensation method 
for determinants, In fact, I think another way to prove the above result (which would work in a more general setting) would be to write 
the linear recurrence as a first order matrix relation and use determinantal identities and/or the Cayley-Hamilton theorem.  

Best wishes,
Andy  
________________________________________
From: SeqFan [seqfan-bounces at list.seqfan.eu] on behalf of Vladimir Shevelev [shevelev at bgu.ac.il]
Sent: 05 March 2013 19:49
To: Sequence Fanatics Discussion list
Subject: [seqfan] Re: Cassini transformation of linear recursion of order 3

Thank you, Andy!

I understand that there are general results, but my concrete aim is to find a linear recurrence of order R(N) with constant coefficients for g=a^2(n)-a(n-1)*a(n+1), if a(n) satisfies a linear  recursion of order  N with constant coefficients. Thus my result yields that R(3)=3. I think that even function R(N) is unknown and it is, in my opinion,  an important conctete open problem.  As a continuation of this topic, I proved that R(4)=6. For example, for tetranacci numbers (A000078)  a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) with a(0)=a(1)=a(2)=0, a(3)=1, g(n) satisfies a  recursion
g(n) = -g(n-1) - 2*g(n-2) - 2*g(n-3) + 2*g(n-4) - g(n-5) + g(n-6).
I am sure that a concrete recursion for g(n) if a(n) satisfies a linear recursion of order N with constant coefficients is a very interesting and difficult problem. Namely in this sense I asked what results are known, beginning with my one for N=3.

Best regards,
Vladimir

----- Original Message -----
From: Andrew N W Hone <A.N.W.Hone at kent.ac.uk>
Date: Tuesday, March 5, 2013 2:01
Subject: [seqfan] Re: Cassini transformation of linear recursion of order 3
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>

> Dear Vladimir,
>
> I don't know to what extent this is "known" but such
> transformations involving polynomial
> functions of the terms of a linear recurrence have nice
> properties.
>
> For instance, if the sequence (a_n) satisfies a linear
> recurrence of order N with constant coefficients, then
>
> g_n = P(a_n, a_{n+1}, ... , a_{n+k-1})
>
> also satisfies a linear recurrence with constant coefficients,
> for any polynomial P in k variables (where w.l.o.g.
> we can assume that k is at most N). With a bit of work one could
> also get an upper bound on
> the order of the recurrence for (g_n).
>
> One can easily prove this for sequences defined over the complex
> numbers, since (generically) one
> can write the terms of the first sequence as a sum
>
> a_n = \sum_j   C_j x_j^n
>
> over the roots x_j of the characteristic polynomial of the
> recurrence for a_n, and then from the polynomial
> P one has an expression of the form
>
> g_n = \sum_k D_k y_k^n,
>
> where the y_k are formed from certain products of x_j. Then g_n
> satisfies
>
> F(S) g_n = 0
>
> where F(S) = \prod _k (S-y_k) and S is the shift operator
> (sending n -> n+1).
>
> With a bit more work one could come up with a more general proof
> that would work
> with recurrences defined over any field, or over a ring.
>
> Your particular choice of g_n is very nice: it is a 2 x 2
> determinant (a discrete Wronskian, or Casorati
> determinant).
>
> Best wishes,
> Andy
>
> ________________________________________
> From: SeqFan [seqfan-bounces at list.seqfan.eu] on behalf of
> Vladimir Shevelev [shevelev at bgu.ac.il]
> Sent: 05 March 2013 03:21
> To: seqfan at list.seqfan.eu
> Subject: [seqfan] Cassini transformation of linear recursion of
> order 3
>
> Dear SeqFans,
>
> I proved the following:
> If a(n+3)=L*a(n+2)+M*a(n+1)+N*a(n), n>=0, a(0)=b, a(1)=c, a(2)=d
> and for n>=1, g=a^2(n)-a(n-1)*a(n+1),
> then g(n+3)=-M*g(n+2)-L*N*g(n+1)+N^2*g(n).
> This identity we call the Cassini transformation of linear
> recursion of order 3.
> In case |g(n)|<=|a(n)|, this allows, using  telesopic
> summation, to obtain a fast convergent series for
> lim(a(n+1)/a(n)) as n goes to infinity. Could anyone say whether
> such a transformation of linear recursion of order 3 is known?
>
> Best regards,
> Vladimir
>
>  Shevelev Vladimir‎
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>

 Shevelev Vladimir‎

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/