1. Consider palindromes that consist only of lowercase letters, such as “level” and “deed,” but not “RadaR,” “ADA,” or “101.” Let c ( n ) be the number of palindromes of length n . a. Write a...

1. Consider palindromes that consist only of lowercase letters, such as “level” and “deed,” but not “RadaR,” “ADA,” or “101.” Let c ( n ) be the number of palindromes of length n .

a. Write a recursive definition of c ( n ).

b. Prove that your answer to part a is correct by using mathematical induction.

2. Prove the following for single-letter operands: If E is a prefix expression and Y is a nonempty string of nonblank characters, then E Y cannot be a legal prefix expression. ( Hint: Use a proof by induction on the length of E .)