Intereting Posts

Two Dirichlet's series related to the Divisor Summatory Function and to the Riemann's zeta-function, $\zeta(s)$
What are dynamic networks.
Integration with a quartic in the denominator $\frac{1}{(x^2-1)^2}$
What math should a computer scientist take in college?
Eckmann-Hilton and higher homotopy groups
Prove ${_2F_1}\left({{\tfrac16,\tfrac23}\atop{\tfrac56}}\middle|\,\frac{80}{81}\right)=\frac 35 \cdot 5^{1/6} \cdot 3^{2/3}$
Borel Measures: Atoms vs. Point Masses
Example of linear parabolic PDE that blows up
Rank of the $n \times n$ matrix with ones on the main diagonal and $a$ off the main diagonal
Negation of quantifiers
Proving that $x$ is irrational if $x-\lfloor x \rfloor + \frac1x – \left\lfloor \frac1x \right\rfloor = 1$
How do I find a flaw in this false proof that $7n = 0$ for all natural numbers?
Square and square root and negative numbers
Using $O(n)$ to determine limits of form $1^{\infty},\frac{0}{0},0\times\infty,{\infty}^0,0^0$?
Why any short exact sequence of vector spaces may be seen as a direct sum?

I was trying to solve this question but stuck with how do I prove it so. I do have the intuition but how to prove it? Here is the link to the page and this one is the problem 1!!

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/assignments/MIT6_042JF10_assn02.pdf

*Don’t tell all the answers but rather give a definitive hint or strategy for the first part!!*

Define a 3-chain to be a (not necessarily contiguous) subsequence

of three integers, which is either monotonically increasing or monotonically decreasing. We

will show here that any sequence of five distinct integers will contain a 3-chain. Write

the sequence as a1, a2, a3, a4, a5. Note that a monotonically increasing sequences is one in

which each term is greater than or equal to the previous term. Similarly, a monotonically

decreasing sequence is one in which each term is less than or equal to the previous term.

Lastly, a subsequence is a sequence derived from the original sequence by deleting some

elements without changing the location of the remaining elements.

- Mathematical induction proof that $\sum\limits_{k=2}^{n-1} {k \choose 2} = {n \choose 3} $
- Proving $2^{2n}-1$ is divisible by $3$ for $n\ge 1$
- Prove with induction that $11$ divides $10^{2n}-1$ for all natural numbers.
- Understanding Less Frequent Form of Induction? (Putnam and Beyond)
- elementary prove thru induction - dumb stumbling
- For what natural numbers is $n^3 < 2^n$? Prove by induction

(a) [4 pts] Assume that a1 < a2. Show that if there is no 3-chain in our sequence, then a3

must be less than a1. (Hint: consider a4!)

(b) [2 pts] Using the previous part, show that if a1 < a2 and there is no 3-chain in our

sequence, then a3 < a4 < a2.

(c) [2 pts] Assuming that a1 < a2 and a3 < a4 < a2, show that any value of a5 must result

in a 3-chain.

(d) [4 pts] Using the previous parts, prove by contradiction that any sequence of five distinct

integers must contain a 3-chain.

- The sum of three consecutive cubes numbers produces 9 multiple
- Enigma : of Wizards, Dwarves and Hats
- Prove by induction that $\sum_{i=1}^{2^n} \frac{1}{i} \ge 1+\frac{n}{2}, \forall n \in \mathbb N$
- Dominoes and induction, or how does induction work?
- Prove that $\sum_{d|n}\phi(d)=n$ where $\phi$ is the Euler's phi function, $n,c\in\mathbb{N}$
- What is the purpose of the first test in an inductive proof?
- Chameleons of Three Colors puzzle
- Fibonacci using proof by induction: $\sum_{i=1}^{n-2}F_i=F_n-2$
- expected value of a sum of a 10 sided die
- In proof by induction, what happens if P(n) is false for a specific case or the base cases are false? Can we still deduce meaningful conclusions?

The first part already contains a good hint. A little more explicit: Suppose the desired conclusion is false, i.e., $a1<a2$ and there is no $3$-chain, but $a3>a1$. How could you choose $a4$ without introducing a $3$-chain?

**Non Contradictory proof –**

A general proof goes like the way, that there are 5 nos,

a1 _ a2 _ a3 _ a4 _ a5.

Now, since ** there are only 2 symbols available, ‘<‘ and ‘>’**, there will be **repetitions of symbols**. And since the question demands that the sequence should not be changed, so there will always be a 3 chain.

For all possible combinations, **with minimum occurrence of each symbol = 2**, a 3 chain sequence can be formed by deleting. For eg.-

1. a1 < a2 > a3 < a4 > a5 | Chain – a1 < a2 < a4 or a2 > a4 > a5

