HW #11

Reminder: Each HW problem solution should consist of:

• a restatement of the entire problem (you may copy it word for word),
• followed by a complete solution with all intermediate steps shown.

All exercises are from §4.3 (recursive definitions and structural induction).

1. (3 points)

   p. 308: 4d

   • This gives you a recursively-defined function and asks you to compute some of its values.

   ---

2. (9 points)

   p. 308: 8d

   • This gives you an "explicit" formula for the nth term of a sequence and asks you to find a recursive definition of it.

   • Hint: Create a 2-column table, with one column for n and one column for a_n.
     Then look for a pattern that defines a_n as a function of a_n–1.

   • 3 points for table;
     3 points for base case of definition;
     3 points for recursive case of definition

   ---

3. (6 points)

   Give a recursive definition of the set of even negative integers.

   • 3 points for base case; 3 points for recursive case.

   ---

4. (6 points)

   Give a recursive definition of the set of positive integer powers of 2.

   • 3 points for base case; 3 points for recursive case.

   ---

5. (15 points)

   p. 309: 26a, c

   • This problem defines a set recursively.

   • Part (a) asks you to list some of its elements (3 points)

   • Part (c) asks you to use structural induction to prove a proposition about the set:
        3 points each for stating and proving the base case;
        3 points each for stating and proving the recursive case;
        total = 12 points.

   ---

   For problems 6, 7, and 8, first read the paragraph about Ackermann functions—which play an important role in the the theory of computation—on p. 310, beginning in the left column after problem #47 and ending in the right column just before problem #48.

   (You might also want to read the articles about it that you can access by linking to "Ackermann" and "function", above.)

   ---

6. (12 points)

   p. 310: 48a–d

   • Problems 48a–d ask you to compute a few values of an Ackermann function.
   • 3 points each

   ---

7. (12 points)

   p. 310: 50

   • This asks you to prove (using mathematical induction, of course!) an interesting theorem about the Ackermann function from problem #48.
   • 3 points each for stating and for proving the base case;
     3 points each for stating and for proving the recursive case

   ---

8. (Required Extra Credit Problem!)

   p. 310: 52

   • This is a deceptively simple problem:
     You're merely asked to compute the value of A(3,4) for the Ackermann function from the 2 previous problems.
     It is simple to do, but may take you a while.

   • If you get it right, with all the steps spelled out, I'll give you 12 points of extra credit.

   • If you stop, or get lost, in the middle of the computation and explain why you stopped computing the value, you will neither get nor lose any extra points.

   • BUT YOU MUST ATTEMPT THIS PROBLEM; otherwise, I will deduct 12 points from your total!
     (I really want you to get a feel for why Ackermann functions are weird.)

   • Hint: You might want to try #51a and especially #51b first and then check your answer in the back of the book.

Grand total = 63 points.

Tentative grading scheme:

A       61 - 63
A-      57 - 60
B+      54 - 56
B       50 - 53
B-      47 - 49
C+      43 - 46
C       36 - 42
C-      29 - 35
D+      22 - 28
D       12 - 21
F        0 - 11