Finding coefficient of $x^k$ in a product of two polynomials

Question

Let $a(x)= a_{0}+a_{1}x+a_{2}x^2+...+a_{n}x^n$ and $b(x)= b_{0}+b_{1}x+b_{2}x^2+...+b_{m}x^m$ be two polynomials. Write down a formula for the coefficient of $x^k$ in the product $a(x)b(x)$, where $0 ≤ k ≤ n + m.$

I noticed the coefficient is always the sum of products of these coefficients whose powers sum to $k$, so for example for two polynomials $(2+5x+7x^2)$ and $(9+2x+3x^2)$ the coefficient of $x^2$ is $3\times2+5\times2+7\times9=79$. So to generalize this observation for the product of $a(x)b(x)$, in order to get a coefficient of $x^k$, we would need a sum of products whose subscripts sum to $k$. For example, the coefficient of $x^4$ in $a(x)b(x)$ would be $a_{4}b_{0}+a_{3}b_{1}+a_{2}b_{2}+a_{1}b_{3}+a_{0}b_{4}$.

However, the question asks for a specific formula, whereas I have found only a pattern which needs more concise form. How to go about finding the actual formula?

Answer 1

You are in the correct way to get the desired formula:

$$\left(\sum_{i=0}^m a_ix^i\right) \left(\sum_{j=0}^n b_jx^j\right)=\sum_{k=0}^{m+n}\left(\sum_{i+j=k} a_ib_j\right)x^k$$

Answer 2

$\sum_{i=0}^{k}a_{i}b_{k-i}$ where $a_{i} = 0$ and $b_{i} = 0$ for $i\gt n$ or $i\lt 0$.

This operation is known as Discrete Convolution and can be performed faster by methods such as Fast Fourier Transform(FFT).

Answer 3

You are right. You can write it in the following:

$$a(x)b(x)=\sum_{i=0}^{n+m}\left(\sum_{j=0}^ia_{j}b_{i-j}\right)x^i$$