# 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.

-
You don't need to induct. Examine the coefficient of $x^i$: how can you make an $x^i$ from terms in $p(x)$ and $q(x)$? – KReiser Aug 6 '12 at 7:25

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}$$

-
I had drawn tables of the sums the equality of which I was attempting to prove, but your answer demonstrated how to visualize the indexing that was necessary to complete a proof without induction. I don't think that infinite sums are necessary for the proof, however; I was able to apply your technique to finite sums with additional zero coefficients. – danportin Aug 7 '12 at 9:16
@danportin Re: infinite sums, I totally understand. I find it nicer not to have to do any direct figuring with the upper limits of the sums. For me it's not that the infinite sums are unnecessary, it's that the more tedious finite sums are unnecessary. Different points of view! – alex.jordan Aug 8 '12 at 0:50

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.

-