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

Robert Israel israel at math.ubc.ca
Sun Feb 8 21:51:29 CET 2009

```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

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/
>

```