Continue with recursive definitions.

Assume that
max(a,b) is defined. Then define max(a_{1},a_{2},¼,a_{n}) by

max(a_{1}) = a_{1}

and max(a_{1},a_{2},¼,a_{n}) = max(max(a_{1},a_{2},¼,a_{n-1}),a_{n}).

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 T

On 7 Nov 2000, 12:38.