The Polynomials $P_n(x+y)$

Question

Let $$\displaystyle P_n(x) = \sum_{k=0}^n \binom{n}{k}x^k.$$

We need to show that $$P_n(x+y) = \sum_{k=0}^n\binom{n}{k}P_k(x)y^{n-k}.$$ In the proof, we have $$\begin{array}{rcl} P_n(x+y) &=& \displaystyle\sum_{k=0}^n \binom{n}{k}(x+y)^k\\ &=& \displaystyle\sum_{k=0}^n \binom{n}{k}\sum_{i=0}^k\binom{k}{i}x^iy^{k-i}\\ &=& \displaystyle\sum_{k=0}^n \sum_{i=0}^k\binom{n}{k}\binom{k}{i}x^iy^{k-i}. \end{array}$$ What to do next knowing that $\displaystyle\sum_{k=0}^n\binom{n}{k}P_k(x)y^{n-k} = \sum_{k=0}^n \sum_{i=0}^k\binom{n}{k}\binom{k}{i}x^iy^{n-k}?$

Answer 1

If we already know that $P_{n}(x)=(1+x)^{n}$ then it is straightforward

$$ \begin{aligned} P_{n}(x+y)&=((1+x)+y)^{n}\\ &=\sum_{k=0}^{n}{\binom{n}{k}(1+x)^{k}y^{n-k}}\\ &=\sum_{k=0}^{n}{\binom{n}{k}P_{k}(x)y^{n-k}} \end{aligned} $$

Answer 2

I will give you some hints on how I would prove the equality that you need to show. First prove that $$P_{n+1}(x) = (1+x) \cdot P_n(x).$$ You can show this directly.

With that equality in the bag we can prove your main equality with induction. So suppose that it is true for $n$. Then \begin{align*} P_{n+1}(x+y) &= (1+x+y) \cdot P_n(x+y) \\ &= (1+x+y) \cdot \sum_{k=0}^n \binom{n}{k} P_k(x) y^{n-k} \\ &= \sum_{k=0}^n\left[ \binom{n}{k} (1+x) P_k(x) y^{n-k} + \binom{n}{k} P_k(x) y^{n+1-k}\right] \\ &= \sum_{k=0}^n\left[ \binom{n}{k} P_{k+1}(x) y^{n-k} + \binom{n}{k} P_k(x) y^{n+1-k}\right] \\ &= \sum_{k=0}^{n+1}\left(\binom{n}{k-1} + \binom{n}{k}\right) P_{k}(x) y^{n+1-k}\\ &= \sum_{k=0}^{n+1}\binom{n+1}{k} P_{k}(x) y^{n+1-k}. \end{align*} This is what you wanted to show. I will let you fill in the details on some of these equalities yourself. And don't forget the base case.