Although this is an old question, I wanted to record what I think is a very cute elementary technique for obtaining the summation formula appearing in Qiaochu Yuan's answer. Maybe it is ultimately similar to Ira Gessel's answer: it also uses generating functions, but it avoids use of exponential generating functions.

I saw this technique in this mathstackexchange answer, but have never seen it elsewhere.

Here's the argument.

First of all, we note that it's easy to see, as mentioned in the answer of Derrick Stolee, that the number of closed walks of length $r$ in the $n$-hypercube is $2^n$ times the number of words of length $r$ in the alphabet $[n] := \{1,2,...,n\}$ in which every letter appears an even number of times. So we want to count words of this form.

For a word $w$ in the alphabet $[n]$, let me use $\bf{z}^w$ to denote $\mathbf{z}^w := \prod_{i=1}^{n} z_i^{\textrm{$\#$ $i$'s in $w$}}$, where the $z_i$ are formal parameters. For a set $A \subseteq [n]^{*}$ of such words, I use $F_A(\mathbf{z}) := \sum_{w \in A} \mathbf{z}^{A}$.

For $i=1,\ldots,n$ and ${F}(\mathbf{z})\in\mathbb{Z}[z_1,\ldots,z_n]$ define $$s_i(F(\mathbf{z})) := \frac{1}{2}( F(\mathbf{z}) - F(z_1,z_2,\ldots,z_{i-1},-z_{i},z_{i+1},\ldots,z_n)),$$ a kind of symmetrization operator. We have the following very easy proposition:

Prop. For $A\subseteq [n]^{*}$, $s_i(F_A(\mathbf{z})) = F_{A'}(\mathbf{z})$ where $A' := \{w\in A\colon \textrm{$w$ has an even $\#$ of $i$'s}\}$.

Thus if $A := [n]^r$ is the set of words of length $r$, and $A'\subseteq A$ is the subset of words where each letter appears an even number of times, we get $$ F_{A'}(\mathbf{z}) = s_n(s_{n-1}(\cdots s_1(F_{A}(\mathbf{z})) \cdots ) ) = s_n(s_{n-1}(\cdots s_1((z_1+\cdots+z_n)^r) \cdots ) ) $$ $$= \frac{1}{2^n}\sum_{(a_1,\ldots,a_n)\in\{0,1\}^n}((-1)^{a_1}z_1 + \cdots + (-1)^{a_n}z_n)^r.$$

Setting $z_i := 1$ for all $i$, we see that $$\#A'=\frac{1}{2^n}\sum_{j=0}^{n}\binom{n}{j}(n-2j)^r,$$ and hence that the number of closed walks we wanted to count is $$\sum_{j=0}^{n}\binom{n}{j}(n-2j)^r,$$ as we saw in Qiaochu's answer.

Incidentally, this gives a combinatorial way to compute the eigenvalues of the adjacency matrix of the $n$-hypercube (see Stanley's "Enumerative Combinatorics" Vol. 1, 2nd Edition, Chapter 4 Exercise 68).

Although this is an old question, I wanted to record what I think is a very cute elementary technique for obtaining the summation formula appearing in Qiaochu Yuan's answer. Maybe it is ultimately similar to Ira Gessel's answer: it also uses generating functions, but it avoids use of exponential generating functions.

I saw this technique in this mathstackexchange answer, but have never seen it elsewhere.

Here's the argument.

First of all, we note that it's easy to see, as mentioned in the answer of Derrick Stolee, that the number of closed walks of length $r$ in the $n$-hypercube is $2^n$ times the number of words of length $r$ in the alphabet $[n] := \{1,2,...,n\}$ in which every letter appears an even number of times. So we want to count words of this form.

For a word $w$ in the alphabet $[n]$, let me use $\bf{z}^w$ to denote $\mathbf{z}^w := \prod_{i=1}^{n} z_i^{\textrm{$\#$ $i$'s in $w$}}$, where the $z_i$ are formal parameters. For a set $A \subseteq [n]^{*}$ of such words, I use $F_A(\mathbf{z}) := \sum_{w \in A} \mathbf{z}^{w}$.

For $i=1,\ldots,n$ and ${F}(\mathbf{z})\in\mathbb{Z}[z_1,\ldots,z_n]$ define $$s_i(F(\mathbf{z})) := \frac{1}{2}( F(\mathbf{z}) + F(z_1,z_2,\ldots,z_{i-1},-z_{i},z_{i+1},\ldots,z_n)),$$ a kind of symmetrization operator. We have the following very easy proposition:

Prop. For $A\subseteq [n]^{*}$, $s_i(F_A(\mathbf{z})) = F_{A'}(\mathbf{z})$ where $A' := \{w\in A\colon \textrm{$w$ has an even $\#$ of $i$'s}\}$.

Thus if $A := [n]^r$ is the set of words of length $r$, and $A'\subseteq A$ is the subset of words where each letter appears an even number of times, we get $$ F_{A'}(\mathbf{z}) = s_n(s_{n-1}(\cdots s_1(F_{A}(\mathbf{z})) \cdots ) ) = s_n(s_{n-1}(\cdots s_1((z_1+\cdots+z_n)^r) \cdots ) ) $$ $$= \frac{1}{2^n}\sum_{(a_1,\ldots,a_n)\in\{0,1\}^n}((-1)^{a_1}z_1 + \cdots + (-1)^{a_n}z_n)^r.$$

Setting $z_i := 1$ for all $i$, we see that $$\#A'=\frac{1}{2^n}\sum_{j=0}^{n}\binom{n}{j}(n-2j)^r,$$ and hence that the number of closed walks we wanted to count is $$\sum_{j=0}^{n}\binom{n}{j}(n-2j)^r,$$ as we saw in Qiaochu's answer.

Incidentally, this gives a combinatorial way to compute the eigenvalues of the adjacency matrix of the $n$-hypercube (see Stanley's "Enumerative Combinatorics" Vol. 1, 2nd Edition, Chapter 4 Exercise 68).

Although this is an old question, I wanted to record what I think is a very cute elementary technique for obtaining the summation formula appearing in Qiaochu Yuan's answer. Maybe it is ultimately similar to Ira Gessel's answer: it also uses generating functions, but it avoids use of exponential generating functions.

I saw this technique in this mathstackexchange answer, but have never seen it elsewhere.

Here's the argument.

First of all, we note that it's easy to see, as mentioned in the answer of Derrick Stolee, that the number of closed walks of length $r$ in the $n$-hypercube is $2^n$ times the number of words of length $r$ in the alphabet $[n] := \{1,2,...,n\}$ in which every letter appears an even number of times. So we want to count words of this form.

For a word $w$ in the alphabet $[n]$, let me use $\bf{z}^w$ to denote $\mathbf{z}^w := \prod_{i=1}^{n} z_i^{\textrm{$\#$ $i$'s in $w$}}$, where the $z_i$ are formal parameters. For a set $A \subseteq [n]^{*}$ of such words, I use $F_A(\mathbf{z}) := \sum_{w \in A} \mathbf{z}^{A}$.

For $i=1,\ldots,n$ and ${F}(\mathbf{z})\in\mathbb{Z}[z_1,\ldots,z_n]$ define $$s_i(F(\mathbf{z})) := \frac{1}{2}( F(\mathbf{z}) - F(z_1,z_2,\ldots,z_{i-1},-z_{i},z_{i+1},\ldots,z_n)),$$ a kind of symmetrization operator. We have the following very easy proposition:

Prop. For $A\subseteq [n]^{*}$, $s_i(F_A(\mathbf{z})) = F_{A'}(\mathbf{z})$ where $A' := \{w\in A\colon \textrm{$w$ has an even $\#$ of $i$'s}\}$.

Thus if $A := [n]^r$ is the set of words of length $r$, and $A'\subseteq A$ is the subset of words where each letter appears an even number of times, we get $$ F_{A'}(\mathbf{z}) = s_n(s_{n-1}(\cdots s_1(F_{A}(\mathbf{z})) \cdots ) ) = s_n(s_{n-1}(\cdots s_1((z_1+\cdots+z_n)^r) \cdots ) ) $$ $$= \frac{1}{2^n}\sum_{(a_1,\ldots,a_n)\in\{0,1\}^n}((-1)^{a_1}z_1 + \cdots + (-1)^{a_n}z_n)^r.$$

Setting $z_i := 1$ for all $i$, we see that $$\#A'=\frac{1}{2^n}\sum_{j=0}^{n}\binom{n}{j}(n-2j)^r,$$ and hence that the number of closed walks we wanted to count is $$\sum_{j=0}^{n}\binom{n}{j}(n-2j)^r,$$ as we saw in Qiaochu's answer.

Incidentally, this gives a combinatorial way to compute the eigenvalues of the adjacency matrix of the $n$-hypercube (see Stanley's "Enumerative Combinatorics" Vol. 1, 2nd Edition, Chapter 4 Exercise 68.)

Although this is an old question, I wanted to record what I think is a very cute elementary technique for obtaining the summation formula appearing in Qiaochu Yuan's answer. Maybe it is ultimately similar to Ira Gessel's answer: it also uses generating functions, but it avoids use of exponential generating functions.

I saw this technique in this mathstackexchange answer, but have never seen it elsewhere.

Here's the argument.

First of all, we note that it's easy to see, as mentioned in the answer of Derrick Stolee, that the number of closed walks of length $r$ in the $n$-hypercube is $2^n$ times the number of words of length $r$ in the alphabet $[n] := \{1,2,...,n\}$ in which every letter appears an even number of times. So we want to count words of this form.

For a word $w$ in the alphabet $[n]$, let me use $\bf{z}^w$ to denote $\mathbf{z}^w := \prod_{i=1}^{n} z_i^{\textrm{$\#$ $i$'s in $w$}}$, where the $z_i$ are formal parameters. For a set $A \subseteq [n]^{*}$ of such words, I use $F_A(\mathbf{z}) := \sum_{w \in A} \mathbf{z}^{A}$.

For $i=1,\ldots,n$ and ${F}(\mathbf{z})\in\mathbb{Z}[z_1,\ldots,z_n]$ define $$s_i(F(\mathbf{z})) := \frac{1}{2}( F(\mathbf{z}) - F(z_1,z_2,\ldots,z_{i-1},-z_{i},z_{i+1},\ldots,z_n)),$$ a kind of symmetrization operator. We have the following very easy proposition:

Prop. For $A\subseteq [n]^{*}$, $s_i(F_A(\mathbf{z})) = F_{A'}(\mathbf{z})$ where $A' := \{w\in A\colon \textrm{$w$ has an even $\#$ of $i$'s}\}$.

Thus if $A := [n]^r$ is the set of words of length $r$, and $A'\subseteq A$ is the subset of words where each letter appears an even number of times, we get $$ F_{A'}(\mathbf{z}) = s_n(s_{n-1}(\cdots s_1(F_{A}(\mathbf{z})) \cdots ) ) = s_n(s_{n-1}(\cdots s_1((z_1+\cdots+z_n)^r) \cdots ) ) $$ $$= \frac{1}{2^n}\sum_{(a_1,\ldots,a_n)\in\{0,1\}^n}((-1)^{a_1}z_1 + \cdots + (-1)^{a_n}z_n)^r.$$

Setting $z_i := 1$ for all $i$, we see that $$\#A'=\frac{1}{2^n}\sum_{j=0}^{n}\binom{n}{j}(n-2j)^r,$$ and hence that the number of closed walks we wanted to count is $$\sum_{j=0}^{n}\binom{n}{j}(n-2j)^r,$$ as we saw in Qiaochu's answer.

Incidentally, this gives a combinatorial way to compute the eigenvalues of the adjacency matrix of the $n$-hypercube (see Stanley's "Enumerative Combinatorics" Vol. 1, 2nd Edition, Chapter 4 Exercise 68).