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 $\displaystyle s_1,\ldots ,s_n$ be a sequence satisfying

(a) $\displaystyle s_1$ is a positive integer and $\displaystyle s_n$ is a negative integer.

(b) For all $\displaystyle i$, $\displaystyle 1\leq i<n$, $\displaystyle s_{i+1}=s_i+1$ or $\displaystyle s_{i+1}=s_i-1$.

Prove that there exists $\displaystyle i$, $\displaystyle 1<i<n$, such that $\displaystyle 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?

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

Quote:

Originally Posted by

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

Let $\displaystyle s_1,\ldots ,s_n$ be a sequence satisfying

(a) $\displaystyle s_1$ is a positive integer and $\displaystyle s_n$ is a negative integer.

(b) For all $\displaystyle i$, $\displaystyle 1\leq i<n$, $\displaystyle s_{i+1}=s_i+1$ or $\displaystyle s_{i+1}=s_i-1$.

Prove that there exists $\displaystyle i$, $\displaystyle 1<i<n$, such that $\displaystyle 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.

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 $\displaystyle 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).

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.

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

Quote:

Originally Posted by

**Ragnarok** 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 $\displaystyle \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 $\displaystyle \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 $\displaystyle 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 $\displaystyle k-1\ge1$ because 1 < k, so $\displaystyle s_{k-1}$ is defined. Since $\displaystyle k-1\notin A$, $\displaystyle s_{k-1}\ge0$, and since $\displaystyle s_k<0$ and $\displaystyle s_{k-1}\le s_k+1$, we have $\displaystyle s_{k-1}\le0$. Altogether, $\displaystyle s_{k-1}=0$. But again, we used induction hidden in the least number principle.

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.