Monday, August 14, 2017

sequences and series - Polynomial for product over a set


Conjecture:
If $A$ is a nonempty, finite set with size $|A|=n$, and
$$P_A(x)=\prod_{a\in A}(x-a),$$

then $P_A(x)$ can be expanded as
$$P_A(x)=\sum_{k=0}^{n}(-1)^{n-k}x^k\sum_{{U\subseteq A}\atop{|U|=n-k}}\prod_{u\in U}u.\tag{1}$$




I have conjectured this based on algebraic evidence. That is, I expanded out the cases $n=1,...,4$ both manually and through $(1)$, and in each case the conjecture held. The problem is, I'm having difficulty proving this result. I'm fairly certain that a proof would involve induction, but I'm not very good at that, and have so far failed.



I was initially interested in this formula because I recognized that $(1)$ would imply that
$$k\ne0,n\iff \sum_{{U\subseteq S_n}\atop{|U|=k}}\prod_{u\in U}u=0\tag{2}$$
for
$$S_n=\left\{\exp\frac{2\pi ik}{n}:k=0,1,...,n-1\right\}.$$

It may seem un-intuitive at first, but $(2)$ is true because
$$P_{S_n}(x)=x^n-1,$$
(as $S_n$ is the set of roots of $x^n-1$) so each term of the expansion must vanish except for the cases $k=0,n$.



After seeing this, I was naturally curious about a proof of $(1)$. Could I have some help or hints? Thanks.

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...