Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By chiro

Math Help - Induction on sequence

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    54

    Induction on sequence

    Hi,


    I'll go strait to the point:

    I have an array of values (it is a problem from CS but simplified) like :


    Code:
    1 2 3 4 5 6 7 8 9 10 11 12 13 ...
    indexing starts from 0. so A[0] = 1

    rule by which the array if filled is : A[i+1] = A[i] +1

    Question is :

    Will the difference between two consecutive values always be 1.


    I decided to prove this by induction on i. So, for i=0 we have A[i+1] -A[i] = A[i] + 1 -A[i] = 1 as expected. Then for i>0 according to the inductive hypothesis if p=0..k, A[q+1]-A[q] = 1 and for q = 1..k+1 we have A[q+1]-A[q] = 1 then it follows that for all i = 0..k+1, A[i+1]-A[i] = 1.


    Does this make any sense ??

    Thank you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,698
    Thanks
    620

    Re: Induction on sequence

    Hey baxy77bax.

    You can do this if you want but you can just re-arrange your relationship and assume that if it holds for all i then the relationship is true.

    Induction statements are usually defined for things that vary but in your case you have specified that A[i+1] - A[i] = 1, where-as many inductive statements look at things that vary (like say A[i+1] - A[i] = i^2 + 2i - 1 for example).
    Thanks from baxy77bax
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: Induction on sequence

    Quote Originally Posted by baxy77bax View Post
    rule by which the array if filled is : A[i+1] = A[i] +1
    Does it follow that A[i + 1] - A[i] = 1? Hmm, let's ask an elementary school student who learned how to move terms from one side of an equation into the other.

    Formally speaking, chiro is right that your induction argument does not use the induction hypothesis, so it is a direct proof (and trivial at that).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Induction on a sequence
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 2nd 2011, 10:25 AM
  2. Induction Sequence
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: November 5th 2009, 10:14 AM
  3. induction on a reccurence sequence
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 29th 2008, 08:24 AM
  4. Induction, sequence, not hard, please help me
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 19th 2007, 11:57 AM
  5. Induction on a sequence
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 23rd 2006, 05:16 PM

Search Tags


/mathhelpforum @mathhelpforum