1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Discrete Math Logic Defineing a function recursion-ish
Loading...