Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
5  
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
add comment

2 Answers

up vote 5 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.