I ran into this problem the other day. The proof is supposed to be done by exhibiting an explicit bijection between two sets, without using induction, recurrence, or generating functions.
Denote by $\omega(n)$ the number of permutations $\sigma\in S_n$ so that $\sigma$ has a square root (that is, there exists $\tau\in S_n$ so that $\tau^2 = \sigma$). Prove that $\omega(2n+1) = (2n+1)\omega(2n)$.