0
$\begingroup$

Is there a formula for the coefficients of $x^n$ for

$$ \prod_{i=1}^N(x+x_i) $$

in terms of $x_i$?

$\endgroup$
1
  • 2
    $\begingroup$ Do you know what Vieta's formulas are? $\endgroup$
    – Calvin Lin
    Commented Sep 21, 2013 at 18:45

3 Answers 3

3
$\begingroup$

The coefficient of $x$ is $$\sum_{k=1}^N\prod_{\substack{i=1\\i\ne k}}^N x_i$$

and to see how we find this formula just expand by choosing one $x$ from one factor and the $x_i$ from the other $$(\color{red}{x}+x_1)(x+\color{red}{x_2})\cdots(x+\color{red}{x_n})$$ and repeat the same thing for all the factors.

Added By the same method we have the coefficient of $x^n$ $$\sum_{1\leq i_1<i_2<\cdots<i_{N-n}\le N}x_{i_1}x_{i_2}\cdots x_{i_{N-n}}$$

$\endgroup$
3
  • $\begingroup$ I'm trying to write a computer code to generate the coefficients given a list of $x_i$ as input, so is there simpler way to do that other than explicitly calculating the above formula using loops? $\endgroup$ Commented Sep 21, 2013 at 18:59
  • $\begingroup$ Simpler than that?! $\endgroup$
    – DonAntonio
    Commented Sep 21, 2013 at 19:01
  • $\begingroup$ @DonAntonio sorry, there was a typo in the question. I mean the coefficients of $x^0,x^1,x^2...$, not just $x^1$, I've corrected that. $\endgroup$ Commented Sep 21, 2013 at 19:07
1
$\begingroup$

Another approach that might be easier to program:

Let's call your function $f(x)$. We know it's a polynomial of degree $n$, so it can be written in the form $p(x) = \sum_{i=0}^n a_ix^i$. Choose $n+1$ values $z_0, \ldots, z_n$. By equating values of $f$ and $p$ at $x = z_0, \ldots, z_n$, we get a system of $n+1$ linear equations $$ \sum_{i=0}^n a_iz_j^i = f(z_j) \quad (j=0,1,\ldots,n) $$ Solve this linear system to get $a_0, \ldots, a_n$.

If you already have (or can find) a function to solve a system of linear equations, then there's not much code for you to write.

The numerical conditioning of the system of equations is bad, so be careful. It can be improved by judicious choice of $z_0, \ldots, z_n$. Certainly you should not try to compute the inverse of the coefficient matrix. If you're interested in this approach, and you need more details, please feel free to ask again.

$\endgroup$
0
$\begingroup$

$$ \begin{align} & \phantom{{}={}} (x+x_1)(x+x_2)(x+x_3)(x+x_4) \\[12pt] & = x^4 & \text{(all size-0 subsets)} \\ & \phantom{=} {} + (x_1+x_2+x_3+x_4) x^3 & \text{(all size-1 subsets)} \\ & \phantom{=} {} + (x_1 x_2 + x_1 x_3 + x_1 x_4 + x_2 x_3 + x_2 x_4 + x_3 x_4) x^2 & \text{(all size-2 subsets)} \\ & \phantom{=} {} + (x_1 x_2 x_3 + x_1 x_2 x_4 + x_1 x_3 x_4 + x_2 x_3 x_4) x & \text{(all size-3 subsets)} \\ & \phantom{=} {} + (x_1 x_2 x_3 x_ 4) & \text{(all size-4 subsets)} \end{align} $$ The "subsets" referred to are subset of the set $\{x_1,x_2,x_3,x_4\}$.

A similar thing works when the number of members of this last-mentioned set is something other than four.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .