Results 1 to 4 of 4

Math Help - Induction and more.

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    50

    Induction and more.

    N is Z loadet in a table T in the spots 1,2,...,N, arranged so that the number in spot i always is smaller og equal to the number on the spot i+1.
    Example given.
    -1212 | -1002 | -800 | -545 | -123 | -54 | -2 | 0 | 4 | 321 | 324 | 501

    (N = 12), We wish to determine wether 0 is part of this table og look at the following algorithm.

    Psedu code picture by krakatau7 - Photobucket

    Question (B)

    Consider a random arranged table T with N entries (inputs?). Prove by induction this claim:

    j-i < 2^n \Rightarrow A(i,j) \leq n

    for every Z i,j,n with 1\leq i \leq j \leq N and n \geq n
    Last edited by Madspeter; October 11th 2009 at 11:33 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Sep 2009
    Posts
    50
    Bumping this thread, as I have modified a bit in the text.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2009
    Posts
    50

    am I right?

    so my first thoughts are

    Basic step P(o) = j - i < 1 => A(j,i) \leq O

    Is this our basic step?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Sep 2009
    Posts
    50
    furthermore

    we assume P(n) j-i < 2^n => A(j,i) \leq n

    is TRUE

    and now we want to prove P(n+1) is true

    P(n+1) j-i < 2^n+1 => A(j,i) \leq n+1

    if we want to prove this, we need to show that

    A(j,i) \leq n+1

    to prove this our teacher said we could use j' - i' < 2^n+1
    and remake 2^n+1 into 2^n *2

    I understand the rule of operation, but I dont see how this can help us to reach further in the induction.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 19th 2010, 05:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 7th 2008, 04:10 PM

Search Tags


/mathhelpforum @mathhelpforum