November 6 November 6


Continue with recursive definitions.
Assume that max(a,b) is defined. Then define max(a1,a2,,an) by
max(a1) = a1
and max(a1,a2,,an) = max(max(a1,a2,,an-1),an).
Here is a recursive definition of the set of bit strings which are palindromes.
l, the empty string, is a palindrome.
x where x is any symbol (in our case 0 or 1) is a palindrome.
If a is a palindrome and x a symbol then xax is a palindrome.
Recursive definitions and proof by induction go well together.
Define B, the set of balanced strings of parentheses, be defined by
l B.
If x B then (x) B.
If x B and y B then xy B.
The proof proceeds by induction on the length of the string. (Note that length is also defined inductively.)
For the base case note that the number of left parentheses of l is 0 and this is the number of right parentheses of l as well.
Assume that the result holds for all balanced parentheses of length less than or equal to n. If there is a balanced string of length n+1 it is either of the form (x) with x of length n-1 or xy with both x and y of length less than n. In either case the number of left parentheses is verified to be equal to the number of right parentheses.


File translated from TEX by TTH, version 2.60.
On 7 Nov 2000, 12:38.