Let $w(n,l)$ denote the number of closed walks of length $2l$ from a given vertex of the $n$-cube. Then, it is well-known that


$$\cosh^n(x)=\sum\_{l=0}^{\infty}\frac{w(n,l)}{(2l)!}x^{2l}.$$


Differentiating both sides, we get
$$n \cdot \cosh^{n-1}(x)\cdot \sinh(x) = \displaystyle\sum\_{l=1}^{\infty}\frac{w(n,l)}{(2l-1)!}x^{2l-1}.$$ By the Cauchy product of the Maclaurin series of $n\cosh^{n-1}(x)$ and $\sinh(x)$ and comparing coefficients of the LHS and RHS, we get the recursion


$$w(n,l)=n\sum\_{k=1}^{l}\binom{2l-1}{2k-1}w(n-1,l-k).$$


The above recursion has the following simple combinatorial interpretation. Let us count the total number of closed walks of length $2l$ on the $n$-cube. W.L.O.G, let the initial step be along the 1st dimension. Then, out of the remaining $2l-1$ steps, choose $2k-1$ more places to step back and forth the "1st" dimension. Note that there is exactly one way for this once the $2k-1$ places are chosen. For the remaining $2l-2k$ steps, we take steps in every dimension except the 1st, resulting in $w(n-1,l-k)$ ways. As $k$ is the number of times we walk back and forth the 1st dimension, we sum $k$ from 1 to $l$ ($k>0$ as the initial step is along the 1st dimension). Finally, as the initial step can be taken in $n$ dimensions, we multiply by $n$ and get the above recursion.


My question is the following. To obtain the above recursion, we considered the Cauchy product of the Maclaurin series of $n\cdot \cosh^{n-1}(x)$ and $\sinh(x)$. This, however, is equivalent to the Cauchy product of the Maclaurin series of $n \cdot \cosh^n(x)$ and $\tanh(x),$ which by the same method gives


$$w(n,l)=n\sum\_{k=1}^{l}(-1)^{k+1}\binom{2l-1}{2k-1}A(2k-1)w(n,l-k),$$


in which the "tangent numbers" $A(2k-1)=T\_k$ count the number of alternating permutations of $2k-1$ elements (note how the dimension of $w$ is unchanged). I was wondering if a combinatorial interpretation of the above was possible, in a similar fashion to the first recursion. The $(-1)^{k+1}$ term hints inclusion-exclusion, but I'm unable to come up with a satisfactory explanation.


The following post on $w(n,l)$ focuses on a closed-form expression, without mention of recursive formulae.
[Number of closed walks on an $n$-cube](https://mathoverflow.net/questions/71736/number-of-closed-walks-on-an-n-cube)



Closed walks on an $n$-cube and alternating permutations
This is a kind of inclusion-exclusion related to the identity
$$
\sum\_{k=1}^m (-1)^{k+1} \binom{2m-1}{2k-1}A(2k-1)=1 \quad\quad(1)
$$
for all $m=1,2,\ldots$.


For a route on the $n$-cube with first step being vertical we label other $2k-1$ vertical steps, take a weight $(-1)^{k+1}A(2k-1)$ for such a configuration and sum up. For given $k$, you may choose $2k-1$ places of vertical steps, after removing them and the first step you get a route of length $2(l-k)$. So the sum of weights of all configurations is
$$\sum\_{k=1}^{l}(-1)^{k+1}\binom{2l-1}{2k-1}A(2k-1)w(n,l-k).$$


On the other hand, the sum of weights of all configurations for a fixed route equals 1 due to (1). Thus the result.


You may ask how to prove (1) сombinatorially. This is most probably known, but for any sake here is a short proof.


Consider such configurations:


(i) $(x\_1,\ldots,x\_{2m-1})$ is a permutation of $1,\ldots,2m-1$ and $k\in \{1,\ldots,m\}$;


(ii) $2k-1$ first terms $x\_1,\ldots,x\_{2k-1}$ are labelled and form an alternating permutation: $x\_1<x\_2>x\_3<\ldots >x\_{2k-1}$;


(iii) other terms are decreasing: $x\_{2k}>x\_{2k+1}>\ldots>x\_{2m-1}$.


Define the weight of such configuration as $(-1)^{k+1}$. The sum of all weights is LHS of (1) (we start with fixing $k$, next fixing the set $\{x\_1,\ldots,x\_{2k-1}\}$, next fix an alternating permutation on this set). On the other hand, any permutation except $\pi=(2m-1,2m-2,\ldots,1)$ is counted twice with opposite weights, and $\pi$ is counted once with weight 1.


