# Discrete Math Logic Defineing a function recursion-ish

1. Mar 1, 2012

### geforce

(3) De fine a function A(m,n) as follows.
A(0,n) = 2n for every n.
A(m,0) = 0 for every m >= 1
A(m,n) = 2 if m >= 1 and n = 1
A(m,n) = A(m -1,A(m, n - 1)) otherwise (i.e., if m >= 1 and n >= 2.

(b) Prove A(m,2) = 4 for every m >= 2
(c) Prove A(1, n) = 2^n for every n >= 1.

Proving these by induction

B) Base Case

M>=2

M=2

A(2,2) = A(2-1, A(2, 2-1))

A(2,1) = 2 by rule so

A(2,2) = A(1, 2) = A(1-1, A(1, 2-1))

A(1,1) = 2

So A(1,2) = A(0,2)
A(0,2) = 2n = 2(2) = 4
Finally, A(2,2) = 4

Induction step

K+1 = 3

M>=3

A(3,2) = A(3-1, A(3, 2-1))

A(3,1) = 2

A(2,2) = 4 from before
so A(3,2) = 4

C) Is basically the same solving

My question is for B) C) Should i be using variables like i, j or something like that because i think I'm doing something wrong with proving because it looks a bit too simple.

2. Mar 1, 2012

### issacnewton

have you studied induction ? you have proved the base case. thats fine. now for the induction
case you assume that the statement is true for some $k\geqslant 2$ and then prove that the statement is true for $k+1$. So for b, assume that

$$A(k,2) = 4$$

for some $k\geqslant 2$. Now prove that the statement is true for $k+1$.

$$A(k+1,2) = 4$$