- #1
geforce
- 26
- 0
(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.
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.