Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Discrete Math Logic Defineing a function recursion-ish

  1. Mar 1, 2012 #1
    (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. jcsd
  3. Mar 1, 2012 #2
    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 [itex]k\geqslant 2[/itex] and then prove that the statement is true for [itex]k+1[/itex]. So for b, assume that

    [tex]A(k,2) = 4[/tex]

    for some [itex]k\geqslant 2[/itex]. Now prove that the statement is true for [itex]k+1[/itex].

    [tex]A(k+1,2) = 4[/tex]
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook