# Solving Sequence Problem: Find Increasing Sequence of 11 Terms

• sylar
In summary: It can skip over terms. For example, the sequence 1, 3, 2, 4, 6, 5, 7, 9, 8 could have a subsequence 1, 3, 4, 6, 7, 9 that is increasing.In summary, the problem is to show that given a sequence with 101 elements, one can find an increasing sequence of 11 terms. This can be achieved by picking the greatest element and adding it to the end of the sequence, then dividing the remaining elements into groups of ten and finding the least element in each group. Arranging these least elements in increasing order will result in an increasing sequence of
sylar
In a sequence with 101 elements show that one can find an increasing sequence of 11 terms.

Here is my approach: Pick the greatest element of the sequence (or one of the largest elements if there is more than one large element) and put it onto the end of the sequence we are forming. Then make ten groups consisting of the terms of the original sequence so that each group has ten elements. Now find the least elements of each group(if there is more than one least element in a group, then choose one of them). Finally, arranging these 10 least elements in an increasing order we get an increasing sequence of 11 terms.

Is this argument sound? Or can we solve this problem in a more elegant way?

The statement isn't even true, though it may be if you apply stricter conditions. Take $$a_1 = a_2 = a_3 ... a_{101}$$ ie a constant sequence. No increasing sequence can be made out of those.

yeah, like Gib Z pointed out, that statement is not true, unless we put some further conditions, like for at least 11 terms not to be equal to each other or sth like that!

Hey guys, i think you are missing one point. The question doesn't ask us to prove that there exists a strictly increasing sequence; it asks us to show that there exists an increasing sequence. That is, if all terms are equal to each other, then we have an increasing sequence.

sylar said:
Is this argument sound?

No, I don't think so. You're not supposed to re-order the terms, are you? If you were you would need only 11 terms.

sylar said:
Hey guys, i think you are missing one point. The question doesn't ask us to prove that there exists a strictly increasing sequence; it asks us to show that there exists an increasing sequence. That is, if all terms are equal to each other, then we have an increasing sequence.

what is your definition of an increasing sequence...because a constant sequence is in no way increasing...it's constant.

I imagine the intended definition is a sequence $a_1,a_2,\ldots$ with $a_1\le a_2\le\cdots$.

The actual theorem goes like this: if you have 101 distinct integers in a sequence, then you will have a 11-term subsequence that is INCREASING or DECREASING (like a lot of combinatorial theorems, it guarantees A or not A).

Or rather, if you want an increasing or decreasing sequence of n+1, then you need n^2+1 numbers.

The OP's statement can't possibly be right:

101, 100, 99, 98, ..., 1.

Last edited:
Gib Z said:
The statement isn't even true, though it may be if you apply stricter conditions. Take $$a_1 = a_2 = a_3 ... a_{101}$$ ie a constant sequence. No increasing sequence can be made out of those.

sutupidmath said:
yeah, like Gib Z pointed out, that statement is not true, unless we put some further conditions, like for at least 11 terms not to be equal to each other or sth like that!

Many texts use the word "increasing" to mean what others would call "non-decreasing" and "strictly increasing" to mean what others would call "increasing". I don't particularly like that terminology myself but I wouldn't take anyone to task for it!

But sylar has clearly misunderstood the question- it's not a matter of picking out 10 numbers from the sequence and putting them into increasing order. If that were what they were asking, you can obviously take any 101 number sequence and change the order so that the entire 101 were "increasing" (non-decreasing).

DragonFall has it right. His example, 101, 100, 99, ... does not have any increasing or non-decreasing subsequence in it. The problem must be to show that you can always find a sequence of 10 numbers that is either non-decreasing or non-increasing.

I was half thinking about the problem last night, and I almost worked out a sort of recursion on the general case (n+1, n^2+1); though I wasn't successful, I'm pretty sure the proof can be done by some sort of induction. I'd love to see a full proof if someone knows it.

what about the sequence 1, 3, 2, 4, 6, 5, 7, 9, 8...there is no non-increasing/decreasing sequence greater than 3 in this, no matter how far out you go.

certainly the conjecture is not true.

x_3n = 3n + 1, x_(3n + 1) = 3(n+1), x_(3n + 2) = 3n + 2. (n = 0, 1, 2...)

suppose the subsequence starts at x_3n. that means that x_3n through x_3n + 10 must either be non-decreasing or non-increasing. however, x_(3n+1) = 3n + 3 > 3n+2 = x_(3n + 2). so the subsequence is not non-decreasing. and x_(3n + 3) = x_3(n+1) = 3(n+1) + 1 = 3n + 4 > x_(3n+2). so the subsequence is not non-increasing.

