Can someone help me with this one: Use induction to show that A (1,n) = n+2, n =0, 1...How do I start here? Thank you.
My guess is that A(m, n) is the Ackermann function. Do you have the same definition as in Wikipedia? Just follow the regular procedure for proofs by induction: identify the property P(n) you are proving for all n, prove the base case P(0), state the induction hypothesis and the goal for the induction step, etc. For more on the generic procedure, see this post.
Yes, this is the outline. So, for the base case, A(1, 0) = A(0, 1) = 2 applying the second and then the first line of definition. For the step, A(1, n + 1) = A(0, A(1, n)) by the third line of definition. Can you continue by using the inductive hypothesis?
I assume the definition you have is the following.
Note: compared to the Wiki link above, I systematically replaced with everywhere in the definition. This is OK because is just a placeholder that relates the left- and right-hand sides; it show where a number that is the second argument of the left-hand side is used in the right-hand side.
To compute , you compare with the definition's left-hand side, i.e., . These two expressions match if and . Then you replace with 0 and with everywhere in the right-hand side. You get
Now you need to select of one of these three values based on which of the corresponding conditions is true.