Consider a sequence, $s$, with elements $1$ and $-1$, of length $2k$, $k > 0$, with sum zero and non-negative partial sums, so that:
\begin{align} \sum_{i=1}^{2k} s_{i} &= 0 \\ p_j = \sum_{i=1}^{j}{s_i} &\ge 0 \quad \forall j \in {1,2, \dots, 2k} \\ s_{i} &\in \{-1,1\} \end{align}
The partial sum $p_{n}$ is the sum of the first $n$ terms of $s$. Define $f(s)$ to be a real valued function of $s$:
\begin{align} f(s) &= \prod_{n=1}^{2k} \eta(p_n,s_n) \\ \eta(p_n,s_n) &= \begin{cases} \sqrt{p_n + 1}, & s_n = -1 \\ \sqrt{p_n}, & s_n = 1 \end{cases} \end{align}
For example:
\begin{align} f(\{-1,1\}) &= \sqrt{0} &&=0, \quad (k = 1) \\ f(\{1,-1\}) &= \sqrt{1}\sqrt{1} &&= 1, \quad (k = 1)\\ f(\{1,1,-1,-1\}) &= \sqrt{1}\sqrt{2}\sqrt{2}\sqrt{1} && = 2, \quad (k = 2) \\ f(\{1,-1,1,-1\}) &= \sqrt{1}\sqrt{1}\sqrt{1}\sqrt{1} && = 1, \quad (k = 2)\\ \end{align}
My question is about the sum of $f(s)$ over all sequences $s$ of length $2k$. Let $S^{k}$ be the set of all sequences of length $2k$, with zero sum, non-negative partial sums, and containing only $-1$ and $1$. For small $k$, I have computed several of these sums in Mathematica, and conjecture that:
$$\sum_{s \in S^{k}} f(s) = (2k - 1)!!$$
where $!!$ denotes the double factorial. Finally, the question: is this true and, if so, why? How can it be proven?
End of question.
For context, here is how this question arose. I was solving problem 2.20 of Modern Quantum Mechanics, Third Edition, Sakurai and Napolitano. One is asked to compute $\langle 0 \vert \exp(iqx) \vert 0 \rangle$ for a one-dimensional simple harmonic oscillator, where $q$ is a number, $x$ is the position operator, and $\vert 0 \rangle$ is the ground state eigenket. Expressing $x$ as a sum of creation and annihilation operators yields:
\begin{align} \langle 0 \vert \exp(iqx) \vert 0 \rangle &= \sum_{j=0}^{\infty} \frac{(iq)^j}{j!}(\frac{\hbar}{ 2 m \omega})^{j/2} \langle 0 \vert (a + a^{\dagger})^{j} \vert 0 \rangle \\ &\textrm{(with all the "usual" definitions)} \\ a \vert 0 \rangle &= 0 \\ a \vert n \rangle &= \sqrt{n} \vert n - 1 \rangle, \quad n \ge 1 \\ a^{\dagger} \vert n \rangle &= \sqrt{n+1} \vert n + 1 \rangle \\ \langle 0 \vert n \rangle &= \delta_{0,n} = \begin{cases} 1 & n = 0 \\ 0 & n \ne 0 \end{cases} \end{align}
Since $a$ and $a^{\dagger}$ don't commute, expanding $(a + a^{\dagger})^j$ yields a sum of $2^j$ terms, and each term becomes one of the sequences $s$ when $a$ is replaced with $-1$, $a^{\dagger}$ is replaced with $1$, and the sequence is reversed. For example: $aa^{\dagger}a^{\dagger}a^{\dagger} \rightarrow \{1,1,1,-1\}$. The function $f(s)$ was defined to collect the product of occupation numbers (the $\sqrt{n}$ and $\sqrt{n+1}$), so that (abusing my own notation): $f(s) = \langle 0 \vert s(a,a^{\dagger}) \vert 0 \rangle$, while the non-negative partial sum condition removes many terms which vanish. The sequence is of even length, and sums to zero, because only terms with an equal number of creation and annihilation operators have non-zero expectation.
\begin{align} \langle 0 \vert \exp(iqx) \vert 0 \rangle &= \sum_{j=0}^{\infty} \frac{(iq)^j}{j!}(\frac{\hbar}{ 2 m \omega})^{j/2} \langle 0 \vert (a + a^{\dagger})^{j} \vert 0 \rangle \\ &= \sum_{j=0}^{\infty}\frac{(iq)^{2j}}{(2j)!}(\frac{\hbar}{ 2 m \omega})^{j} (2j-1)!! \quad \textrm{(substitution based on conjecture)}\\ &= \exp(\frac{-q^2}{2}\frac{\hbar}{2 m \omega}) \end{align}
And that is the correct result, as given in the question. So all that remains is to understand how we can prove that $\sum_{s \in S^{k}} f(s) = (2k - 1)!!$.