Problem 1 (10 + 15 = 25 points) You encounter the following mysterious piece of code.

Algorithm 1: Mystery Function

1 Function (, ):

2 if = 0 then

3 return (1, 0)

4 else

5 1

6 for from 1 to do

7

8 (, ) (, 1)

9 return ( , + 4 )

(a) What are the results of (, 2), (, 3), and (, 4)?

(b) What does the code do in general, when given input integer 0? Prove your assertion by

induction on .

Problem 1(10+15=25 points) You encounter the following mysterious piece of code. (a) What are the results of F(a,2),F(a,3), and F(a,4) ? (b) What does the code do in general, when given input integer n0 ? Prove your assertion by induction on n