Homework 15

Details

1. Consider the following recursively defined function
   
   \(\displaystyle T(n) = \begin{cases} 2, & \text{if } n \le 0, \\ T(n-1) + 3, & \text{if } n > 0. \end{cases} \)
   
   
   1. (5) Compute \(T(0)\), \(T(1)\), \(T(2)\), \(T(3)\), and \(T(4)\).
   2. (2) What are the base case(s) of the recursion?
   3. (2) What are the inductive/recursive cases?
   4. (3) Explain why the recursion always terminates.
2. A student is climbing a staircase with \(n\) steps. At each move, the student may climb either \(1\) step or \(2\) steps. Let \(S(n)\) be the number of different ways to climb the staircase.
   1. (3) Explain why \(S(0)=1\) and \(S(1)=1\).
   2. (3) Explain why, for \(n\ge 2\),
      \[ S(n)=S(n-1)+S(n-2). \]
   3. (4) Compute \(S(2)\), \(S(3)\), \(S(4)\), and \(S(5)\).
   4. (6) Prove by induction that the recurrence correctly counts the number of ways to climb the staircase. (Hint: If you did parts (a) and (b) correctly, you have most of the details already.)