starting at x_(3n + 1) and x_(3n + 2) leads to similar reasoning. But that exhausts the possibilities.

It's not a conjecture, it's a theorem, and the proof must go something like this:

Given n^2+1 numbers, there is an increasing or decreasing sequence of size n+1.

True for n=1.

Now suppose it's true for all n<k.

Now given (n+1)^2+1 numbers, partition the list into n^2+1 (A) and 2n+1(B). By induction hypothesis, WLOG, there is an increasing sequence within the first part of size n+1. Now if any of B is greater than the last element of one such sequence then we are done. Otherwise,

SOMETHING HAPPENS HERE.

QED.

matticus said:
x_3n = 3n + 1, x_(3n + 1) = 3(n+1), x_(3n + 2) = 3n + 2. (n = 0, 1, 2...)

suppose the subsequence starts at x_3n. that means that x_3n through x_3n + 10 must either be non-decreasing or non-increasing. however, x_(3n+1) = 3n + 3 > 3n+2 = x_(3n + 2). so the subsequence is not non-decreasing. and x_(3n + 3) = x_3(n+1) = 3(n+1) + 1 = 3n + 4 > x_(3n+2). so the subsequence is not non-increasing.

starting at x_(3n + 1) and x_(3n + 2) leads to similar reasoning. But that exhausts the possibilities.

A subsequence does not need to consist of consecutive elements of the sequence.

1 3 5 7 is a subsequence of 1 2 3 4 5 6 7

matticus said:
what about the sequence 1, 3, 2, 4, 6, 5, 7, 9, 8...there is no non-increasing/decreasing sequence greater than 3 in this, no matter how far out you go.

certainly the conjecture is not true.
No, the conjecture, as DragonFall restated it, was to find either a non-decreasing or non-increasing sub-sequence (not required to be consecutive): 1, 2, 6, etc. gives an increasing sequence.

The original statement was simply for an increasing sub-sequence. That certainly applies here.

Sorry for the delayed response. First, i want to thank all the posters who commented on these problem. Second, i admit that i misunderstood the problem and what i wrote here was not true. (Though still I'm right with the definition of an increasing sequence) The statement to prove is: In a sequence of (n^2)+1 distinct elements, there exists an increasing or decreasing subsequence of length n+1.

Our instructor asks questions at the end of the lectures just for fun and this was one of these problems. Yesterday, he told me that this is a very nice problem and he didn't know about it before he saw the proof in a mathematics journal. He added that the proof method was strong induction.

So if you prove the statement or see the proof somewhere, can you post here please? Thanks.

## 1. How do you find an increasing sequence of 11 terms?

To find an increasing sequence of 11 terms, you need to follow a few steps. First, determine the starting number of the sequence. Then, find the common difference between each term. Next, use the formula an = a1 + (n-1)d to find the remaining terms in the sequence. Lastly, check your solution by plugging in the values into the formula and ensuring that each term is larger than the previous one.

## 2. What is the starting number of an increasing sequence?

The starting number of an increasing sequence is the first number in the sequence. It is also known as the initial term or first term.

## 3. How do you determine the common difference in an increasing sequence?

The common difference in an increasing sequence is the constant value that is added to each term to get the next term in the sequence. To determine the common difference, subtract the first term from the second term and continue to do so for consecutive terms until you get the same value. This value is the common difference.

## 4. Can an increasing sequence have negative numbers?

Yes, an increasing sequence can have negative numbers. The key is that each term in the sequence must be larger than the previous one. This means that the sequence can increase or decrease as long as each term is larger than the previous one.

## 5. What is the difference between an increasing sequence and a decreasing sequence?

An increasing sequence is a sequence in which each term is larger than the previous one, while a decreasing sequence is a sequence in which each term is smaller than the previous one. In other words, an increasing sequence goes up and a decreasing sequence goes down.

• General Math
Replies
1
Views
1K
• General Math
Replies
3
Views
2K
• General Math
Replies
4
Views
2K
• Calculus and Beyond Homework Help
Replies
8
Views
2K
• General Math
Replies
4
Views
1K
• General Math
Replies
6
Views
2K
• General Math
Replies
1
Views
2K
• General Math
Replies
16
Views
2K
• General Math
Replies
55
Views
4K
• General Math
Replies
6
Views
1K