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?

0)
 Follow
 0 followers
 10 badges
 Send a private message to 0)
 Thread Starter
Offline10ReputationRep: Follow
 1
 01022010 21:46
Last edited by 0); 01022010 at 22:07. 
DFranklin
 Follow
 60 followers
 17 badges
 Send a private message to DFranklin
Online17ReputationRep: Follow
 2
 01022010 21:52
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? 
0)
 Follow
 0 followers
 10 badges
 Send a private message to 0)
 Thread Starter
Offline10ReputationRep: Follow
 3
 01022010 21:56
(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? 
0)
 Follow
 0 followers
 10 badges
 Send a private message to 0)
 Thread Starter
Offline10ReputationRep: Follow
 4
 01022010 22:05
I've also edited my OP to use 'or' instead of 'and'. I think (hope) it's correct now.

DFranklin
 Follow
 60 followers
 17 badges
 Send a private message to DFranklin
Online17ReputationRep: Follow
 5
 01022010 22:13
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...) 
0)
 Follow
 0 followers
 10 badges
 Send a private message to 0)
 Thread Starter
Offline10ReputationRep: Follow
 6
 01022010 22:20
(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...)
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. 
DFranklin
 Follow
 60 followers
 17 badges
 Send a private message to DFranklin
Online17ReputationRep: Follow
 7
 01022010 22:32
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. 
0)
 Follow
 0 followers
 10 badges
 Send a private message to 0)
 Thread Starter
Offline10ReputationRep: Follow
 8
 01022010 22:43
(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.
'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) 
DFranklin
 Follow
 60 followers
 17 badges
 Send a private message to DFranklin
Online17ReputationRep: Follow
 9
 01022010 22:53
What you have is close, but not the same. Can you post your hint, using the exact wording?

0)
 Follow
 0 followers
 10 badges
 Send a private message to 0)
 Thread Starter
Offline10ReputationRep: Follow
 10
 01022010 22:59
(Original post by DFranklin)
What you have is close, but not the same. Can you post your hint, using the exact wording?
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.Last edited by 0); 01022010 at 23:06. 
DFranklin
 Follow
 60 followers
 17 badges
 Send a private message to DFranklin
Online17ReputationRep: Follow
 11
 01022010 23:17
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).

0)
 Follow
 0 followers
 10 badges
 Send a private message to 0)
 Thread Starter
Offline10ReputationRep: Follow
 12
 01022010 23:38
(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). 
DFranklin
 Follow
 60 followers
 17 badges
 Send a private message to DFranklin
Online17ReputationRep: Follow
 13
 01022010 23:41
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?] 
0)
 Follow
 0 followers
 10 badges
 Send a private message to 0)
 Thread Starter
Offline10ReputationRep: Follow
 14
 01022010 23:47
(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?]
I thought a_3,a_2,a_1 would be the longest descending sequence ending in a_1. 
Straightpath
 Follow
 0 followers
 0 badges
 Send a private message to Straightpath
Offline0ReputationRep: Follow
 15
 01022010 23:49
From what exam board is this?

DFranklin
 Follow
 60 followers
 17 badges
 Send a private message to DFranklin
Online17ReputationRep: Follow
 16
 01022010 23:51
(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.
To put it another way, a_3, a_2, a_1 is NOT a subsequence of a_1, a_2, a_3. 
0)
 Follow
 0 followers
 10 badges
 Send a private message to 0)
 Thread Starter
Offline10ReputationRep: Follow
 17
 02022010 00:03
(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.
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. 
0)
 Follow
 0 followers
 10 badges
 Send a private message to 0)
 Thread Starter
Offline10ReputationRep: Follow
 18
 02022010 00:05
(Original post by Straightpath)
From what exam board is this? 
DFranklin
 Follow
 60 followers
 17 badges
 Send a private message to DFranklin
Online17ReputationRep: Follow
 19
 02022010 00:15
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:ShowIn 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:ShowNow, 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:ShowNow 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. 
0)
 Follow
 0 followers
 10 badges
 Send a private message to 0)
 Thread Starter
Offline10ReputationRep: Follow
 20
 02022010 14:16
Thank you for your help. I have one more question but I'll make a new thread.
 Fp1 mei ocr proof by induction
 Proof By Induction
 FP1: proof by induction
 Fp1 proof by induction  lost in the mark scheme
 Proof by Induction Question
 fp1 proof by induction question  confusing
 Fp1 proof by induction recurrence
 Stuck with fp1 proof by induction sinplification
 Proof By Induction Question
 FP1: proof by induction

University of Leeds

Loughborough University

Queen Mary University of London

Royal Holloway University of London

Royal Holloway University of London

Finance and Mathematics (Including Foundation Year)
University of Essex

University of Oxford

Mathematics with Integrated Foundation Year
University of Brighton

Mathematics, Operational Research, Statistics, Economics (MORSE)
University of Warwick

University of St Andrews
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.
 SherlockHolmes
 Notnek
 charco
 Mr M
 Changing Skies
 F1's Finest
 rayquaza17
 RDKGames
 davros
 Gingerbread101
 Kvothe the Arcane
 TeeEff
 The Empire Odyssey
 Protostar
 TheConfusedMedic
 nisha.sri
 claireestelle
 Doonesbury
 furryface12
 Amefish
 harryleavey
 Lemur14
 brainzistheword
 Rexar
 Sonechka
 TheAnxiousSloth
 EstelOfTheEyrie
 CoffeeAndPolitics
 an_atheist
 Labrador99
 EmilySarah00