Let $ A := \mathbb{C}\langle x, y \rangle / ( xy-2 ) $ where $ \mathbb{C}\langle x, y \rangle $ is the free (non-commuative) $ \mathbb{C} $-algebra which is generated by $ x $ and $ y $ and $ ( xy-2 ) $ is the two-sided ideal which generated by the element $ xy-2 $.


Let us also write $ x $ resp. $ y $ for the classes of $ x $ resp. $ y $ in $ A $. Clearly, the elements $ y^k x^l $ form a basis of $ A $ for $ k, l \in \mathbb{N}\_0 $. Therefore, there is a presentation
$$ ( x + y )^n = \sum\_{k + l = 0, \dots, n} c\_{k,l}^{(n)} y^k x^l $$
for any $ n \in \mathbb N\_0 $.


**Questions:**
I am interested in the sum of these coefficients, i.e.
$$ S\_n = \sum\_{k, l} c\_{k,l}^{(n)}. $$


1. Is there a general method to compute powers of sums in such algebras?
2. What can be more said about the asymptotic behaviour of $ S\_n $ except for the obvious bounds in $(\*)$?
3. Does anybody know a context in which this algebra (or more generally the algebra $ \mathbb C\langle x, y \rangle / ( xy - a ) $ for $ a \in \mathbb N $) plays a role?


**Known and maybe helpful:**
As we have two choices in each of the $ n $ factors in $ ( x + y )^n $, (without using the relation $ xy = 2 $) we already count at least $ 2^n $ $ ( x, y ) $-monomials. Moreover, applying the relation $ xy = 2 $ only doubles the coefficient of any of these $ 2^n $ monomials. This provides the lower bound $ 2^n $ for $ S\_n $.
One the other hand, mapping $ ( x, y ) \mapsto (\sqrt 2, \sqrt 2) $ yields a morphism $ A \to \mathbb{C} $ of $ \mathbb C $-algebras and gives the upper bound $ 2^{3n/2} $. So, we have the bounds
\begin{align} 2^n \le S\_n \le 2^{3n/2}. (\*) \end{align}
Furthermore, with some more effort one can show $ S\_n \ll 2^{3n/2} / \sqrt n $ asymptotically as $ n \to \infty $. Anyway, I have the feeling that $ 2^{3n/2} $ is not far off, in the sense that $ (2^{3/2}-\varepsilon)^n / S\_n \to 0 $ for any $ \varepsilon > 0 $.


**Approach:**
Let $ \mathbb C^{ \mathbb N } $ be the vector space of sequences with elements in $ \mathbb C $ and $ L, R \in \operatorname{End}\_{\mathbb C}( \mathbb C^{ \mathbb N } ) $ be the backward and forward shifts. Then the algebra $ A $ is isomorphic to the sub algebra $ B := \mathbb C\langle L, R \rangle $ of $ \operatorname{End}\_{\mathbb C}( \mathbb C^{ \mathbb N } ) $ (consider the map $ ( x, y ) \mapsto ( 2 L, R ) $). I seems to be possible to get $ S\_n $ by the action of $ B $ on $ \mathbb C^{\mathbb N } $. But it is computationally involved and unclear whether the so obtained presentation of the $ S\_n $ is useful.


**Edit**
As suggested in the comments, here are some additional information which were computed by using MAGMA: For $ n = 0, \dots, 15 $, the values of $ S\_n $ are
$$ [ 1, 2, 5, 12, 31, 78, 205, 528, 1403, 3666, 9817, 25908, 69783, 185526, 502005, 1342296 ] $$
and, for $ n = 0, \dots, 5 $ the desired presentations of $ ( x + y )^n $ are
$ [
 1, \\
 x + y, \\
 x^2 + y\*x + y^2 + 2, \\
 x^3 + y\*x^2 + y^2\*x + y^3 + 4\*x + 4\*y, \\
 x^4 + y\*x^3 + y^2\*x^2 + y^3\*x + y^4 + 6\*x^2 + 6\*y\*x + 6\*y^2 + 8, \\
 x^5 + y\*x^4 + y^2\*x^3 + y^3\*x^2 + y^4\*x + y^5 + 8\*x^3 + 8\*y\*x^2 + 8\*y^2\*x + 8\*y^3 + 20\*x + 20\*y
] .$



A power of a sum in a non-commutative algebra
Consider the sum of the coefficients of the degree-$(n-2k)$ "reduced" monomials $y^ix^j$ in $(x+y)^n$. The degree of a reduced monomial always differs from $n$ by an even number, so this will capture everything. This is clearly of the form $2^k\cdot T(n,k)$ for some unknown function $T$, since each time you reduce the product $xy$ you pick up a factor of $2$. So your sum $S\_n$ equals $\sum\_{k=0}^{\lfloor n/2 \rfloor} 2^k\cdot T(n,k)$.


Now, I claim that $T(n,k)$ is given by A298637 on the OEIS. This is basically immediate from the definition. From the explicit formula given there, we have $$T(n,k) = \frac{(n+1-2k)^2}{n+1}\binom{n+1}{k}$$
so that
$$S\_n = \sum\_{k=0}^{\lfloor n/2 \rfloor} 2^k\cdot \frac{(n+1-2k)^2}{n+1}\binom{n+1}{k}$$
By considering the contribution to the sum for $k=\lfloor n/2 \rfloor$ we see that this equals $2^{3n/2 - o(1)}$, confirming your suspicion.


