4
$\begingroup$

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,

  • 3
    [tag: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.2011-11-25
  • 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.)2011-11-25
  • 0
    Everyone is considering *commutative* algebras here...2011-11-26

2 Answers 2

5

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.

  • 0
    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...2011-11-26
  • 0
    @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.2011-11-27
  • 0
    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!2011-11-27
4

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?

  • 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?2011-11-25
  • 0
    @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.2011-11-25
  • 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.2011-11-25
  • 0
    @QiaochuYuan: But surely you cannot invoke the combinatorial interpretation in order to establish it as a polynomial identity...2011-11-25
  • 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).2011-11-25
  • 0
    @QiaochuYuan: Ah, fair enough. Thanks!2011-11-25
  • 0
    @Qiaochu Yuan: So, are you saying that it holds with the assumption that $A$ is an associative and commutative $Q$-algebra?2011-11-26
  • 0
    @user2764: yes.2011-11-26
  • 0
    @QiaochuYuan: I don't see how to proceed by induction in this case. In the case of natural numbers we have to divide by expressions involving $x$ and $y$ at some point. But here we can't... So, what is the procedure to show the formula above?2011-11-26
  • 0
    @user2764: the argument is not by induction. I'll write up a separate answer.2011-11-26
  • 0
    @Qiaochu Yuan: THANKS. I will appreciate too much.2011-11-26