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.