Suppose you’re working on an algebraic expression that involves variables, addition, multiplication, and parentheses. You try repeatedly to expand it using the distributive law.
How do you know that the expression won’t continue to expand forever?
For example, expanding
(x + y)(s(u + v) + t)
gives
x(s(u + v) + t) + y(s(u + v) + t),
which has more parentheses than the original expression.
Starting with the innermost multiplication, when expanded it produces a*b terms at most, where a and b are the numbers of terms in the two multiplicands, to be added to the number of terms in the rest of the innermost parentheses. Do this separately for each innermost (or locally innermost) multiplication and then addition. You will eventually stop.
Alternative proof:
The most terms you could have at the end is 2^n, where n is the number of letters. In the first, unexpanded, example given, n = 6. When already partially expanded, as in the second expression given n is larger, as we count each occurrence of a given letter (to account for the ultimate possibility of square, cube, etc. factors) and thus 2^n is larger, but we know that it's still true that in this case the number of terms must still be 2 to the original n or less, as that is a tighter restriction on what the number of terms can be. In any case it is finite.
Actually it's always less than 2^n if we also count constants in the count of "variables", as no term will lack all of these pieces.
So we predicted less than 64:
(x+y)(su+sv+t)
xsu+xsv+xt + ysu+ysv+yt
Just 6 terms--indeed less than 64.
|
|
Posted by Charlie
on 2017-04-13 10:03:35 |
Two proposed proofs
