# [seqfan] Re: Proof For A269254

israel at math.ubc.ca israel at math.ubc.ca
Mon Oct 23 07:13:39 CEST 2017

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.
>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.
>> Email: njasloane at gmail.com
>>
>>
>> On Sun, Oct 22, 2017 at 5:49 PM, L. Edson Jeffery <lejeffery2 at gmail.com>
>> wrote:
>>
>>>
>>> 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/
>
>