[seqfan] Re: Proof For A269254

[israel at math.ubc.ca]

Also useful in the gfun package are the `rec*rec` and `rec+rec` commands. 
Given linear recurrences (optionally with initial conditions, and not 
necessarily constant coefficients) for sequences a(n) and b(n), `rec*rec` 
and `rec+rec` produce linear recurrences for a(n)*b(n) and a(n)+b(n) 
respectively. Thus if a(n) and b(n) satisfy
  {a(n) = a(n-1) + 2*a(n-2), a(0)=0, a(1)=1}
and
  {b(n) = b(n-1) - 3*b(n-3), b(0)=1, b(1)=0, b(2)=0}
then we can get a recurrence satisfied by c(n)=a(n)*b(n) as follows:

`rec*rec`({c(n) = c(n-1) + 2*c(n-2), c(0)=0, c(1)=1},
          {c(n) = c(n-1) - 3*c(n-3), c(0)=1, c(1)=0, c(2)=0}, c(n));

the result being

{c(n+6)-c(n+5)+21*c(n+3)-2*c(n+4)+30*c(n+2)-72*c(n), c(0) = 0, c(1) = 0, 
c(2) = 0, c(3) = -9, c(4) = -15, c(5) = -33}

Cheers,
Robert

On Oct 22 2017, 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/
>
>