A polynomial in x has m nonzero terms. Another polynomial in x has n nonzero terms where m < n. These polynomials are multiplied and all like terms are combined. The resulting polynomial in x has a maximum of how many nonzero terms?
The answer shows mn but why??
The correct answer IS indeed mn. For example, we might have:
f(x) = x^{2}+x+1
g(x) = x^{6}+x^{3}+1, in which case:
f(x)g(x) = x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1, which has 9 = 3*3 terms
(it might not be possible to "combine and simplify", because there may be NO "overlap" of equal terms of x^{k}, for any given k).
The general formula for polynomial multiplication is:
So it is tempting to think that the number of terms will not exceed m+n, but in the formula above, the number of 0 terms in the first polynomial could be fairly large, with just enough "gaps" in the non-zero terms to completely put a polynomial with the number of terms in the second polynomial "in the gaps".
As is easily verifed (you can use induction), the number of possible terms (with NO combining of "like terms", which may not exist) of a product of a sum with m summands, and a sum with n summands, is a sum with mn summnads.
Yes, I was thinking the same thing. If f(x) is a polynomial, let terms(f) denote the number of nonzero terms in f(x). I believe the statement says: For all polynomials f and g, if terms(f) < terms(g), then terms(fg) <= terms(f)terms(g), and this upper bound is sharp, i.e., the inequality turns into an equality (only) for some f, g. The fact that the inequality is strict for some f and g or even for some classes of polynomials does not refute this statement.
Show that the product of two polynomials with m and n terms, respectively, has <= mn terms. This is easy if you know how polynomials are multiplied. Then note Deveno's example where the product, after adding like terms, has exactly mn terms. Thus, saying that the product has < mn terms (instead of <= mn terms) is incorrect. So, the maximum number of terms in a product is mn. This maximum is achieved for some pairs of polynomials, and for other pairs (as in topsquark's example) it is not.
Now that I have read the whole problem...
Think of the distributive law: a(b + c) = ab + ac.
Now for an example: Say your first polynomial has two terms (m = 2), ax^p + bx^q, and your second polynomial has three terms (n = 3), cx^r + dx^s + ex^t. Then
So there will be m terms that distribute and, one at a time, multiplies the n terms. So before simplification we have mn terms. (Simplifying will merely reduce the number of terms to less than mn.)
Can you work this into a proof?
-Dan
Simply, in the most general case, in the most suitable conditions, each term in one of the polynomials can generate a term for each term in the other polynomial, as though you were talking about ordered pairs. So you just multiply the two.
It is easy to show that one can always pick a polynomial g(x) with n non-zero terms given a polynomial f(x) with m non-zero terms such f(x)g(x) has mn non-zero terms.
Suppose f(x) = c_{1}x^{k1} + c_{2}x^{k2} +...+ c_{m}x^{km}, where k_{1} < k_{2} <...< k_{m}, c_{j} ≠ 0.
Let g(x) = 1 + x^{km+1} + x^{2km+2} +...+ x^{(n-1)km+n-1}, for any n > m, which clearly has n non-zero terms.
then f(x)g(x) = f(x) + (x^{km+1})(f(x)) + (x^{2km+2})(f(x)) +....+ (x^{(n-1)km+n-1})(f(x)).
The highest term of x^{jkm+j}(f(x)) (for j = 0,1,...,n-2) is some (constant) multiple of x^{jkm+j+km} = x^{(j+1)km+j}, whereas the lowest term of
x^{(j+1)km+(j+1)}(f(x)) is some (constant) multiple of x^{(j+1)km+(j+1)+k1}, and:
(j+1)k_{m}+j < (j+1)k_{m}+(j+1) ≤ (j+1)k_{m}+(j+1)+k_{1}.
Now all theses j's and k's might be confusing. Here is a concrete example:
Suppose f(x) = 1 + 3x^{3} + 2x^{5} (3 non-zero terms). To find a polynomial g(x) with 4 non-zero terms we pick:
g(x) = 1 + x^{6} + x^{12} + x^{18}.
Then f(x)g(x) = (1 + 3x^{3} + 2x^{5}) + x^{6}(1 + 3x^{3} + 2x^{5}) + x^{12}(1 + 3x^{3} + 2x^{5}) + x^{18}(1 + 3x^{3} + 2x^{5})
As you can see the highest power of x in each grouping is less than the lowest power of x in the next grouping, so we will have 12 non-zero terms.
On the other hand, for ANY sum (polynomial or not) with m terms, say:
S = A_{1}+...+A_{m}, and ANY sum with n terms, say T = B_{1}+...+B_{n}
ST = A_{1}(B_{1}+...+B_{n}) + A_{2}(B_{1}+...+B_{n}) +...+ A_{m}(B_{1}+...+B_{n})
= A_{1}B_{1}+...+ A_{1}B_{n} +...+A_{m}B_{1}+...+A_{m}B_{n}, which has mn terms (before simplification).
So the largest possible number of terms is mn, and this bound is indeed reached (for some polynomial products).