# Finding Divisibility of Sequence of Numbers Generated Recursively

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

• Where do they come from? Have you checked OEIS? – vonbrand Feb 23 '16 at 23:50
• I have and they are not in the OEIS... My professor wants something related to the Euler numbers, so he's extending the denominator to increase the power series expansion. I'm not precisely sure what his motivations are, but he wanted look specifically at this generating function and the sequence it generated. – Eleven-Eleven Feb 23 '16 at 23:53
• I've checked Mathematica for numbers up to $E_{48}$ and it seems to be true...but higher than this, my computer is running slow.... – Eleven-Eleven Feb 24 '16 at 0:01

## 1 Answer

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.

• I think the idea is great, although I am confused about the expansion. How would expansion of the power series that you have for $\frac{1}{x}E_0(x)$ provide proof of the $a_{2n+1}$ being integers for all $n$? It would seem that recursively defined sequences of integers would always be integers, but is that true? – Eleven-Eleven Feb 25 '16 at 15:34
• @Eleven-Eleven: Expanding expressions like $\frac{1}{e^{2x}+1+2x}=\sum_{n\geq 0}(-1)^n(2x+e^{2x})=\sum_{n\geq 0}(-1)^n\sum_{j=0}^n\binom{n}{j}e^{2jx}(2x)^{n-j}$ we can do some structural considerations and check if the coefficients of $\frac{x^n}{n!}$ are integral. The benefit is, that if we can show that the typical coefficient is integral, this will hold for all $n$. But keep in mind that the factor $\frac{1}{n!}$ is present in the exponential generating function and has to be respected and verified, that this does not prevent the coefficient from being integral. – Markus Scheuer Feb 25 '16 at 22:25
• My cousin, @iceman, has worked on this with me for some time and someone on this site got us a closed form. I forgot about it for a while until i brought it up to him. There is a closed form here.... WIth the obvious $n!$ out front we would just have to determine that the remaining stuff inside is an integer then too, right? (sum of integers is still indeed an integer...) – Eleven-Eleven Feb 26 '16 at 19:00
• did you get a chance to look at the link above in my last comment? – Eleven-Eleven Feb 27 '16 at 15:06
• @Eleven-Eleven: Hi, I already had a look at the reference. I'm afraid the expression there is too complicated for a proper handling. I also wouldn't call this a closed form, because it contains sums. It's just a straightforward expansion. I'll try to find an answer which is convenient for you this weekend. Best regards, – Markus Scheuer Feb 27 '16 at 15:12