Turn on thread page Beta
 You are Here: Home >< Maths

# Induction proof watch

1. I'm doing a question which has lead to this statement which I'm trying to prove (I think this is correct):

If m,n are positive integers and , are sequences of positive integers with distinct and for all

then there exists an and a such that

or .

It looks like I need to use induction to prove this. The case n=1,m=1 is clearly true so assume true for n=p, m=q. The case n=p+1, m=q+1 gives the equation

but I'm not sure where to go from here. Can someone help?
2. I don't see that the case n=m=1 is true.

Take x_1 = x_2 = 1, y_1 = y_2 = 2

For what k is x_k = m+1?
3. (Original post by DFranklin)
I don't see that the case n=m=1 is true.

Take x_1 = x_2 = 1, y_1 = y_2 = 2

For what k is x_k = m+1?
Oops I forgot to say that the pairs must be distinct.
4. I've also edited my OP to use 'or' instead of 'and'. I think (hope) it's correct now.
5. If all the x_i are distinct, and you have mn+1 of them, then at least one x_i >= mn+1 (pigeonhole) and so x_i >= m+1.

(I suspect you are still not asking the right question...)
6. (Original post by DFranklin)
If all the x_i are distinct, and you have mn+1 of them, then at least one x_i >= mn+1 (pigeonhole) and so x_i >= m+1.

(I suspect you are still not asking the right question...)
The initial question is

Prove that in any sequence of distinct real numbers, there are either numbers (not necessarily consecutive) that occur in increasing order, or that occur in decreasing order.

For each , I set the pair as the longest increasing and decreasing subsequences ending with . I then developed the assumptions in my statement (OP) which I thought were correct and then thought that proving the statement would prove the above theorem.
7. I don't see where your assumptions in the OP come from, and (knowing the standard proof of the problem you've just posted), they seem a lot stronger than are usually used to complete the proof. So I am inclined to think you've gone wrong somewhere, to be honest.

But if your assumptions are correct, I believe my post #5 is a valid proof.
8. (Original post by DFranklin)
I don't see where your assumptions in the OP come from, and (knowing the standard proof of the problem you've just posted), they seem a lot stronger than are usually used to complete the proof. So I am inclined to think you've gone wrong somewhere, to be honest.

But if your assumptions are correct, I believe my post #5 is a valid proof.
Does the standard proof you speak of use the idea of x_i and y_i (defined above) because I was given a hint which uses them.

'x_i +y_i =mn+2' came from looking at small values of m and n and noticing that the pairs (x_i,y_i) would be a list of the ways of summing to mn+2 with each (x_i,y_i) appearing once e.g. m=1,n=4 the pairs are

(2,4),(4,2),(1,5),(3,3),(5,1)
9. What you have is close, but not the same. Can you post your hint, using the exact wording?
10. (Original post by DFranklin)
What you have is close, but not the same. Can you post your hint, using the exact wording?
For each term a_i, consider the ordered pair (x_i, y_i), where x_i and y_i are the lengths of the longest increasing and decreasing subsequences ending with a_i. The conclusion holds if there is an i for which x_i ≥ m + 1 or y_i ≥ n + 1.

Edit: Oh I noticed that I didn't use the word 'lengths' earlier. Is this what you mean by it almost being correct? Sorry about all the mistakes.
11. In the proof I'm familiar with, x_i is the length of the longest ascending sequence starting with a_i, but y_i is the length of the longest descending sequence ending with a_i. (You can swap ascending and descending etc., but you need one sequence to start with a_i and one to end with a_i).
12. (Original post by DFranklin)
In the proof I'm familiar with, x_i is the length of the longest ascending sequence starting with a_i, but y_i is the length of the longest descending sequence ending with a_i. (You can swap ascending and descending etc., but you need one sequence to start with a_i and one to end with a_i).
Hmmm but with that definition, wouldn't that make x_i equal to y_i for all i?
13. a_1 =1, a_2 =2, a_3 = 3.

x_1 = 3 (longest ascending sequence starting with a_1 is a_1, a_2, a_3).
y_1 = 1 (longest descending sequence ending with a_1 is a_1. (Since a_1 is the first element, the only possible sequence ending in a_1 is a_1 itself).

[Note: you do realise that when we find these sequences a_i a_j a_k (etc.) we need i < j < k (etc.) don't you?]
14. (Original post by DFranklin)
[Note: you do realise that when we find these sequences a_i a_j a_k (etc.) we need i < j < k (etc.) don't you?]
No I didn't realise that. Why do you need to assume this?

I thought a_3,a_2,a_1 would be the longest descending sequence ending in a_1.
15. From what exam board is this?
16. (Original post by 0-))
No I didn't realise that. Why do you need to assume this?

I thought a_3,a_2,a_1 would be the longest descending sequence ending in a_1.
Because you're looking for a subsequence, and by definition, the indices in a subsequence are increasing.

To put it another way, a_3, a_2, a_1 is NOT a subsequence of a_1, a_2, a_3.
17. (Original post by DFranklin)
Because you're looking for a subsequence, and by definition, the indices in a subsequence are increasing.

To put it another way, a_3, a_2, a_1 is NOT a subsequence of a_1, a_2, a_3.
OK I should have known that.

Now I'm thinking that there's a mistake in the question. Another hint says to find (x_i,y_i) for the sequence e.g. 2,4,1,3,5. This doesn't really show anything if I use the proper subsequence definition. Maybe my lecturer also got confused and meant any sequence with elements taken from the original sequence (in any order)? Or maybe he should have written the question like you did.
18. (Original post by Straightpath)
From what exam board is this?
University maths.
19. I think it's very unlikely he got confused, although the hint doesn't really fit in with the proof I have in mind either. (Obviously, if you do it, you'll find that there's an x_i or y_i that is at least 3, since otherwise the result you're trying to prove would be false).

What's more revealing is to think what would have to happen if every x_i and y_i was < 3. (or more generally, if the result you're trying to prove was false).

[N.B. 3 nested spoilers - I've given away most of the answer by the end, but as I'm going to bed now... It's not too difficult to find a solution by googling, as well].

Spoiler:
Show
In that case, there are at most mn values for the pairs (x_i, y_i), so if there are mn+1 pairs, we can find two identical ones. That is, we can find distinct i, j with x_i = x_j and y_i = y_j.

Spoiler:
Show
Now, translate that back into the terms of the original problem. We have two elements a_i and a_j and for both of them, the longest ascending subsequence starting with them is x_i and the longest descending subsequence ending with them has length x_j.

Spoiler:
Show
Now show that we can always use one of a_i, a_j to extend one of the sequences involving the other one. Which contradicts that we had the longest subsequence. So we have a contradiction, so our assumption that the result was false was incorrect and we're done.
20. Thank you for your help. I have one more question but I'll make a new thread.

Reply
Submit reply
Turn on thread page Beta
TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: February 2, 2010
Today on TSR

### Students as customers

Are unis responsible for your grades?

### University open days

• Sheffield Hallam University
City Campus Postgraduate
Wed, 17 Oct '18
• Northumbria University
All faculties Undergraduate
Wed, 17 Oct '18
• Staffordshire University
Nursing and Midwifery Undergraduate
Wed, 17 Oct '18
Poll
Useful resources

## Make your revision easier

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

Can you help? Study help unanswered threads

## Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.