Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question
3  
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
1  
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
add comment

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
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
add comment

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?

share|improve this answer
2  
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
5  
@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
3  
@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
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.