0
$\begingroup$

Let $f(x)=a_{0}+\cdots+a_{m}x^{m}$ and $g(x)=b_{0}+\cdots+b_{n}x^{n}$. Polynomial multiplication is defined by $$f(x)g(x)=d_{0}+d_{1}x+\cdots+d_{n}x^{n}$$ where $d=\sum_{i=0}^{n}a_{i}b_{n-i}$. Intuitively, the leading term of $f(x)g(x)$ is $a_{m}b_{n}x^{m+n}$. But using the formula, $$d_{n}=\sum_{i=0}^{m+n}a_{i}b_{m+n-i}.$$ This suggests that $$\sum_{i=0}^{m+n}a_{i}b_{m+n-i}=a_{m}b_{n}.$$ How do I prove this?

$\endgroup$
0

2 Answers 2

1
$\begingroup$

The “convolution formula” $$ d_k = \sum_{i=0}^{k}a_{i}b_{k-i} $$ for the coefficients of the product of $$ f(x)=a_{0}+\cdots+a_{m}x^{m} \\ g(x)=b_{0}+\cdots+b_{n}x^{n} $$ requires that we define $a_i = 0$ for $i > m$ and $b_j = 0$ for $j > n$. Then $$ \sum_{i=0}^{m+n}a_{i}b_{m+n-i}=a_{m}b_{n} $$ holds because in the sum all terms with $i \ne m$ vanish.

$\endgroup$
0
$\begingroup$

Calling

$$ \left(\sum_{k=0}^m a_k x^k\right)\left(\sum_{j=0}^n b_j x^j\right) = \sum_{k=0}^m\sum_{j=0}^n a_k b_j x^{k+j} $$

making now

$\nu = j + k$ we have

$$ \sum_{k=0}^m\sum_{j=0}^n a_k b_j x^{k+j} = \sum_{\nu}^m\sum_{k=0}^{\nu}a_k b_{\nu-k}x^{\nu}\Rightarrow d_{\nu} = \sum_{k=0}^{\nu}a_k b_{\nu-k} $$

NOTE

This summation is performed over a rectangular lattice so care should be taken at the limits. This operation is known as convolution.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .