## CS 5315 Homework #2

**Date Assigned:** Thursday, January 20, 2005
**Due Date:** Tuesday, January 25, 2005

1. In the class, we proved that if P(n) is a primitive recursive
predicate, and f(n) and g(n) are primitive recursive functions, then
the function "if P(n) then f(n) else g(n)" is also primitive
recursive. Use the ideas from this proof to prove that if P1(n) and
P2(n) are primitive recursive predicates, and f(n), g(n), and h(n) are
primitive recursive functions, then the function
"if P1(n) then f(n) else if P2(n)
then g(n) else h(n)" is also primitive recursive.

2. Show that the function pow(a,n)=a^n (a to the power n) is a primitive
recursive function.