Results 1 to 5 of 5

Math Help - How did they get this answer to mathematical induction?

  1. #1
    Junior Member
    Joined
    May 2010
    Posts
    27

    How did they get this answer to mathematical induction?

    My professor gave us the answer to a homework question and i dont know how she got some of it?

    1 + 3n <= 4^n, n >= 0 for all integers n

    Base case
    let n = 0

    then 1 + 3n = 1 + 3(0) = 1
    4^n = 4^0 = 1

    1 = 3n = 1 = 4^n good

    next inductive Step

    P(k) ----> P(k + 1)
    4^k >= 1 + 3k (ind hyp)

    4^(k+1) = 4^k x 4 laws of exponent
    >=(1 +3k) 4 by induction

    >=(4 + 12k)
    4^(k+1)>=(4 + 3k)
    4^(k+1)>=1 + 3k + 3
    4^(k+1)>=1 + 3(k + 1) conclusion

    What i dont get is in bold
    1) It looks like they flipped the equity sign and equation after the base case? why?
    2) The stuff in bold i see they multiplied (1 + 3k) to get (4 + 12k). how did they get to (4 + 3k) then to 1 + 3k + 3?


    Thank you!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    \displaystyle P(k): 1+3k\leq 4^k We assume this and we need to obtain \displaystyle P(k+1): 1+3(k+1)\leq 4^{k+1}

    \displaystyle 4*[1+3k]\leq [4^k]*4\rightarrow 4+12k\leq 4^{k+1}\rightarrow 4+3k+9k\leq 4^{k+1} Since k is positive, we can drop the 9k term WLOG.

    Thus, \displaystyle 4+3k\leq 4^{k+1}\rightarrow 1+3+3k\leq 4^{k+1}\rightarrow 1+3(1+k)\leq 4^{k+1}\rightarrow 1+3(k+1)\leq 4^{k+1}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    May 2010
    Posts
    27
    How did you get 4 + 3k + 9k <= 4^k+1 from 4 + 12k <= 4^(k+1)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    What is 9k+3k equal to?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by Thetheorycase View Post
    My professor gave us the answer to a homework question and i dont know how she got some of it?

    1 + 3n <= 4^n, n >= 0 for all integers n

    Base case
    let n = 0

    then 1 + 3n = 1 + 3(0) = 1
    4^n = 4^0 = 1

    1 + 3n = 1 = 4^n good

    next inductive Step

    P(k) ----> P(k + 1)
    4^k >= 1 + 3k (ind hyp)

    4^(k+1) = 4^k x 4 laws of exponent
    >=(1 +3k) 4 by induction

    .......if 4^k\ \ge\ 1+3k\Rightarrow\ (4)4^k\ \ge\ (4)(1+3k)

    >=(4 + 12k)
    4^(k+1)>=(4 + 3k)

    ..... it's only required to show 4^{k+1}\ \ge\ 1+3(k+1)

    4+12k>4+3k

    4^(k+1)>=1 + 3k + 3
    4^(k+1)>=1 + 3(k + 1) conclusion

    What i dont get is in bold
    1) It looks like they flipped the equity sign and equation after the base case? why?
    2) The stuff in bold i see they multiplied (1 + 3k) to get (4 + 12k). how did they get to (4 + 3k) then to 1 + 3k + 3?

    they used the fact that 4+12k>4+3k and (4)+3k=(1+3)+3k


    Thank you!!!
    Here is another way...

    P(k)

    1+3k\ \le\ 4^k


    P(k+1)

    replace k with k+1

    1+3(k+1)\ \le\ 4^{k+1}

    Try to show that P(k+1) has to be valid if P(k) is valid


    Proof

    if 4^{k+1}\ \ge\ 1+3(k+1) ......get this in the form 4^k and 1+3k for comparison.

    then (4)4^k\ \ge\ 1+3k+3

    (3)4^k+4^k\ \ge\ (1+3k)+3.

    Since (3)4^k\ \ge\ 3 for all k\ \ge\ 0

    then 4^{k+1}\ \ge\ 1+3(k+1) if 4^k\ \ge\ 1+3k
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  2. mathematical induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 9th 2009, 01:06 PM
  3. Mathematical induction
    Posted in the Calculus Forum
    Replies: 1
    Last Post: January 6th 2009, 09:03 PM
  4. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 11th 2008, 06:16 AM
  5. Replies: 2
    Last Post: April 28th 2008, 09:15 AM

Search Tags


/mathhelpforum @mathhelpforum