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

Paul D Hanna pauldhanna at juno.com
Mon Feb 9 02:20:17 CET 2009

```Hello Robert,
Yes, and it seems to work even for higher powers of exponents:
if a(n,m) = (1/n) Sum_{k=1..n} 2^(k^m) a(n-k), with a(0)=1,
then a(n,m) is an integer for any integer m >= 0.

But when m>2 the numbers get too large too quickly to suit my taste.

Thanks for the comment.
Paul

-- Robert Israel <israel at math.ubc.ca> wrote:
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/
>

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/

```