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

Paul D Hanna pauldhanna at juno.com
Wed Feb 11 18:24:22 CET 2009

```Seqfans,
Below I rewrite the sums to show the similarity between these g.f.s
to some g.f.s already in the OEIS.
Compare sums (1) to (2) and (3) to (4).

Sums (2) and (4) have nice Binomial expressions.
Does (1) and (3) as well?

(1) Sum_{n>=0} [ Sum_{k>=1} (2^k*x)^k/k ]^n / n!

A155200 = [1, 2, 10, 188, 16774, 6745436, 11466849412, ...].

(2) Sum_{n>=0} [ Sum_{k>=1} (2^n*x)^k/k ]^n / n!

A060690 = [1, 2, 10, 120, 3876, 376992, 119877472, ...].

(3) Sum_{n>=0} [ Sum_{k>=1} ((2^k+1)*x)^k/k ]^n / n!

A155201 = [1, 3, 17, 285, 21747, 7894143, 12593691755, ...]

(4) Sum_{n>=0} [ Sum_{k>=1} ((2^n+1)*x)^k/k ]^n / n!

A133991 = [1, 3, 17, 193, 5427, 463023, 134675759, ...]

It would be nice to express (1) and (3) above in terms of binomials.
Thanks,
Paul

-- Max Alekseyev <maxale at gmail.com> wrote:
From the recurrence relations, it follows that

a(n) = B_n( 0!*2^(1^2), 1!*2^(2^2), 2!*2^(2^3), ..., (n-1)!*2^(2^n) ) / n!

and

a(n) = B_n( 0!*(2^1+1)^1*0!, 1!*(2^2+1)^2, 2!*(2^3+1)^3, ...,
(n-1)!*(2^n+1)^n ) / n!

where B_n() are complete Bell polynomials:
http://en.wikipedia.org/wiki/Bell_polynomial

Regards,
Max

On Sun, Feb 8, 2009 at 6:24 AM, Paul D Hanna <pauldhanna at juno.com> 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/

```