[seqfan] Re: linear recurrence multiples

[Fred Lunnon]

  PROPOSITION:  Given some arbitrary integer  m , together with some
linear recurrence of order  r  with integer coefficients: then there
exists an integer linear recurrence of order  2 r  generating the same
sequences, with central coefficient equal to  m .

  Sketch proof:
The initial recurrence acting on sequence  S(n) ,

    a_0 S(n) + a_1 S(n+1) + ... + a_r S(n+r)  =  0 ,

may be rewritten in "umbral" notation in the form  P(E) S_n = 0 ,
where polynomial

    P(E)  =  a_0 + a_1 E + ... + a_r E^r ,

and  E  (uppercase epsilon) traditionally denotes the shift operator
defined by  E S(n) = S(n+1) .

  LEMMA:  Given  P(E)  generating  S(n) , and  Q(E)  some arbitrary
integer polynomial: then their polynomial product  P(E) Q(E)  also
generates  S(n) .

  Now suppose

    Q(E)  =  b_0 + b_1 E + ... + b_r E^r ,

so that the central term of  P(E) Q(E)  is

    c_r E^r  =  ( a_r b_0 + ... a_(r-j) b_j + ... + a_0 b_r ) E^r .

Since  P(E)  denotes an integer recurrence, it can be assumed that
GCD(a_0, ...,a_r) = 1 ; indeed, if  S(n)  is an integer sequence we
can set  a_r = -1 .  Therefore by the "chinese remainder theorem",
equation  c_r = m  in unknowns  b_0, ...,b_r  has a solution
in integers (which can furthermore be calculated efficiently).  QED.

  I'll leave the matter at that for now, as it remains unclear to me
whether your notion of "formula" encompasses extra constraints which
you have yet to articulate.

Fred Lunnon


On 7/21/19, Dale Gerdemann <dale.gerdemann at gmail.com> wrote:
> Sorry: In my last post, I accidentally reversed b and c. If the recurrence
> is defined by a(0)=0, a(1)=1, a(n) = b*a(n-1) + c*a(n-2), then as long as c
> <= b, formulae for m*a(n) can be generated using the method I described.
>
> El El dom, 21 jul 2019 a las 2:25, Dale Gerdemann <dale.gerdemann at gmail.com>
> escribió:
>
>> In the formula a(n) = b*a(n-1) + c*a(n-2), b and c are intended to be
>> integers. For example if (b,c) = (1,1) you have the Fibonacci sequence and
>>  here you can find a nice formula  for each positive integer m:
>>
>> m=2:  2*a(n) = a(n+1) + a(n-2)
>>
>> m=3: 3*a(n) =  a(n+2) + a(n-2)
>>
>> m=4: 4*a(n) = a(n+2) + a(n) + a(n-2)
>>
>> m=5:  5*a(n) =  a(n+3) + a(n-1) + a(n-4)
>>
>> The interesting thing about these formulae is the relation to golden ratio
>> base.  If t is the golden ratio, (1+sqrt(5))/2, then:
>>
>> 2 = t^1 + t^{-2}
>>
>> 3 = t^2 + t^{-2}
>>
>> 4 = t^2 + t^0 +t^{-2}
>>
>> 5 = t^3 + t^{-1} + t^{-4}
>>
>> I experimented with finding simular formulae for other recurrences, i.e.
>> for other values of b and  c.  The easiest way to do this is to pick a
>> large value for  n, such as n=100. Then find a greedy sum for m*a(100)
>> such
>> as 2*a(100) = a(101) + a(98). Then generalize this to 2*a(n) = a(n+1) +
>> a(n-2). Finally, to be sure that the generalized formulae is correct, it
>> needs to be checked with some values other than  n=100. Now my
>> experimentation seems to show that this method yields valid formulae for
>> recurrences defined with  b <= c, but  the generalized formulae are never
>> valid when c > b. So what is going on here?
>>
>> El El dom, 21 jul 2019 a las 0:32, Fred Lunnon <fred.lunnon at gmail.com>
>> escribió:
>>
>>>   I'm afraid it is unclear to me what is meant by "formula" in this
>>> context.
>>> For example, does it mean "linear recurrence with integer coefficients,
>>> such that at least one (or exactly one) coefficient equals  m " ?
>>>
>>>   In that case the question would reduce to consideration of polynomial
>>> multiples of a polynomial in a single variable.
>>>
>>> WFL
>>>
>>>
>>>
>>> On 7/19/19, Dale Gerdemann <dale.gerdemann at gmail.com> wrote:
>>> > I have a question concerning recurrences of the form a(0)=0,
>>> a(1)=1,a(n) =
>>> > b*a(n-1)+c*a(n-2). When (b,c) is (3,2), for example, we have A007482
>>> > and
>>> > when (b,c)=(2,3), we have A015518. For A007482, it seems to be possible
>>> to
>>> > find formulae for m*a(n) for any m. For example, if m=4, we have 4*a(n)
>>> =
>>> > a(n+1)+a(n-1)+2*a(n-2). For A015518,  however, it seems that no such
>>> > formulae can be found. It appears that such formulae can be found just
>>> in
>>> > case b >= c. Is this correct?
>>> >
>>> > --
>>> > Seqfan Mailing list - http://list.seqfan.eu/
>>> >
>>>
>>> --
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>
>>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>