Call a polynomial P in the variablesx1,x2,...,xn symmetric if switching any of the variables leaves P unchanged. So for examplex12+x22+x32x1x2x3 is a symmetric polynomial inx1,x2,x3 but x1+2x2+3x3is not. A particular example of this are the power-sum symmetric polynomials defined as pk = i=1nxik. Show that any symmetric polynomial can be written as a polynomial in the power-sum symmetric polynomials. For example, if

P(x, y, z) =x12+x22+x32x1x2x3 , then P =p2p13/6+p1p2/2p3/3

. Hint: You will want to use induction, but not on the number of variables. Start with a polynomial P and find a way to add or subtract products of the power-sum polynomials to simplify it. Repeat this until there is nothing left.