Why is the constant term of $(1+x+y+xy)^n$ equal to $\frac{1}{2}\binom{2n}{n}$？ 
If we define this: for any $x,y$ such that 
  $x^2=y^2=1,xy\neq yx$, express in terms of $n$ the constant term of the expression $$f_{n}=(1+x+y+xy)^n\,.$$

I guess this result is $\dfrac{1}{2}\binom{2n}{n}$.
for $n=1$, we have
$f_{1}=1+x+y+xy$ the constant term is $1=\dfrac{1}{2}\binom{2}{1}$
for $n=2$, we have
$$f_{2}=(1+x+y+xy)(1+x+y+xy)=1+x+y+xy+x+x^2+xy+x^2y+y+yx+y^2+yxy+xy+xyx+xy^2+xyxy=1+x+y+xy+x+1+xy+y+y+yx+1+yxy+xy+xyx+x+xyxy=3+3x+3y+3xy+yx+yxy+xyx+xyxy$$ the term is $3=\dfrac{1}{2}\binom{4}{2}$
for $n=3$,we have $$f_{3}=f_{2}(1+x+y+xy)=(3+3x+3y+3xy+yx+yxy+xyx+xyxy)(1+x+y+xy)$$ the constant term is $$3+3x^2+3y^2+yxxy=3+3+3+yy=3+3+3+1=10=\dfrac{1}{2}\binom{6}{3}$$
I tink this problem very interesting,But maybe use induction to prove it?I can't it 
 A: Let $R$ be algebra generated over $\mathbb{Z}$ by non-commuting variables $x$, $y$, subject to $x^2=y^2=1$. There is an algebra homomorphism $\varphi:R\to M_2(\mathbb{Z}[t,t^{-1}])$ given by
$$
x\mapsto \begin{bmatrix}0&1\\1&0\end{bmatrix},\hspace{10mm}y\mapsto \begin{bmatrix}0&t^{-1}\\t&0\end{bmatrix}.
$$
I claim that $\varphi$ is injective. To check this, note that there is a $\mathbb{Z}$-basis for $R$ consisting of $(xy)^n$ and $x(xy)^n$ for $n\in\mathbb{Z}$, and observe that
$$
\varphi((xy)^n)=\begin{bmatrix}t^{n}&0\\0&t^{-n}\end{bmatrix},\hspace{10mm}\varphi(x(xy)^n)=\begin{bmatrix}0&t^{-n}\\t^{n}&0\end{bmatrix}
$$
are $\mathbb{Z}$-linearly independent.
Now, we have
$$
\varphi(1+x+y+xy)=\begin{bmatrix}1+t&1+t^{-1}\\1+t&1+t^{-1}\end{bmatrix}=(1+t)\begin{bmatrix}1&t^{-1}\\1&t^{-1}\end{bmatrix}.
$$
It is easy to check by induction that
$$
\begin{bmatrix}1&t^{-1}\\1&t^{-1}\end{bmatrix}^n = (1+t^{-1})^{n-1}\begin{bmatrix}1&t^{-1}\\1&t^{-1}\end{bmatrix},
$$
so we get
$$
\varphi\big((1+x+y+xy)^n\big)=(1+t)^n (1+t^{-1})^{n-1}\begin{bmatrix}1&t^{-1}\\1&t^{-1}\end{bmatrix}=t^{-n+1}(1+t)^{2n-1}\begin{bmatrix}1&t^{-1}\\1&t^{-1}\end{bmatrix}.
$$
The constant coefficient of $(1+x+y+xy)^n$ is the coefficient of $1$ in the upper left entry of the matrix above, which is
$$
{2n-1\choose n-1}=\frac{1}{2}{2n\choose n}.
$$
