How to show the double factorial isn't a polynomial

Question

$(2n-1)!! = \dfrac{(2n)!}{2^{n} \times n!}$

I was wondering how you prove the double factorial is exponential.

I guess you have to prove that for all $m$ and $\alpha$ that there exists an $n$ such that

$\alpha \times n^{m} <\dfrac{(2n)!}{2^{n} \times n!}$

However, I'm having problems. I'm sure it most be exponential.

Answer 1

We have $(2n)!!=1\cdot 3\cdot 5\cdot 7\cdots (2n-1)$. There are $n$ terms. All but one is $\ge 3$, and if $n\ge 5$ one of them is $9$. Thus if $n\ge 5$, then $(2n)!\gt 3^n$.

Note that $3\gt e$. Now use whatever tools you like to prove that for any polynomial $P(x)$, we have $e^x\gt P(x)$ for all large enough $x$.

Answer 2

We have $$(2n-1)!! = 1 \times 3 \times 5 \times \cdots \times (2n-3) \times (2n-1) = \begin{cases}\prod_{k=1,3}^{n-1} (n+k)(n-k) & \text{if n is even}\\ n\prod_{k=2,4}^{n-1} (n+k)(n-k) & \text{if n is odd}\end{cases}$$ Hence, we get that $$(2n-1)!! = \begin{cases}\prod_{k=1,3}^{n-1} (n^2-k^2) & \text{if n is even}\\ n\prod_{k=2,4}^{n-1} (n^2-k^2) & \text{if n is odd}\end{cases}$$ But $n^2 - k^2 \geq 2n-1$ for all $k \in \{0,1,2,\ldots,n-1\}$ Hence, we get that $$(2n-1)!! \geq \begin{cases} (2n-1)^{\lfloor (n-1)/2 \rfloor}& \text{if n is even}\\ n (2n-1)^{\lfloor (n-1)/2 \rfloor} & \text{if n is odd}\end{cases}$$ which is clearly faster than any polynomial.