Combinatorial proof of Recurrence for the number of permutations of odd order Let $a_n$ denote the number of permutations of odd order in $S_n$. This is sequence A000246 in OEIS. Then there is the recurrence relation on OEIS that $a_{2n} = (2n-1)a_{2n-1}$ and $a_{2n+1} = (2n+1)a_{2n}$, or equivalently $a_n = a_{n-1} + (n-1)(n-2)a_{n-2}$. 
It seems like there should be a combinatorial proof for this result. 
Since there isn't a simple recurrence for the number of partitions with odd parts, it doesn't seem like working on the level of partitions will work. 

These permutations  are precisely  the ones that  do not  contain even
cycles, giving the species
$$\mathfrak{P}(\mathfrak{C}_{=1}(\mathcal{Z})
+ \mathfrak{C}_{=3}(\mathcal{Z})
+ \mathfrak{C}_{=5}(\mathcal{Z})
+ \mathfrak{C}_{=7}(\mathcal{Z})
+ \cdots)$$
This yields the EGF
$$G(z) = \exp\left(\sum_{q\ge 1} \frac{z^q}{q}
- \sum_{q\ge 1} \frac{z^{2q}}{2q}\right)
\\ = \exp\log\frac{1}{1-z} 
\exp\left(- \frac{1}{2} \log\frac{1}{1-z^2}\right)
\\ = \frac{\sqrt{1-z^2}}{1-z}.$$
Differentiate to obtain
$$G'(z) = \frac{\sqrt{1-z^2}}{1-z} \frac{1}{1-z}
- \frac{\sqrt{1-z^2}}{1-z} \frac{z}{1-z^2}
= G(z) \frac{1}{1-z^2}.$$
Extracting coefficients we find for $n\ge 2$
$$n! [z^n] G'(z) (1-z^2) = n! [z^n] G(z)
\quad\text{or}\quad
a_{n+1} -  n! [z^{n-2}] G'(z) = a_n$$
which finally yields
$$a_{n+1} = a_n + n! \times \frac{a_{n-1}}{(n-2)!}
\quad\text{or}\quad
a_{n+1} = a_n + n (n-1) a_{n-1}$$
as desired. 
For the second recurrence we start with the closed form from the EGF
$$n! \sum_{q=0}^{\lfloor n/2\rfloor} [z^{2q}] \sqrt{1-z^2}
= n! \sum_{q=0}^{\lfloor n/2\rfloor} (-1)^q {1/2\choose q}.$$
Since $\lfloor (2n+1)/2\rfloor = \lfloor 2n/2\rfloor$ we have
$$a_{2n+1} = (2n+1) a_{2n}$$ by inspection.
The first recurrence now yields
$$a_{2n+1} = a_{2n} + 2n (2n-1) a_{2n-1}
\quad\text{or}\quad
(2n+1) a_{2n} = a_{2n} + 2n (2n-1) a_{2n-1}$$
and finally
$$2n a_{2n} = 2n (2n-1) a_{2n-1}
\quad\text{or}\quad
a_{2n} = (2n-1) a_{2n-1}.$$
