Results 1 to 6 of 6
Like Tree2Thanks
  • 1 Post By emakarov
  • 1 Post By emakarov

Math Help - Prove that a sequence has a given value (discrete version of calculus proof)

  1. #1
    Member
    Joined
    Apr 2010
    Posts
    116
    Thanks
    1

    Prove that a sequence has a given value (discrete version of calculus proof)

    This is from a discrete math textbook, but obviously calculus-based, so I'm asking it here.

    Let s_1,\ldots ,s_n be a sequence satisfying
    (a) s_1 is a positive integer and s_n is a negative integer.
    (b) For all i, 1\leq i<n, s_{i+1}=s_i+1 or s_{i+1}=s_i-1.
    Prove that there exists i, 1<i<n, such that s_i=0.

    I thought about doing proof by contradiction, but I can't work anything out. I do not remember or never came across the regular calculus version of this theorem. Can anyone help?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie Phantasma's Avatar
    Joined
    Jun 2013
    From
    United States of Hysteria
    Posts
    19
    Thanks
    6

    Re: Prove that a sequence has a given value (discrete version of calculus proof)

    Quote Originally Posted by Ragnarok View Post
    This is from a discrete math textbook, but obviously calculus-based, so I'm asking it here.

    Let s_1,\ldots ,s_n be a sequence satisfying
    (a) s_1 is a positive integer and s_n is a negative integer.
    (b) For all i, 1\leq i<n, s_{i+1}=s_i+1 or s_{i+1}=s_i-1.
    Prove that there exists i, 1<i<n, such that s_i=0.

    I thought about doing proof by contradiction, but I can't work anything out. I do not remember or never came across the regular calculus version of this theorem. Can anyone help?
    If the first term is positive and the last term is negative, then the sequence has to pass 0 (or go past infinity, in some cases, but we'll ignore that) somewhere on that interval.

    Because the sequence must pass from one integer to the next higher or next lower integer, then it must pass through the integer zero.

    I'm unfamiliar with the discrete analogue of the intermediate value theorem, so I can't help you there. However, the result here should be intuitive.
    Follow Math Help Forum on Facebook and Google+

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

    Re: Prove that a sequence has a given value (discrete version of calculus proof)

    I agree that the result is intuitive. Formally, it is proved by induction on n. When proving the claim for n + 1, we consider s_2. It is either positive (then we apply the induction hypothesis for the interval 2, ..., n+1), or zero (then the claim is immediate).
    Thanks from Ragnarok
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Apr 2010
    Posts
    116
    Thanks
    1

    Re: Prove that a sequence has a given value (discrete version of calculus proof)

    Thanks guys! I understand that the result is intuitive, but sometimes intuitive things are the hardest for me to prove. emakarov, I am wondering if there is a way to prove it without induction since the book has not covered induction yet. All that has been covered is proof by contradiction, contraposition, exhaustion, etc.
    Follow Math Help Forum on Facebook and Google+

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

    Re: Prove that a sequence has a given value (discrete version of calculus proof)

    Quote Originally Posted by Ragnarok View Post
    I am wondering if there is a way to prove it without induction since the book has not covered induction yet. All that has been covered is proof by contradiction, contraposition, exhaustion, etc.
    Since the fact is relatively simple, any proof depends heavily on the available axioms. To be sure, a proof of a complicated fact, e.g., that \pi is transcendental, also depends on the basic facts about real numbers. But the main part of such proof starts when these basic facts are already established; they are just a very short introduction. So, if you change axioms of real numbers and establish basic facts in a different way, the proof that \pi is transcendental will not change that much. On the other hand, a proof of a simple fact like commutativity of addition on natural numbers is all about the axioms that define addition. The proof is just a few steps long, so changing axioms changes it completely.

    Now, in the standard axiomatization of natural numbers and integers (called Peano arithmtic), induction plays a crucial role. Induction is for proofs what loops are for algorithms. Very few general facts can be proved without it. For example, commutativity of addition requires three applications of induction.

    So I doubt the original claim can be proved without induction in the standard axiomatization. In less formal proofs, though, induction is often not mentioned explicitly and is replaced by things like "..." and "and so on". The fact that every nonempty set of natural numbers has the least element is also equivalent to induction. It can be used to reason as follows. Consider A = \{i\in\mathbb{N}\mid 1 < i \le n\text{ and }s_i < 0\}. Then A is nonempty because n is in A. Therefore, A has the least element, say, k. Note that k-1\ge1 because 1 < k, so s_{k-1} is defined. Since k-1\notin A, s_{k-1}\ge0, and since s_k<0 and s_{k-1}\le s_k+1, we have s_{k-1}\le0. Altogether, s_{k-1}=0. But again, we used induction hidden in the least number principle.
    Thanks from Ragnarok
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Apr 2010
    Posts
    116
    Thanks
    1

    Re: Prove that a sequence has a given value (discrete version of calculus proof)

    Thanks so much for the detailed reply, it was fascinating for me to read and really helped me a lot since I am often confused by how rigorous books want answers to be.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Models for Cooling, 9.4 in the Stewart Calculus book, version 6.
    Posted in the Differential Equations Forum
    Replies: 3
    Last Post: June 14th 2011, 10:06 PM
  2. how to prove this version of L'Hopital's rule
    Posted in the Calculus Forum
    Replies: 0
    Last Post: March 14th 2011, 09:41 AM
  3. Express this sequence as a unit step function (discrete)
    Posted in the Advanced Math Topics Forum
    Replies: 3
    Last Post: January 3rd 2011, 05:31 AM
  4. Replies: 2
    Last Post: August 28th 2009, 02:59 AM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum