Reading material

Pages 63-66.

Additional material

The Standard ML function
  fun pow(0) = 1
    | pow(n) = pow(n - 1) + pow(n - 1)
computes 2n. The function
  local
    fun helper(0, p) = p
      | helper(n, p) = helper(n - 1, n * p)
  in
    fun fac(n) = helper(n, 1)
  end
computes n!

Question

What does the Java method

  public static int m(int i)
  {
      if (i == 0) 
      {
          return 1;
      }
      else
      {
          return m(i - 1) + 2 * m (i - 2);
      }  
  }
return? Which expression does it correspond to? How can induction be used to prove the method correct?