I am trying to use this exercise to study for my exam. I plan on offering the ma

Question

I am trying to use this exercise to study for my exam. I plan on offering the maximum number of points in the hopes that I can get a very detailed answer I will be able to use to completely understand the problem.

If I can get an answer within the next couple of hours I would be willing to gift some extra points as well.

Thanks!

A sequence (an) is called strictly increasing if Vn : an less than an+1. A sequence (an) is called strictly decreasing if Vn : an greater than an+1. A sequence (an) is called constant if Vn : an = an+1. Prove that every sequence of n3 + 1 (not necessarily distinct) integers contains a subsequence of length n + 1 that is either strictly increasing or strictly decreasing or constant.

Explanation / Answer

let a1,a2,a3,.....,a(n^3+1) be the given sequence

let (b1,b2,.....,b(n^3+1)) be an arrangement of (a1,a2,a3,.....,a(n^3+1)) such that

b1<=b2<=.....<=b(n^3+1)

consider subsequence {b1, bn+1, b2n+1, b3n+1......, bn^3+1}

we know that b1<= bn+1 <= b2n+1 <=b3n+1......<= bn^3+1

if any two elements of the above sequence are equal, i.e

bpn+1 = b(p+1)n+1 ,    then the required sequence is {bpn+1, bpn+2, ....., bpn +n+1}

since bpn+1 =bpn+2 = .....= bpn +n+1

if no two elemets of {b1, bn+1, b2n+1, b3n+1......, bn^3+1} are equal then

{b1, bn+1, b2n+1, b3n+1......, bn^3+1}is our required sequence

since b1< bn+1 < b2n+1 <b3n+1......< bn^3+1 if no elements are equal

thus proved

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.