Product of Polynomials If $p$ is a polynomial of degree $n$ and $q$ is a polynomial of degree $m$, then their product $p \cdot q$ is given by:
  $$ (p \cdot q)(x) = \sum_{i = 0}^{n + m} \left ( \sum_{k = 0}^i p_k q_{i - k} \right ) x^i $$
where $p_i$ and $q_i$ denote the $i$th coefficient of $p$ and $q$, respectively. I am having trouble proving that $p \cdot q$ is, indeed, subject to this identity. I have attempted to prove the identity by induction on the degree of one of the polynomials, but am having trouble completing the proof. My trouble arises when I distribute sums in the inductive step of the proof. I assume the proof is relatively simple, and I am overlooking something simple. I would appreciate some help in this regard. Here, the polynomials are real-valued.
 A: It's all about reindexing. Also, a helpful trick is to treat the polynomials as having infinitely many terms, most of which have $0$ as the coefficient.
$$\left(\sum_{k=0}^{\infty}p_kx^k\right)\left(\sum_{j=0}^{\infty}q_jx^j\right)=\sum_{k=0}^{\infty}\sum_{j=0}^{\infty}p_kq_jx^{k+j}$$
Now reindex by replacing all $j$'s with $i-k$.
$$=\sum_{k=0}^{\infty}\sum_{i-k=0}^{\infty}p_kq_{i-k}x^{k+i-k}$$
$$=\sum_{k=0}^{\infty}\sum_{i=k}^{\infty}p_kq_{i-k}x^{i}$$
And switch the order of summation by visualizing the pairs $(i,k)$ that you are summing over, using an $i$-axis and a $k$ axis:
$$\begin{array}{ccccccc}
\uparrow i&\vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\
&\blacksquare & \blacksquare &\blacksquare &\blacksquare &\blacksquare\\
&\blacksquare & \blacksquare &\blacksquare &\blacksquare &\\
&\blacksquare & \blacksquare &\blacksquare & &\\
&\blacksquare & \blacksquare & & &\\
&\blacksquare &  & & & &\rightarrow k
\end{array}$$
$$=\sum_{i=0}^{\infty}\sum_{k=0}^{i}p_kq_{i-k}x^{i}$$
A: Here's a slightly different point of view which might clarify things.
Pretend first to multiply $p(x)*q(y)$ (different variables!). You get
$$
p(x)q(y)=\sum_{i=0}^n\sum_{j=0}^mp_iq_jx^iy^j.
$$
Now set $x=y$. Since $x^ix^j=x^k$ if and only if $i+j=k$ you can rearrange the above sum as
$$
p(x)q(x)=\sum_{k=0}^{m+n}\big(\sum_{i+j=k}p_iq_j\big)x^k.
$$
Finally, $i+j=k$ if and only if $j=k-i$, thus you can rewrite the inner sum as $\sum_{i=0}^kp_iq_{k-i}$ which is the formula you want.
