Finding Divisibility of Sequence of Numbers Generated Recursively

Question

I have the following generating function: $$E(x)=\frac{2e^x}{e^{2x}+1+2x}=\sum_{n=0}^\infty {E_n}\frac{x^n}{n!}$$ which generates a sequence of integers below

$$\{1, -1, 3, -15, 93, -725, 6815, -74627, 933849,-13148361,205690779,...\}$$

Thus, accordingly, $E_0=1, E_1=-1, E_2=3, E_3=-15, ...$. So I was playing around and decided to look at these numbers prime factorization. Below is the breakdown of the first 15 numbers... $$ \begin{array}{l|l} n & |E_n| & \text{prime decomposition} \\ \hline 0 & 1 & 1 \\ 1 & 1 & 1 \\ 2 & 3 & 3 \\ 3 & 15 & 3\cdot 5 \\ 4 & 93 & 3\cdot 31 \\ 5 & 725 & 5^2\cdot 29 \\ 6 & 6815 & 5\cdot 29\cdot 47 \\ 7 & 74627 & 7^2\cdot 1523 \\ 8 & 933849 & 3^7\cdot 7\cdot 61 \\ 9 & 13148361 & 3^2\cdot 17\cdot 19\cdot 4523 \\ 10 & 205690779 & 3^3\cdot 7^2\cdot 155473 \\ 11 & 3539545559 & 11\cdot 31\cdot 43\cdot 241393 \\ 12 & 66466203637 & 11\cdot 283\cdot 701\cdot 30449 \\ 13 & 1351309774685 & 5\cdot 13\cdot 97\cdot 5003\cdot 42839 \\ 14 & 29595401433975 & 3\cdot 5^2\cdot 13\cdot 8539\cdot 3554779 \\ \end{array} $$

I noticed that for odd indexed numbers, the number was divisible by the index; in other words, $n|E_n$. Also, for even indexed numbers, the number was divisible by the index minus one, so $(n-1)|E_n$. Below is the chart color coded with odds in red and evens in blue.

$$ \begin{array}{l|l} n & |E_n| & \text{prime decomposition} \\ \hline 0 & 1 & 1 \\ \color{red}{1} & 1 & \color{red}{1} \\ \color{blue}{2} & 3 & \color{blue}{1}\cdot 3 \\ \color{red}{3} & 15 & \color{red}{3}\cdot 5 \\ \color{blue}{4} & 93 & \color{blue}{3}\cdot 31 \\ \color{red}{5} & 725 & \color{red}{5}^2\cdot 29 \\ \color{blue}{6} & 6815 & \color{blue}{5}\cdot 29\cdot 47 \\ \color{red}{7} & 74627 & \color{red}{7}^2\cdot 1523 \\ \color{blue}{8} & 933849 & 3^7\cdot \color{blue}{7}\cdot 61 \\ \color{red}{9} & 13148361 & \color{red}{3^2}\cdot 17\cdot 19\cdot 4523 \\ \color{blue}{10} & 205690779 & 3\cdot \color{blue}{3^2}\cdot 7^2\cdot 155473 \\ \color{red}{11} & 3539545559 & \color{red}{11}\cdot 31\cdot 43\cdot 241393 \\ \color{blue}{12} & 66466203637 & \color{blue}{11}\cdot 283\cdot 701\cdot 30449 \\ \color{red}{13} & 1351309774685 & 5\cdot \color{red}{13}\cdot 97\cdot 5003\cdot 42839 \\ \color{blue}{14} & 29595401433975 & 3\cdot 5^2\cdot \color{blue}{13}\cdot 8539\cdot 3554779 \\ \end{array} $$

I thought this was interesting and think the conjecture would hold. My problem is this: I don't know how to begin even testing this idea. How do you test for divisibility of large numbers when the numbers are generated recursively? It would be easy to test for the small; $E_0, E_3, $ etc. But this is an infinite sequence, so how could i test the 100th term? What are some methods that would be used to prove such a conjecture?

EDIT: I do have the recursive definition, in fact I have two for the numbers, which may help readers...

$$E_n=1-2nE_{n-1}-\sum_{k=0}^{n-2}{\binom{n}{k}2^{n-k-1}E_k}$$ and $$E_n=-\frac{1}{2}\sum_{k=0}^{n-1}\binom{n}{k}\left(1+(-1)^{n-k}+2(n-k)(-1)^{n-k-1}\right)E_k$$

Answer 1

At first we simplify the problem by considering even and odd parts of $E(x)$ separately. We can write \begin{align*} E(x)&=E_e(x)+E_o(x)\\ &=\frac{E(x)+E(-x)}{2}+\frac{E(x)-E(-x)}{2} \end{align*}

The odd part: $E_o(x)$

