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

combinatoricsgenerating-functionssequences-and-series

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}$ …

Best Answer

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.

Related Question