# Thread: induction to show that A (1,n)

1. ## induction to show that A (1,n)

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.

2. ## Re: induction to show that A (1,n)

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.

3. ## Re: induction to show that A (1,n)

Base case: A (1,0)=2 true. Inductive Step : Assume A(1,n)= n+2 is true, then A(1, n+1)= (n+1)+2 is true.

4. ## Re: induction to show that A (1,n)

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?

5. ## Re: induction to show that A (1,n)

me...not really

6. ## Re: induction to show that A (1,n)

By IH, A(1, n) = n + 2. So, you can simplify A(0, A(1, n)). After that, apply the first line of the definition.

7. ## Re: induction to show that A (1,n)

simplify A(0, A(1, n)) = A(0, n+2)? A(1,1) =3

8. ## Re: induction to show that A (1,n)

Originally Posted by tinabaker
simplify A(0, A(1, n)) = A(0, n+2)?
Yes.
Originally Posted by tinabaker
A(1,1) =3
This is true but is not used in the inductive step.
Originally Posted by emakarov
After that, apply the first line of the definition.

9. ## Re: induction to show that A (1,n)

A(0, n+2)= A (1,n), really not sure howto apply the first line of the definition.

10. ## Re: induction to show that A (1,n)

I assume the definition you have is the following.

$A(m, k) =\begin{cases}k+1 & \mbox{if } m = 0 \\A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } k = 0 \\A(m-1, A(m, k-1)) & \mbox{if } m > 0 \mbox{ and } k > 0.\end{cases}$

Note: compared to the Wiki link above, I systematically replaced $n$ with $k$ everywhere in the definition. This is OK because $n$ 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 $A(0, n+2)$, you compare $A(0, n+2)$ with the definition's left-hand side, i.e., $A(m, k)$. These two expressions match if $m = 0$ and $k= n + 2$. Then you replace $m$ with 0 and $k$ with $n + 2$ everywhere in the right-hand side. You get

$\begin{cases}(n+2)+1 & \mbox{if } 0 = 0 \\A(0-1, 1) & \mbox{if } 0 > 0 \mbox{ and } n+2 = 0 \\A(0-1, A(0, (n+2)-1)) & \mbox{if } 0 > 0 \mbox{ and } n+2 > 0.\end{cases}$

Now you need to select of one of these three values based on which of the corresponding conditions is true.

11. ## Re: induction to show that A (1,n)

I think the first one, because m=0, then A (0, (n+2)+1)

12. ## Re: induction to show that A (1,n)

Originally Posted by mathproblems
I think the first one, because m=0
That's right.

Originally Posted by mathproblems
then A (0, (n+2)+1)
But where did A (0, (n+2)+1) come from? Is it in the first line of the definition?