[seqfan] Peculiar Integer Recurrences ... Proof?

Paul D Hanna pauldhanna at juno.com
Sun Feb 8 12:24:06 CET 2009

        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? 
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 ). 

More information about the SeqFan mailing list