2. a1 > a2 < a3 > a4 < a5 | Chain – a1 > a3 > a4 or a2 < a4 < a5

Answering the question in the form they asked –

**Part 1 **–

Now we assume a1 < a2.

So, the 5 numbers would be – a1 < a2 _ a3 _ a4 _ a5.

Proof by contradiction –

**For propositon, lets assume, there is no 3-chain, but a3 > a1**. There arise 2 possibilities, which are –

1 – a1 < a2 < a3

2 – a1 < a3 < a2

The first case cannot be taken(It forms the 3 chain)! In the second case, when we introduce a4, there are 4 possibilities,as –

1 – a4 < a1 < a3 < a2

2 – a1 < a4 < a3 < a2

3 – a1 < a3 < a4 < a2

4 – a1 < a3 < a2 < a4

As we can see, all of them have a chain, (4,3,2),(4,3,2),(1,3,4),(1,2,4).

Thus, our assumption that a3 > a1, gave no possible combinations.

Thus our assumption was wrong!!

**Part 2 – **

Proof by contradiction –

From part 1, we know that a3 < a1, the possible combinations that can be made from the three numbers are –

1 – a3 < a1 < a2

**We are given the equation, a3 < a4 < a2, then the proposition will be, a4 < a3 or a4 > a2. This is just converse of the given statement.**

Adding a4 to the equation, we get combinations as-

1 – a4 < a3 < a1 < a2

2 – a3 < a1 < a2 < a4

As we can see, both the combinations give a 3-chain combinations as (4,3,2),(1,2,4).

Thus the assumption that a4 < a3 or a4 > a2 is false, because it is given that there is no 3 – chain to be formed!

**Part 3 – **

Proof by contradiction –

From previous part, and the assumptions in this part, we know that the combinations can be –

1 – a3 < a4 < a1 < a2

2 – a3 < a1 < a4 < a2

**The proposition for the proof can be that, adding a5 doesn’t makes any 3 chain.**

Adding a5 to the equation, the possible positions can be –

1 – a5 < a3 < a4 < a1 < a2

2 – a3 < a5 < a4 < a1 < a2

3 – a3 < a4 < a5 < a1 < a2

4 – a3 < a4 < a1 < a5 < a2

5 – a3 < a4 < a1 < a2 < a5

Every possible combination has a 3 – chain. (5,3,1),(5,4,2),(3,4,5),(3,4,5),(1,2,5).

Thus the assumption for a5 can be added to the equation, is wrong!!

In similar manner, the fourth part can be proved!!

Klaus Draeger has helped you with the first part, and the other parts are similar. Just try to envisage the possible cases at each step of the game – there is no “strategy” involved in this solution approach.

Here is a proof involving less chasing of cases:

Let ${\bf s}=(s_1,s_2,s_3,s_4)$ be given by

$$s_k:={\rm sgn}(a_{k+1}-a_k)\quad\in\{-1,1\}\ .$$

If ${\bf s}$ contains two successive entries of the same sign we are done. It remains to consider the case ${\bf s}=(1,-1,1,-1)$, since symmetry will then take care of $-{\bf s}$. When $a_4> a_2$ then $(a_1, a_2, a_4)$ is an ascending chain, and when $a_4< a_2$ then $(a_2,a_4, a_5)$ is a descending chain, since $s_4=-1$ says that $a_5<a_4$.

- Is there any sans-calculus proof of irrationality of $\pi$?
- Show that every group of prime order is cyclic
- A trigonometic integral with complex technicals
- Traces of all positive powers of a matrix are zero implies it is nilpotent
- Compute $\int_0^{\pi/4}\dfrac{(1-x^2)\ln(1+x^2)+(1+x^2)-(1-x^2)\ln(1-x^2)}{(1-x^4)(1+x^2)} x\exp\dfrac{x^2-1}{x^2+1} dx$
- Necessary and Sufficient Conditions for Riemann Integrability
- Proving $W$ is a subspace of $P_{2}$
- Proof of Unique Solution for Modular Exponentiation In Cryptography
- Is any divergence-free curl-free vector field necessarily constant?
- Runge-Kutta methods: step size greater than 1
- Sum of eigenvalues and singular values
- Minimize $\|AXBd -c \|^2$, enforcing $X$ to be a diagonal block matrix
- Solution of functional equation $f(x+y)=f(x)+f(y)+y\sqrt{f(x)}$
- The Function $f:\mathbb{R}^{2}\rightarrow \mathbb{R}^{2}$ defined by $f(r,\theta)=(r\cos\theta,r\sin\theta)$
- Is the product of a Cesaro summable sequence of $0$s and $1$s Cesaro summable?