[seqfan] Re: linear recurrence multiples

[Fred Lunnon]

  On reflection, the chinese remainder theorem has nothing to do with it!
The point is rather that there are in general an awful lot of solutions
to the equation  c_r = m , many of which are not very interesting:
for instance, when  a_r = -1  we can always just choose  Q(E) = -m .
Even insisting that (say)  GCD(b_0, ...,b_r) = 1 , or similarly for
P Q , is not going to improve this situation a great deal.

  So as I (and other respondents) have already made clear, the extra
constraints implicit in the notion of a "formula" need to be made
explicit before further progress with your enquiry can be made!

WFL



On 7/21/19, M. F. Hasler <seqfan at hasler.fr> wrote:
> On Sun, Jul 21, 2019, 06:59 Dale Gerdemann  wrote:
>> 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.
>
>
> I don't agree: a check isn't a proof (*), but it is easy to prove such
> formulae rigorously by using the explicit expression for a(n).
> (Google "second order linear recurrent sequence with constant coefficients"
> to get all details.)
>
> (* it may be sufficient to make  n "linearly independent" checks if you
> test for an n dimensional subspace (loosely speaking), yet you have to
> prove that you are in that setting and in particular that you made at least
> n  "independent" checks)
>
> 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?
>>
>
> Could it be that this distinction is rather based on the sign of the
> discriminant b²–4c ? The general theory explains the fundamental solutions
> in the respective cases, which could in turn explain why & when a given
> formula works (or not).
>
>
> 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.
>>
>
> Same for me.
> But maybe Ehren's earlier reply already settles the question.
>
>>
> 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.
>>
>
> IMHO a formula "of that type" (to be made precise) should always exist.
> (See Ehren's reply for the cited case.)
>
> - Maximilian
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>