Prove that for $n\ge 2$, the $n$-cube has at least $2^{2^{n-2}}$ perfect matchings

Question

While reviewing graph theory, I came across a problem that I could not solve. The first part of the question asked one to prove that the n-cube has a perfect matching. This seemed to be a consequence of Hall's Theorem also described here:

Perfect matching in k-cubes

However, I am not sure as to how to start to enumerate how many perfect matching are in total. Any help would be much appreciated!

Thanks

Answer 1

It holds trivially for $n=2$. So we proceed by induction on $n$. If it holds for some $n\geq 2$, then we consider the $n+1$-cube which constitutes of $2$ $n$-cube, by induction hypothesis, each $n$-cube has at least $2^{2^{n-2}}$ many perfect matchings, hence, just consider those perfect matchings formed by some perfect matchings of the two $n$-cube, for the $n+1$-cube we have at least $(2^{2^{n-2}})^2=2^{2\cdot2^{n-2}}=2^{2^{(n+1)-2}}$ perfect matchings.