[seqfan] Re: Proof For A269254

[Fred Lunnon]

  Testing recurrence equality requires comparing only  max(k, m)  terms!

  A curious echo of my earlier enquiry concerning automatic sequences
--- and my thanks for replies to that off-list.

WFL



On 10/23/17, israel at math.ubc.ca <israel at math.ubc.ca> wrote:
> In fact, if we know a sequence a(n) satisfies a linear recurrence of order
> <= k, and another sequence b(n) satisfies a linear recurrence of order <=
> m, then a(n) - b(n) satisfies a linear recurrence of order <= k*m. Thus if
> the first k*m terms of a and b match, they must be equal. So if you have a
> sequence that you know has order at most 6, and gfun finds a
> constant-coefficient recurrence of order 2 that matches the first 12 terms,
> you know that your sequence satisfies this.
>
> Cheers,
> Robert
>
>
> On Oct 22 2017, Neil Sloane wrote:
>
>>PS
>>
>>The missing steps in the proof can be filled in like this.
>>
>>For example, we know by construction that b(n) satisfies a second-order
>>recurrence,
>>and c(n) a third-order recurrence.  We want to prove that the componentwise
>>product b(n)*c(n) satisfies a second order recurrence. Well, a basic
>>theorem about linear recurrences tells us that the product satisfies a
>>linear recurrence of order at most 2*3 =  6. And NOW we can use Gfun in
>>Maple to find it,
>>and it turns out to satisfy a second-order recurrence.  All that gfun does
>>in a case like this is to make a call to Maple's convert[ratpoly], which
>>uses Pade approximations.  I assume this can be made rigorous if anyone has
>>doubts.
>>
>>Best regards
>>Neil
>>
>>Neil J. A. Sloane, President, OEIS Foundation.
>>11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
>>Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
>>Phone: 732 828 6098; home page: http://NeilSloane.com
>>Email: njasloane at gmail.com
>>
>>
>>On Sun, Oct 22, 2017 at 10:38 PM, Neil Sloane <njasloane at gmail.com> wrote:
>>
>>> The case 110 is certainly always composite. I didn't work out all the
>>> details, but, first, a(3n+1) is zero mod 3 (just run the recurrence mod
>>> 3)
>>>
>>> Second, it seems that a(3n) = b(n)*c(n),
>>> where Don Reble found b(n) = 110*b(n-1)-b(n-2), and using gfun I get
>>> c(n) = 12099*c(n-1)-12099*c(n-2)+c(n-3)
>>>
>>> Third, similarly, it seems that a(3n+2) = d(n)*e(n), where d(n) and e(n)
>>> satisfy the same recurrences as b(n) and c(n), except with different
>>> initial conditions.
>>>
>>> This may not be a legal proof, but one can now use gfun to verify that
>>> a(3n) and b(n)*c(n) satisfy the recurrence
>>> A(n) = 1330670*A(n-1) - A(n-2),
>>> and so must be equal.
>>> Likewise,  a(3n+2), d(n)*e(n) satisfy the same recurrence
>>> (with different initial conditions)
>>> and so are also equal.
>>>
>>>
>>>
>>> Best regards
>>> Neil
>>>
>>> Neil J. A. Sloane, President, OEIS Foundation.
>>> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
>>> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
>>> Phone: 732 828 6098 <(732)%20828-6098>; home page: http://NeilSloane.com
>>> Email: njasloane at gmail.com
>>>
>>>
>>> On Sun, Oct 22, 2017 at 5:49 PM, L. Edson Jeffery <lejeffery2 at gmail.com>
>>> wrote:
>>>
>>>> Brad,
>>>>
>>>> Nice proof. I just submitted the array used for computing A269254.
>>>> Here is the draft if anyone wants to add to it:
>>>>
>>>> https://oeis.org/draft/A294099
>>>>
>>>> I also stated the theorem in A269254 and gave a link to your proof on
>>>> seqfan.
>>>>
>>>> Meanwhile, a(110) is still unknown. My Mathematica program ran all
>>>> night, and is still running, to no avail.
>>>>
>>>> Ed Jeffery
>>>>
>>>> --
>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>>
>>>
>>>
>>
>>--
>>Seqfan Mailing list - http://list.seqfan.eu/
>>
>>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>