# Prove by Induction that the Hyper graph $Q_d$ has at least $2^{{2^d} - d - 2}$ spanning trees

we experimented with some pen and paper and saw that the maximal number of spanning trees can be recursively defined as:

• $Q(1) = 1$
• $Q(2) = 4$
• $Q(d) = Q(d-1) * 2^{d-1}$

for $Q_d \geqslant 1$

we now consider $R(d) = 2^{{2^d} - d - 2}$ and construct our Basis

• d = 1 $\rightarrow$ is a special case where Q(1) = R(1) = 1
• d = 2 $\rightarrow$ Q(2) = 4 and R(2) = 1.

for our Induction step we consider that for $d+1$ $\rightarrow$ $Q(d+1) \geqslant R(d+1)$

now is this what i'm supposed to prove? and if so, how do i prove a $\geqslant$ per induction?

-
any tips? am i moving in the wrong direction here ? –  Shokodemon Jun 28 '12 at 21:33
Yes, that is what you're supposed to do in order to prove an inequality by induction. However, according to this paper from arXiv, it is shown in Stanley's Enumerative Combinatorics that the number of spanning trees of the $d$-dimensional hypercube is $\prod_{k=2}^d (2k)^{\binom{d}{k}}$. –  Andrew Uzzell Dec 11 '12 at 13:21