bogus OGF in A002113 (and very many others)

[N. J. A. Sloane]

On Mon, May 12, 2008 at 12:32 PM, Joerg Arndt <arndt at jjj.de> wrote:
> I think the GF for A067743 is
> sum(k=1,N, z^(2*k^2)*(1+z^k)/(1-z^k) )
>
> comment says that seq ==   A000005[n] - A067742[n]
> which have GFs:
> Sum_{k>0} x^(k^2)*(1+x^k)/(1-x^k)
> and
> sum((-1)^(k-1)*q^(k+1 choose 2)/(1-q^k), k, 1, inf)
>
> (more forms are given with A000005)
>
> From these the statement should follow.

It follows, but pure algebraic proof may be relatively hard.
On the other hand, there is a simple proof for your proposed GF, not
dealing directly with GFs for A000005 and A067742.

We need to count such divisors d|n that d^2<=n/2 or d^2>2n.
In the latter case, let's switch to co-divisor, replacing d with n/d.
Then we need to find the total count of:
1) such divisors d|n that 2d^2<=n;
2) such divisors d|n that 2d^2<n.

Let d|n and 2d^2<=n. Then n-2d^2 must be a multiple of d, i.e.,
n-2d^2=td for some integer t>=0.
Moreover, it is easy to see that 1) is equivalent to n = 2d^2 + td for
some integer t>=0.
Therefore, the answer for 1) is the coefficient of z^n in
SUM[d=1..oo] SUM[t=0..oo] x^(2d^2 + td) = SUM[d=1..oo] x^(2d^2)/(1 - x^d)

Similarly, the answer for 2) is
SUM[d=1..oo] x^(2d^2)/(1 - x^d) * x^d

Therefore, the GF for A067743 is
SUM[d=1..oo] x^(2d^2)/(1 - x^d) + SUM[d=1..oo] x^(2d^2)/(1 - x^d) * x^d
= SUM[d=1..oo] x^(2d^2)/(1 - x^d) * (1 + x^d)
as proposed.

Regards,
Max