# Binomials in associative algebras

Given any associative algebra $A$ over a field of characteristic zero, $x\in A$ and $k\in \mathbb Z_+$, set $\binom{x}{k} = \frac{x(x-1)\cdots(x-k+1)}{k!}$. It is not hard to see that is is still in $A$.

How to express $\binom{x+y}{k}$ in terms of a linear combination of products of $\binom{x}{m}$ and $\binom{y}{n}$ for appropriate $m,n\in \mathbb Z_+$ ?

Thanks,

-
algebra tag is not intended for questions concerning associative algebras. I changed it to abstract-algebra, if you have a better idea, please, change it to a more suitable tag. –  Martin Sleziak Nov 25 '11 at 21:29
I mean there is a trivial way to do this as a linear combination of products of ${x \choose 1}$ and ${y \choose 1}$. Do you want a stronger condition than this? When $x, y$ commute I think Dimitrije's answer is exactly what you want but I don't know if a reasonable answer exists in general. (Your condition on $A$ is also strange: it's actually more general to just say $\mathbb{Q}$-algebra.) –  Qiaochu Yuan Nov 25 '11 at 22:48
Everyone is considering commutative algebras here... –  Mariano Suárez-Alvarez Nov 26 '11 at 20:42

The argument I have in mind seems to be engendering some confusion, so I'll spell it out in full. The crucial lemma is the following.

Lemma: Suppose $P(x_1, ... x_n)$ is a polynomial. If $P(k_1, ... k_n) = 0$ for all non-negative integers $k_1, ... k_n$, then $P = 0$ identically.

Proof. We proceed by induction on $n$. The case $n = 1$ is obvious. In the general case, regard $P(x_1, ... x_n)$ as a polynomial in $x_n$ with coefficients in $F[x_1, ... x_{n-1}]$, so write $$P(x_1, ... x_n) = \sum_i P_i(x_1, ... x_{n-1}) x_n^i.$$

By fixing $x_1, ... x_{n-1}$ and varying $x_n$ we conclude that each of the polynomials $P_i(x_1, ... x_{n-1})$ satisfies $P_i(k_1, ... k_{n-1}) = 0$ for all non-negative integers $k_1, ... k_{n-1}$, and the result follows by induction.

Consider now the polynomial $$P(x, y) = {x + y \choose m} - \sum_{a=0}^m {x \choose a} {y \choose m-a}.$$

The combinatorial argument in Dimitrije Kostic's answer shows that $P(k_1, k_2) = 0$ for all non-negative integers $k_1, k_2$, and then the lemma above shows that $P = 0$ identically. In other words, $P(x, y) = 0$ in the universal commutative $\mathbb{Q}$-algebra generated by two generators $\mathbb{Q}[x, y]$, and so $P = 0$ for elements $x, y$ in any commutative $\mathbb{Q}$-algebra.

-
I still don't understand how you pass to $A$ from the situation with nonnegative integers. I understand the idea and the fact that $P(k_1,k_2)=0$ for all $k_1,k_2\in \mathbb Z_+$. But after you write "In other words" I am confused... –  Binai Nov 26 '11 at 20:57
@user2764: to prove that $P(x, y) = 0$ for elements $x, y$ in any commutative $\mathbb{Q}$-algebra it suffices to prove that $P(x, y) = 0$ in the subalgebra generated by $x, y$. This subalgebra is a quotient of $\mathbb{Q}[x, y]$, so it suffices to prove that $P(x, y) = 0$ in this ring, and this is equivalent to proving that $P = 0$ identically as a polynomial, which the Lemma accomplishes. –  Qiaochu Yuan Nov 27 '11 at 0:06
Ok, I got it... Thanks! Now I see why you mentioned combinatorial Nullstellensatz. When I read your proof at the first time, I was confused in what you took as the domain. Thanks again! –  Binai Nov 27 '11 at 5:45

There's a simple combinatorial formula. For all positive integers $x,y,m$ you have $$\binom{x+y}{m} = \sum_{l=0}^m \binom{x}{l} \binom{y}{m-l}$$ It's easy to prove. If you're choosing $m$ elements from a set of $x+y$ elements, you can do this by taking some number $l$ of them from among the first $x$ elements and then the remaining $m-l$ from the last $y$ elements. Could this be what you're looking for?

-
But here $x$ and $y$ are not necessarily integers: they are elements of an arbitrary associative algebra, so the combinatorial interpretation is no longer appropriate. Does the identity still hold when $x$ and $y$ are not integers? –  Arturo Magidin Nov 25 '11 at 21:47
@ArturoMagidin Oops, you're right. There's probably a similar identity in terms of gamma functions, and I doubt it's much harder to prove it. –  Dimitrije Kostic Nov 25 '11 at 21:52
@Arturo: for fixed $m$, this identity holds for non-negative integers $x, y$, hence it holds as a polynomial identity in variables $x$ and $y$ (for example by the combinatorial Nullstellensatz), hence it holds for elements $x, y$ of an arbitrary commutative algebra. –  Qiaochu Yuan Nov 25 '11 at 22:44
@QiaochuYuan: But surely you cannot invoke the combinatorial interpretation in order to establish it as a polynomial identity... –  Arturo Magidin Nov 25 '11 at 23:04
@Arturo: yes, you can. The combinatorial interpretation establishes it for non-negative integers $x, y$, and this is Zariski-dense (for example, again, by the combinatorial Nullstellensatz). –  Qiaochu Yuan Nov 25 '11 at 23:10