Prove the value of the $k$th symmetric sum via induction

188 Views Asked by At

Define the $k$th symmetric sum of a polynomial with $n$ roots as the sum of all products formed by multiplying $k$ of the roots. For example, if the $3$ roots of $f(x)$ were $1,2,$ and $3$, the $2$nd symmetric sum of that polynomial would be $$1\times2+1\times3+2\times3=11$$

Prove by induction that the $k$th symmetric sum is $$(-1)^ka_{n-k}/a_n$$

I know that given a polynomial $f(x)=a_nx^n+a_{n-1}x^{n-1}+\dots+a_1x+a_0,$ the sum of its roots is $\frac{-a_{n-1}}{a_n}$ and the product of its roots is $\frac{-a_0}{a_n}$, and thus I can do the base case. I don't know how to continue, however.

1

There are 1 best solutions below

0
On

What you are refering are known as Vieta's Fromulas.

It can be proven by noticing that we have:

$$a_nx^n + a_{n-1}x^{n-1} + \cdots + a_0 = f(x) = a_n(x-\alpha_1)(x-\alpha_2) \cdots (x-\alpha_n)$$

where $\alpha_i$ are the roots of $f$. Now expland the right side and compare the coefficients.


If you insist on having an inductional proof, the induction can be done on the degree of the polynomial. The base case is trivial and assume it's true for $\text{deg } f = n-1$. Then we have that:

$$a_nx^n + a_{n-1}x^{n-1} + \cdots + a_0 = f(x) = a_n(x-\alpha_1)(x-\alpha_2) \cdots (x-\alpha_n) = a_nf_{n-1}(x)(x- \alpha_n)$$

If $f_{n-1}(x) = x^{n-1} + b_{n-2}x^{n-2} + \cdots b_0$ then we have that $k$-th symmetric sum of $f$ is the sum of the $k$-th symmetric sum of $f_{n-1}$ and the $(k-1)$-th symmetric sum of $f_{n-1}$ times $\alpha_n$. Using the induction hypothesis we would be able to make the conclusion.