# [seqfan] Re: Peculiar Integer Recurrences ... Proof?

f.firoozbakht at sci.ui.ac.ir f.firoozbakht at sci.ui.ac.ir
Mon Feb 9 11:19:19 CET 2009

```Quoting Robert Israel <israel at math.ubc.ca>:

> It seems to work as well if 2 is replaced by any other integer.
> If a(n,x) = (1/n) Sum_{k=1..n} x^(k^2) a(n-k), with a(0)=1,
> then the polynomial a(n,x) takes integer values on the integers.
>
>
> Robert Israel

It seems that it's true for the second sequence of polynomials too.
Namely the terms of both sequences of polynomials takes integer values
on the integers(x can be negative):

a(n,x) = (1/n) Sum_{k=1..n} x^(k^2) a(n-k,x), with a(0,x)=1

b(n,x) = (1/n) Sum_{k=1..n} (x^k+1)^k b(n-k,x), with b(0,x)=1

a(n,x) for n = 0, 1, 2, ..., 8 :

a(0,x) = 1

a(1,x) = x

a(2,x) = 1/2!(x^2+x4)

a(3,x) = 1/3!(x^3+3x^5+2x^9}

a(4,x) = 1/4!(x^4+6x^6+3x^8+8x^10+6x^16)

a(5,x) = 1/5!(x^5+10x^7+15x^9+20x^11+20x^13+30x^17+24x^25)

a(6,x) = 1/6!(x^6+15x^8+45x^10+55x^12+120x^14+130x^18+90x^20+144x^26+120x^36)

a(7,x) = 1/7!(x^7+21x^9+105x^11+175x^13+420x^15+210x^17+490x^19+630x^21+
420x^25+504x^27+504x^29+840x^37+720x^49)

a(8,x) = 1/8!(x^8+28x^10+210x^12+532x^14+1225x^16+1680x^18+1540x^20+3640x^22+
3640x^22+1260x^24+3360x^26+1344x^28+4032x^30+1260x^32+2688x^34+
3360x^38+3360x^40+5760x^50+5040x^64)

And b(n,x) for n = 0, 1, 2, ..., 5 :

b(0,x) = 1

b(1,x) = 1+x

b(2,x) = 1/2!(2+2x+3x^2+x^4)

b(3,x) = 1/3!(6+6x+9x^2+13x^3+3x^4+3x^5+6x^6+2x^9)

b(4,x) = 1/4!(24+24x+36x^2+52x^3+85x^4+12x^5+42x^6+24x^7+39x^8+8x^9+8x^10+
24x^12+6x^16)

b(5,x) =
1/5!(120+120x+180x^2+260x^3+425x^4+561x^5+210x^6+250x^7+375x^8+235x^9+
340x^10+60x^11+120x^12+140x^13+240x^15+30x^16+30x^17+120x^20+
24x^25)

--- Farideh Firoozbakht

> On Sun, 8 Feb 2009, Paul D Hanna wrote:
>
>> Seqfans,
>>        Prove that the following recurrences generate only integers.
>>
>> (1) a(n) = (1/n)*Sum_{k=1..n} 2^(k^2) * a(n-k) for n>0, with a(0)=1.
>>
>> (2) a(n) = (1/n)*Sum_{k=1..n} (2^k + 1)^k * a(n-k) for n>0, with a(0)=1.
>>
>> Emperical evidence: a(0) thru a(400) are all integers - quite convincing
>> (a(400) has 48163 digits in both recurrences).
>>
>> A proof would be nice!
>> Anyone up for the challenge?
>>       Paul
>>
>> P.s.: recurrence (1) was derived by Vladeta Jovovic from the g.f.
>> for A155200.
>> I think (1) may lend itself to a proof better than the g.f. given there:
>> G.f.: A(x) = exp( Sum_{n>=1} 2^(n^2) * x^n/n ).
>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>>

----------------------------------------------------------------
University of Isfahan (http://www.ui.ac.ir)

```