[seqfan] Re: Highest exponent of 2 dividing A155200(n)
Max Alekseyev
maxale at gmail.com
Thu Sep 3 05:08:50 CEST 2009
On Wed, Sep 2, 2009 at 8:59 PM, <franktaw at netscape.net> wrote:
> Not a complete answer, but perhaps some insight.
>
> The power of 2 dividing n! is n - A000120(n).
>
> Thus, the conjecture is equivalent to A155200(n) * n! is divisible by
> exactly 2^n.
The proof is then easily follows from the recurrent formula:
%F A155200 n*a(n) = 2*a(n-1) + sum(k=1,n-1,4^k*a(k)*[2*(k+1)*a(n-1-k)
- (n-k)*a(n-k)] for n>0, with a(0)=1.
Multiplying it by (n-1)!, we have:
a(n)*n! = 2*a(n-1)*(n-1)! + sum(k=1,n-1,
binomial(n-1,k)*4^k*a(k)*k!*[2*(k+1)*a(n-1-k)*(n-1-k)! -
a(n-k)*(n-k)!].
Assume that valuation(a(m)*m!,2) = m for all m<n.
Then for every summand (k=1..n-1), we have
valuation( binomial(n-1,k)*4^k*a(k)*k!*[2*(k+1)*a(n-1-k)*(n-1-k)! -
a(n-k)*(n-k)!], 2 )
>= 2k + k + (n-k) = 2k+n > n.
and thus
valuation(a(n)*n!,2) = valuation(a(n-1)*(n-1)!,2)+1 = n.
By induction, valuation(a(n)*n!,2) = n for all n.
Regards,
Max
More information about the SeqFan
mailing list