Is $s_n$ a multiple of $2^n$ for all $n \geq 0$?

Question

Let's define: $$a_{0,0} = 1$$ $$\forall k \ne 0, a_{0,k} = 0$$ $$\forall n \geq 0, \forall k, a_{n+1,k} = -(4n-2k+3)a_{n,k-1} + (2k+1)a_{n,k}$$

    |   0    1    2    3    4  ...
----+-----------------------------
  0 |   1 
  1 |   1   -1
  2 |   1   -8    3
  3 |   1  -33   71  -15
  4 |   1 -112  718 -744  105
...   ...  ...  ...  ...  ... ...

Up to the alternated sign, this is OEIS' sequence number A214406. Now let's define: $$s_n = \sum_{k=0}^n a_{n,k}$$ $$ s_0 = 1, s_1 = 0, s_2 = -4, s_3 = 24, s_4=-32, \dots $$

It appears that for all $n$, $s_n$ is a multiple of $2^n$. Is it provable?

Context/own efforts: so far, I was able to prove connections with the sequence of functions $(R_n)_{n \in \mathbb{N}}$ defined by:

$$ R_0(x)=1 $$ $$ R_{n+1}(x) = \left( R_n(x) \times \frac{2x}{1+x^2} \right)' $$

The connection is:

$$ s_n = 2^n R_n(1) $$

We even have:

$$ R_n(x) = 2^n \frac{P_n(x^2)}{(1+x^2)^{2n}} $$

where $$ P_n(x) = \sum_{k=0}^n a_{n,k} x^k $$

I don't know if it helps, but this also means that the exponential generating function

$$ \sum_{n \geq 1} \frac{s_{n-1}}{2^{n-1}} \frac{x^n}{n!} $$

is the series reversion of

$$ \frac{\ln(x+1)}{2} + \frac{x}{2} + \frac{x^2}{4} = 0 + 1x + 0 x^2 + \frac{1}{6}x^3 - \frac{1}{8}x^4 + \frac{1}{10}x^5 - \frac{1}{12}x^6 \dots $$

I also established that

$$ s_{n+1} = -4 \sum_{k=0}^n (n-k) a_{n,k} $$

but this appears just to push the problem forward, of proving that $ \sum_{k=0}^n k a_{n,k} $ is a multiple of $2^{n-1}$ ...

Answer 1

I found a proof. Its sketch is:

Let $$ f(x) = \frac{x}{1+x^2} $$

Then with $m=\lfloor n/2 \rfloor$ and $r = n \mod 2$, the following can be established by induction:

$$ f^{(n)}(x) = (-1)^m (n!) \left ( \sum_{k=0}^{m+r} (-1)^k \binom{n+1}{2k+1-r} x^{2k + 1 - r} \right) \frac{1}{ (1+x^2)^{n+1}} $$

Then one evaluates at 1, and observes, and proves, that:

$$ 2^{m+1} \frac{f^{(n)}(1)}{n!} $$

is indeed very particular:

$$ 1, 0, -1, 1, -1, 0, 1, -1, 1, 0, -1, 1, -1, 0, 1, -1, 1, 0, -1, 1, -1, 0, 1, -1, 1, 0, -1, 1, -1, 0, 1, -1, 1, 0, -1, 1, -1, 0, 1, -1, 1, \dots $$

In other terms, $$ 2 f^{(n)}(1) = \frac{n!}{2^{\lfloor n/2 \rfloor}} \times \begin{array}{|rl|} +1, & n \in 8 \mathbb{N} + \{ 0, 3, 6 \} \\ 0, & n \in 8 \mathbb{N} + \{ 1, 5 \} \\ -1, & n \in 8 \mathbb{N} + \{ 2, 4, 7 \} \\ \end{array} $$ For even shorter notations, define $$ g = 2f $$ $$ g_n = g^{(n)} $$

Then $$ \bbox[white, border: 2px solid black]{ g_n(1) = \frac{n!}{2^{\lfloor n/2 \rfloor}} \times \begin{array}{|rl|} +1, & n \in 8 \mathbb{N} + \{ 0, 3, 6 \} \\ 0, & n \in 8 \mathbb{N} + \{ 1, 5 \} \\ -1, & n \in 8 \mathbb{N} + \{ 2, 4, 7 \} \\ \end{array} } $$

Now,

