证明子序列长度为至少是n当且仅当序列是这样的()()...()[],一个()是一次1..m都出现的序列，共n个。
必要性。数学归纳法。n>=1是，序列显然是()[]，假设n>=k是，序列是k个()+[]，如果n>=k+1，取第k个()的最后一个素，这个元素在长度为k的某个子序列中一定会用到，如果用不到就把它放到[]中去，这样做第k个()仍然是一次1..m都出现的序列，再取前一个元素，由归纳假设保证第k个()中一定有一个元素满足要求，由于n>=k+1，所以在这个元素之后必然会出现1..m的所有元素一次，所以[]=()[]'
充分性。太显然了，没什么证的。

• 多谢精彩论证，做学问就应当严谨！！ (0) 200593141 2007-08-29 19:16:19
• 弱弱的还是不明白…… (289) kathycat 2008-11-06 20:39:31
• Re:写个证明 (3) tanghaibao 2008-12-29 01:23:52