For Exercises 52–62, refer to the following. Call a sequence musical if repeatedly applying deflation to it eventually results in a single .
57. Show that apart from the lone sequence , every musical sequence is an initial subsequence of all the musical sequences that are successive inflations of it.
57.
It suffices to show that every musical sequence is an initial subsequence of its inflation. Note that for any musical sequence except , its inflation is longer; and for any except , its deflation is shorter. Let be the shortest musical sequence that is not an initial subsequence of its inflation . Now by hypothesis is not ; nor can be , because the inflation of is . Since is neither nor , it can be deflated and the deflation is shorter. Because is shorter than , is an initial subsequence of . But under inflation of to , the initial part of that is inflates to all of , followed by inflation of the rest of . Hence, is an initial subsequence of , contrary to the supposition that it isn’t.