Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.