Evaluating the sum over all strings made of two anticommuting terms

Solution 1:

Let $C(n,k)$ denote the summation of all strings of $k$ $A$'s and $n-k$ $B$'s, so that $C(n,k)=c(n,k)A^kB^{n-k}$. Since $$ \begin{align} c(n,k)A^kB^{n-k}=C(n,k) &=A\cdot C(n-1,k-1)+B\cdot C(n-1,k)\\ &= A\cdot c(n-1,k-1) A^{k-1}B^{n-k} +B\cdot c(n-1,k)\cdot A^{k}B^{n-k-1}\\ &=c(n-1,k-1) A^{k}B^{n-k} + c(n-1,k)\color{red}{(-1)^k}\cdot A^{k}B^{n-k}\\ &=[c(n-1,k-1)+(-1)^k c(n-1,k)] A^{k}B^{n-k} \end{align} $$ We conclude that $$ c(n,k)=c(n-1,k-1)+(-1)^k c(n-1,k), $$ so $c(n,k)$ satisfies a twisted version of Pascal's rule. Using this, together with the base cases $c(0,k)=1[k=0]$, you can prove by induction that $$ c(n,k)=\begin{cases} \binom{\lfloor n/2\rfloor }{\lfloor k/2\rfloor } & \text{if $n$ is odd or $k$ is even} \\ 0 & \text{if $n$ is even and $k$ is odd} \end{cases} $$ Putting this triangle of integers into OEIS, we find the entry https://oeis.org/A051159, which also gives this description for $c(n,k)$:

Coefficients in expansion of $(x + y)^n$ where $x$ and $y$ anticommute ($y x = -x y$), that is, $q$-binomial coefficients when $q = -1$.

That is, $c(n,k)=\binom{n}{k}_{-1}$.