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

Wed Mar 6 16:22:45 CET 2013

Thank you very much, Richard, for interesting papers, and Andy for formula for R(N)! In fact, I did the same strong conjecture and even sent it to Sequence Fanatics Discussion list but after your proof I cancelled from this posting.
Note only that R(2)=1(not 3)
Indeed, as I proved ealier (see my message to Sequence Fanatics Discussion list from Feb 28 2013), if
a(0)=b,a(1)=c, for n>=2, a(n)=N*a(n-1)+M*a(n-2).               
Then for n>=1,
g(n)= a^2(n) - a(n-1)*a(n+1) = (-M)^(n-1)*(c^2-N*b*c-M*b^2).
So g(n) = C*(-M)^(n-1)=-M*g(n-1).

... Nowever the general problem for g(n) still waits for its solution!

Best regards,
Vladimir

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

> 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/
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
> 

 Shevelev Vladimir‎