$$ \begin{array}{lcl|lcll} R_0 & = & 1 & R_0(1) & = & 1 & = 1 \\ R_1 & = & \left( R_0 g \right)' = \left( g_0 \right)' = g_1 & R_1(1) & = & \frac{1!}{2^{\lfloor 1/2 \rfloor}} \times 0 & = 0 \\ R_2 & = & \left( R_1 g \right)' = \left( g_1 g_0 \right)' = g_2 g_0 + g_1^2 & R_2(1) & = & ( \frac{2!}{2^{\lfloor 2/2 \rfloor}} \times -1)(\frac{0!}{2^{\lfloor 0/2 \rfloor}} \times +1) + (\frac{1!}{2^{\lfloor 1/2 \rfloor}} \times 0)^2 = (-1)(+1) - (0)^2 & = -1 \\ R_3 & = & \left( R_2 g \right)' = \left( (g_2 g_0 + g_1^2) g_0 \right)' = \left( g_2 g_0^2 + g_1^2 g_0 \right)' = g_3 g_0^2 + 4 g_2 g_1 g_0 + g_1^3 & R_3(1) & = & ( \frac{3!}{2^{\lfloor 3/2 \rfloor}} \times +1)(\frac{0!}{2^{\lfloor 0/2 \rfloor}} \times +1)^2 + 4 \times ( \frac{2!}{2^{\lfloor 2/2 \rfloor}} \times -1)(\frac{1!}{2^{\lfloor 1/2 \rfloor}} \times 0)(\frac{0!}{2^{\lfloor 0/2 \rfloor}} \times +1) + (\frac{1!}{2^{\lfloor 1/2 \rfloor}} \times 0)^3 = 3 \times (+1)^2 + 4 \times (-1)(0)(+1) + (0)^3 & = 3 \\ \dots \\ \end{array} $$

Clearly, behind the scene are the partitions of $n$ and their coefficients listed in OEIS sequence number A145271. The following formula holds, $$ \bbox[white, border: 2px solid black]{ R_n(1) = \sum_{P \mbox{ partition of } n} \mbox{A145271}(n, P) \times \prod_{p \mbox{ part of } P} g_{\mbox{size}(p)}(1) } $$

with the nice property that it's not worth computing the contributions of partitions that contain a part equal to 1, or 5, or a multiple of 4 plus 1 (they are 0).

Finally, as a sum of products of integers, $R_n(1)$ is an integer; and $s_n$ is thus a multiple of $2^n$.

Answer 2

Starting with $$s_n = 2^n R_n(1)$$

All we need to prove then is that $R_n(1)$ is an integer for all $n$

Clearly $s_n$ is a sequence of integers, implying that if $R_n(1)$ is not an integer, then it must be a fraction with denominator $2^m,m\leq n$.

Remember $ R_0(x)=1, R_{n+1}(x) = \left( R_n(x) \times \frac{2x}{1+x^2} \right)' $

Note that since $R_n(x)$ can subsequently be written as $R_n(1)=\frac{a*2^b}{2^m}$ for integers $a,b$, we just need to prove $b\geq m$ to prove $R_n(1)$ is an integer

Proof by induction:

$R_0(1)$ clearly satisfies this condition.

Also note for $n>0$, $R_{n+1}(x) = \cfrac{d}{dx} (R_n(x) \times (\frac{2x}{x^2+1}-1))=R^{'}_n(x)\times \frac{2x}{x^2+1}-R_n(x)\times \frac{2(x+1)(x-1)}{(x^2+1)^2}$

$R_{n+1}(1) = R^{'}_n(1)\times (1-0) = R^{'}_n(1)$

$R_{n+1}(1) = \frac{d^n}{dx^n}R_1(1) = \frac{d^{n+1}}{dx^{n+1}}\frac{2x}{x^2+1}$

By the quotient rule, if there are $m-b$ factors of $2$ in the simplified denominator of $R_n(1)$ (such that there are 0 factors of 2 in the numerator), then there is at most $2(m-b)$ factors of $2$ in the denominator of $R^{'}_n(1)$.

However, since for $R_0(1),m-b=0$, then for $R_1(1)$, the denominator can have at most $2(m-b) = 0$ factors of 2. Equivalently, $2(m-b)\leq 0,b\geq m$ By induction, this holds true for every $R_n(1)$, which is what we set out to prove.