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.
Product of Polynomials
-
5You 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)$? – 2012-08-06
2 Answers
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}$
-
0@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! – 2012-08-08
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.