MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

The number of such walks is $2^n$ (the number of vertices of the $n$-cube) times the number of walks that start (and end) at the origin. We may encode such a walk as a word in the letters $1, -1, \dots, n, -n$ where $i$ represents a positive step in the $i$th coordinate direction and $-i$ represents a negative step in the $i$th coordinate direction. The words that encode walks that start and end at the origin are encoded as shuffles of words of the form $i\ -i \ \ i \ -i \ \cdots\ i \ -i$, for $i$ from 1 to $n$. Since for each $i$ there is exactly one word of this form for each even length, the number of shuffles of these words of total length $m$ is the coefficient of $x^m/m!$ in $$\biggl(\sum_{k=0}^\infty \frac{x^{2k}}{(2k)!}\biggr)^{n} = \left(\frac{e^x + e^{-x}}{2}\right)^n.$$ Expanding by the binomial theorem, extracting the coefficient of $x^r/r!$, and multiplying by $2^n$ gives Qiaochu's formula.
Let $W(n,r)$ be the coefficient of $x^r/r!$ in $\cosh^n x$, so that $$W(n,r) = \frac{1}{2^n}\sum_{j=0}^n\binom{n}{j} (n-2j)^r,$$ then n-2j)^r.$$Then we have the continued fraction, due originally to L. J. Rogers,$$ \sum_{r=0}^\infty W(n,r) x^r = \cfrac{1}{1- \cfrac{1\cdot nx^2}{ 1- \cfrac{2(n-1)x^2}{1- \cfrac{3(n-2)x^2}{\frac{\ddots\strut} {\displaystyle 1-n\cdot 1 x^2} }}}} $$A combinatorial proof of this formula, using paths that are essentially the same as walks on the n-cube, was given by I. P. Goulden and D. M. Jackson, Distributions, continued fractions, and the Ehrenfest urn model, J. Combin. Theory Ser. A 41 (1986), 21–-31. Incidentally, the formula given above for W(n,r) (equivalent to Qiaochu's formula) is given in Exercise 33b of Chapter 1 of the second edition of Richard Stanley's Enumerative Combinatorics, Volume 1 (not published yet, but available from his web page). Curiously, I had this page sitting on my desk for the past month (because I wanted to look at Exercise 35) but didn't notice until just now that this formula was on it. 3 deleted 11 characters in body The number of such walks is 2^n (the number of vertices of the n-cube) times the number of walks that start (and end) at the origin. We may encode such a walk as a word in the letters 1, -1, \dots, n, -n where i represents a positive step in the ith coordinate direction and -i represents a negative step in the ith coordinate direction. The words that encode walks that start and end at the origin are encoded as shuffles of words of the form i\ -i \ \ i \ -i \ \cdots\ i \ -i, for i from 1 to n. Since for each i there is exactly one word of this form for each even length, the number of shuffles of these words of total length m is the coefficient of x^m/m! in$$\biggl(\sum_{k=0}^\infty \frac{x^{2k}}{(2k)!}\biggr)^{n} = \left(\frac{e^x + e^{-x}}{2}\right)^n. $$Expanding by the binomial theorem, extracting the coefficient of x^r/r!, and multiplying by 2^n gives Qiaochu's formula. Incidentally, if we let W(n,r) be the coefficient of x^r/r! in \cosh^n x, so that$$W(n,r) = \frac{1}{2^n}\sum_{j=0}^n\binom{n}{j} (n-2j)^r,$$then we have the continued fraction, due originally to L. J. Rogers,$$ \sum_{r=0}^\infty W(n,r) x^r = \cfrac{1}{1- \cfrac{1\cdot nx^2}{ 1- \cfrac{2(n-1)x^2}{1- \cfrac{3(n-2)x^2}{\frac{\ddots\strut} {\displaystyle 1-n\cdot 1 x^2} }}}} $$A combinatorial proof of this formula, using paths that are essentially the same as walks on the n-cube, was given by I. P. Goulden and D. M. Jackson, \textit{Distributions, Distributions, continued fractions, and the Ehrenfest urn model,}model, J. Combin. Theory Ser. A 41 (1986), 21–-31.          2 added 678 characters in body; deleted 1 characters in body; added 3 characters in body; added 2 characters in body The number of such walks is 2^n (the number of vertices of the n-cube) times the number of walks that start (and end) at the origin. We may encode such a walk as a word in the letters 1, -1, \dots, n, -n where i represents a positive step in the ith coordinate direction and -i represents a negative step in the ith coordinate direction. The words that encode walks that start and end at the origin are encoded as shuffles of words of the form i\ -i \ \ i \ -i \ \cdots\ i \ -i, for i from 1 to n. Since for each i there is exactly one word of this form for each even length, the number of shuffles of these words of total length m is the coefficient of x^m/m! in$$\biggl(\sum_{k=0}^\infty \frac{x^{2k}}{(2k)!}\biggr)^{n} = \left(\frac{e^x + e^{-x}}{2}\right)^n. $$Expanding by the binomial theorem, extracting the coefficient of x^r/r!, and multiplying by 2^n gives Qiaochu's formula. Incidentally, if we let W(n,r) be the coefficient of x^r/r! in \cosh^n x, so that$$W(n,r) = \frac{1}{2^n}\sum_{j=0}^n\binom{n}{j} (n-2j)^r,$$then we have the continued fraction, due originally to L. J. Rogers,$$ \sum_{r=0}^\infty W(n,r) x^r = \cfrac{1}{1- \cfrac{1\cdot nx^2}{ 1- \cfrac{2(n-1)x^2}{1- \cfrac{3(n-2)x^2}{\frac{\ddots\strut} {\displaystyle 1-n\cdot 1 x^2} }}}}  A combinatorial proof of this formula, using paths that are essentially the same as walks on the $n$-cube, was given by I. P. Goulden and D. M. Jackson, \textit{Distributions, continued fractions, and the Ehrenfest urn model,} J. Combin. Theory Ser. A 41 (1986), 21–-31.