Is there a known formula for the number of closed walks of length (exactly) $r$ on the $n$-cube? If not, what are the best known upper and lower bounds?


[Edit] Note: the walk can repeat vertices.



Number of closed walks on an $n$-cube
Yes (assuming a closed walk can repeat vertices). For any finite graph $G$ with adjacency matrix $A$, the total number of closed walks of length $r$ is given by


$$\text{tr } A^r = \sum\_i \lambda\_i^r$$


where $\lambda\_i$ runs over all the eigenvalues of $A$. So it suffices to compute the eigenvalues of the adjacency matrix of the $n$-cube. But the $n$-cube is just the Cayley graph of $(\mathbb{Z}/2\mathbb{Z})^n$ with the standard generators, and the eigenvalues of a Cayley graph of any finite abelian group can be computed using the discrete Fourier transform (since the characters of the group automatically given eigenvectors of the adjacency matrix). We find that the eigenvalue $n - 2j$ occurs with multiplicity ${n \choose j}$, hence


$$\text{tr } A^r = \sum\_{j=0}^n {n \choose j} (n - 2j)^r.$$


For fixed $n$ as $r \to \infty$ the dominant term is given by $n^r + (-n)^r$. 


