Nested Sum Encountered in Maclaurin Expansion of $e^{-x^2}$

Question

In the course of working out the Maclaurin expansions of $e^{-x^2}$ and $cos(x^2)$, I ran into the following nested sum:

$$ \underbrace{ \sum_{a=0}^1 \left( a \sum_{b=0}^{a+1} b \left( \sum_{c=0}^{b+1} c \cdots d \sum_{e=0}^{d+1} \left( e \sum_{f=0}^{e+1} f \right) \right) \right) }_{\text{n sums deep}} $$

To illustrate, for $n=4$ the above will expand to

$$ 1(2(3(4+3+2+1)+2(3+2+1)+1(2+1))+1(2(3+2+1)+1(2+1))) $$

Then from looking at a hand calculation of the first few terms and guessing the pattern, it looks like the above should be equal to

$$ \prod_{k=1}^n (2k-1) $$

Indeed, I numerically confirmed equality up to $n=16$, but haven't had luck at finding a proof yet.

Can you find either a proof or a counterexample?

Answer 1

Define $a(n,1)=n(1+2+\dots+(n+1))=n(n+1)(n+2)/2$. Then define recursively $$a(n,k)=n\sum_{r=1}^{n+1}a(r,k-1)$$ Then your sequence is $a(1,1),a(1,2),a(1,3),\dots$. So entering that into Mathematica, we get $3, 15, 105, 945, 10395, 135135,\dots$. Checking with oeis.org we find these are just the numbers $1\times3\times5\times7\times\dots\times 2n-1$.

Since you did not ask for a proof of the correct formula and I am lazy, I have not given one, but it should be fairly easy by induction.

Answer 2

Returned to the problem and things became clear. Thank you to almagest for the inspiration to consider his recursive function.

To keep everything in one spot, I'll start from the beginning defintions:

Let $S \colon \mathbb{N}^{2} \to \mathbb{N}$ and define as follows:

$$ \begin{align} S(0,0) & \equiv 0 \\ S(0,k) & \equiv 0 \\ S(a,0) & \equiv 1 \label{eq_Sa0}\tag{1}\\ S(a,k) & \equiv \sum_{n_{1}=0}^{a} n_{1} \sum_{n_{2}=0}^{n_{1}+1} + ... n_{k-1} \sum_{n_k=0}^{n_{k-1}+1} \end{align} $$

Then we can recursively define $S$ as follows:

$$ S(a,k+1) = \sum_{n=0}^{a} n S(n+1,k) $$

We wish to show the following since the case $a=1$ reduces to my original question (to be shown below):

$$ S(a,k) = \frac{1}{2^{k}k!} \prod_{p=0}^{2k-1} (a+p) \label{eq_main}\tag{2} $$

Before we continue we will need to make use of the following lemma (pay close attention to the index $k$):

$$ \sum_{n=0}^{a} \prod_{p=0}^{k-1} (a+p) = \frac{1}{k+1} \prod_{p=0}^{k} (a+p) \label{eq_lemma}\tag{3} $$

To prove \ref{eq_lemma} we will proceed by induction. First notice that \ref{eq_lemma} is trivially true for all $k \in \mathbb{N}$ when $a=0$:

$$ \begin{align} \sum_{n=0}^{0} \prod_{p=0}^{k-1} (a+p) & = \prod_{p=0}^{k-1} p = 0 \\ & = \frac{1}{k+1} \prod_{p=0}^{k} (0+p) \end{align} $$

Since we know know \ref{eq_lemma} is true for all $k \in \mathbb{N}$ with at least some given $a \in \mathbb{N}$ then

$$ \begin{align} \sum_{n=0}^{a+1} \prod_{p=0}^{k-1} (a+p) & = \sum_{n=0}^{a} \prod_{p=0}^{k-1} (a+p) + (a+1)(a+2) \cdots (a+k) \\ & = \frac{1}{k+1} \prod_{p=0}^{k} (a+p) + (a+1)(a+2) \cdots (a+k) \\ & = (a+1)(a+2) \cdots (a+k)\left(\frac{a}{k+1} + 1\right) \\ & = \frac{1}{k+1}(a+1)(a+2) \cdots (a+k)[a + (k+1)] \\ & = \frac{1}{k+1} \prod_{p=0}^{k} (a + 1 +p) \end{align} $$

Thus quod erat demonstrandum for Lemma \ref{eq_lemma}.

Now let's return to proving \ref{eq_main} and proceed inductively from the trivial case $k=1$ which is clearly true for all $k \in \mathbb{N}$ since by definition we know \ref{eq_Sa0}:

$$ \begin{align} S(a,1) & = \sum_{n=0}^{a} n S(a+1,0) \\ & = \sum_{n=0}^{a} n \\ & = \frac{1}{2} a(a+1) \end{align} $$

Thus we know that \ref{eq_main} is true for all $a \in \mathbb{N}$ for some particular $k \in \mathbb{N}$. So we proceed by induction on $k$, keeping in mind Lemma \ref{eq_lemma} from above:

$$ \begin{align} S(a,k+1) & = \sum_{n=0}^{a} n S(n+1,k) \\ & = \sum_{n=0}^{a} n \frac{1}{2^{k}k!} \prod_{p=0}^{2k-1} (n + 1 +p) \\ & = \frac{1}{2^{k}k!} \sum_{n=0}^{a} \prod_{p=0}^{2k} (n + p) \\ & = \frac{1}{2^{k}k!} \left[\frac{1}{2(k+1)} \prod_{p=0}^{k+1} (a+p)\right] \\ & = \frac{1}{2^{k+1}(k+1)!} \prod_{p=0}^{k+1} (a+p) \end{align} $$

And Q.E.D. for equation \ref{eq_main}. Now all the remains to be shown is that \ref{eq_main} reduces to the question in the original post when $a=1$:

$$ \begin{align} \sum_{n_{1}=0}^{1} n_{1} \sum_{n_{2}=0}^{n_{1}+1} + ... n_{k-1} \sum_{n_k=0}^{n_{k-1}+1} &= S(1,k) \\ & = \frac{1}{2^{k}k!} \prod_{p=0}^{2k-1} (p+1) \\ & = \frac{1 \cdot 2 \cdot 3 \cdots (2k-1)2k}{2 \cdot 4 \cdot 6 \cdots (2k-2)2k} \\ & = \prod_{p=1}^{k} (2p-1) \end{align} $$

Q.E.D.

Thanks again, almagest, for the inspiration!