Here we focus at the odd part $E_o(x)$. We want to show that \begin{align*} 2n+1|E_{2n+1}\qquad\qquad n\geq 0 \end{align*} Translated into exponential generating functions we consider \begin{align*} E_o(x)&=\sum_{n=0}^\infty E_{2n+1}\frac{x^{2n+1}}{(2n+1)!}\\ &=\sum_{n=0}^\infty (2n+1)a_{2n+1}\frac{x^{2n+1}}{(2n+1)!}\\ &=\sum_{n=0}^\infty a_{2n+1}\frac{x^{2n+1}}{(2n)!}\\ &=x\sum_{n=0}^\infty a_{2n+1}\frac{x^{2n}}{(2n)!} \end{align*} and have to show that \begin{align*} \frac{1}{x}E_o(x) \end{align*} has integral coefficients.

[2016-02-28] Update:

We show $\frac{1}{x}E_o(x)$ has integral coefficients. We start with an expansion of the generating function.

\begin{align*} \frac{1}{x}E_o(x)&=\frac{1}{2x}\left(\frac{2e^x}{e^{2x}+1+2x}-\frac{2e^{-x}}{e^{-2x}+1-2x}\right)\\ &=\frac{1}{x}e^x\sum_{n=0}^{\infty}(-1)^n\left(2x+e^{2x}\right)^n-\frac{1}{x}e^{-x}\sum_{n\geq 0}(-1)^n\left(-2x+e^{-2x}\right)^n\tag{1}\\ &=\frac{1}{x}e^x\sum_{n=0}^{\infty}(-1)^n\sum_{j=0}^n\binom{n}{j}(2x)^je^{2x(n-j)}\\ &\qquad\qquad-\frac{1}{x}e^{-x}\sum_{n\geq 0}(-1)^n\sum_{j=0}^n\binom{n}{j}(-2x)^je^{-2x(n-j)}\\ &=2\sum_{n=0}^{\infty}(-1)^n\sum_{j=0}^n\binom{n}{j}(2x)^{j-1} \left(e^{x(2n-2j+1)}+(-1)^{j-1}e^{-x(2n-2j+1)}\right)\tag{2} \end{align*}

In (1) we use an expansion as geometric series and the representation (2) is appropriate for the next step. Note that $\frac{1}{x}E_o(x)$ is an even function. So, we only need to take care of coefficients of even powers of $x$. In the following we use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a generating series. In order to show that the exponential generating function $\frac{1}{x}E_o(x)$ has integral coefficients we claim

The following is valid \begin{align*} (2k)![x^{2k}]\frac{1}{x}E_o(x)\in\mathbb{Z} \qquad\qquad k\geq 0 \end{align*}

We obtain from (2)

\begin{align*} (2k)!&[x^{2k}]\frac{1}{x}E_o(x)\\ &=2(2k)![x^{2k}]\sum_{n=0}^{\infty}(-1)^n\sum_{j=0}^n\binom{n}{j}(2x)^{j-1} \left(e^{x(2n-2j+1)}+(-1)^{j-1}e^{-x(2n-2j+1)}\right)\\ &=2(2k)!\sum_{n=0}^{\infty}(-1)^n\sum_{j=0}^{n}\binom{n}{j}2^{j-1}\\ &\qquad\cdot[x^{2k-j+1}]\left(\sum_{l=0}^{\infty}\frac{1}{l!}(2n-2j+1)^lx^l +(-1)^{j-1}\sum_{l=0}^{\infty}\frac{1}{l!}(2n-2j+1)^lx^l\right)\tag{3}\\ &=2(2k)!\sum_{n=0}^{2k+1}(-1)^n\sum_{j=0}^{n}\binom{n}{j}2^{j-1}\\ &\qquad\cdot\left((2n-2j+1)^{2k-j+1} +(-1)^{j-1}(2n-2j+1)^{2k-j+1}\right)\frac{1}{(2k-j+1)!}\tag{4}\\ \end{align*}

Comment:

• In (3) we apply the linearity of the coefficient of operator and use the rule $$[x^{n+m}]A(x)=[x^n]x^{-m}A(x)$$

• In (4) we select the value $l=2k-j+1$ corresponding to the coefficient $[x^{2k-j+1}]$. Note that the power $2k-j+1$ is non-negative and $0\leq j \leq n$. We respect this by considering \begin{align*} 2k-n+1\geq 0 \end{align*} which gives an upper limit $2k+1$ of the sum with index $n$.

Looking at the representation (4) we see there is only one critical part when considering the integral property, namly the fraction \begin{align*} \frac{(2k)!}{(2k+1-j)!}\qquad\qquad 0\leq j \leq 2k+1 \end{align*} all other parts are clearly integral. This fraction is integral for all values of $j$ besides $j=0$. So, we finally have to take a look at (4) with $j=0$. \begin{align*} 2(2k)!\sum_{n=0}^{2k+1}(-1)^n\frac{1}{2}\left((2n+1)^{2k+1} -(2n+1)^{2k+1}\right)\frac{1}{(2k+1)!}=0\in\mathbb{Z} \end{align*} and the claim follows.

A similar job could be done for the even part.