Book

https://discrete.openmathbooks.org/pdfs/dmoi3-tablet.pdf

6:48 AM Mon Mar 6 43% d21.oakton.edu a Show written solutions for all of the following problems. Text: Discrete Mathematics: An Open Introduction, 3'd Edition. 0.4 Functions, Exercises: 9, 11 2.4 Solving Recurrence Relations, Exercises: 2a. and 2b. Exercises Given the following recursive function, find the output for the specified input. 1) FACTORIAL (n) : return n* FACTORIAL(n-1) Find FACTORIAL (5) . 2) GCD(X, y) : if (x % y = 0), return y else, return GCD(y, x % y) Find GCD(24, 72) . 3) POW(x, n) : if (n = 1), return x else return x*POW(x, n-1) Find POW(5, 4) . 4) ACKERMANN(x, y) : if (x = 0), return y+1 else if((x > 0) and (y = 0)), return ACKERMANN(x-1, 1) else if((x > 0) and (y > 0)), return ACKERMANN(x-1, ACKERMANN(x, y-1) ) Find ACKERMANN ( 3, 2) . 5) PAY_TOLLS (n) : if (n = 10), return 2 else if (n = 5), return 1 else, return PAY_TOLLS(n - 5) + PAY_TOLLS(n - 10) Find PAY_TOLLS(40) . 6) Give a recursive function for finding the sum of the first n odd positive integers. Use a similar notation to the previous recursive functions in Exercises 1 through 5 above. Given the following recursively defined functions, find the output for the specified input. 7) Find f(1), f(2), and f(3), if f(n) is defined recursively by f(0) = 2 and for n = 0, 1, 2, ... a) f(n + 1) = f(n) + 2 f (n + 1) = 3f(n) c) f (n + 1) = 2f(n) Find f(2), f(3), and f(4), if f(n) is defined recursively by f(0) = 1, f(1) = -2 and for n = 2, 3, ... a) f (n + 1) = f(n) + 3.f(n - 1) b ) f ( n + 1 ) = f (n)2f (n - 1)