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)
x(s(u + v) + t) + y(s(u + v) + t),
which has more parentheses than the original expression.
For any expression, construct an array of counts where the nth element (counting from the RIGHT) counts the number of products with exactly n parentheticals in the expression. For the example given, that looks like: [1, 1] -- s(u+v) is a product with 1 parenthetical, and (x+y)( stuff ) is a product with 2 parentheticals.
An example like (x+y)(a+b)(c + d(e+f)) would have an array like [1,0,1] in the same way.
If I pick any case where I can apply the distributive property and do so, I decrease one element of the array, and then increase the next lower element by twice however many added terms are in the second term less one. In the example given, when we go from (x+y)(s(u+v) + t) to x(s(u+v)+t) + y(s(u+v) + t) then the array goes from [1,1] to [0,4], increasing the next term by 3 because s(u+v)+t has two terms. [The exact size of the increase is irrelevent, only the fact that the increase is to the next lower term matters.]
If instead we had expanded s(u+v) first, we'd have (x+y)(su + sv + t) and the array would become [1,0]. If there is no "next lower element" then nothing increases from the operation.
Let's define "less than" in the context of comparing arrays so that a < b if in the first element left to right where a and b differ then a's element < b's element. (you might also imagine the array as digits in a Base-N number where N is something larger than the maximum count, which would give the same meaning to "less than".
The key then is to see that no matter which place we choose to apply the distributive property, the change to the array results in a strictly smaller array. Since each operation reduces the array, and since when there are no parentheticals at all the array is all zeros, after a finite number of operations the array must reach all zeros and there must be an end to the expansion.
Posted by Paul
on 2017-04-13 12:25:16