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