Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have the following question as homework, and I am still clueless as to how to approach these problems. Just when I think I have a hand of how to solve card related problems, I get thrown another that just leaves me clueless. Any who, I would appreciate any help afforded in explaining the problem below

How many strictly increasing sequences of integers are there that begin with $1$ and end with $n$, where $n>1$? For example, if $n =4$, there are $4$ such sequences: $1,4;\quad 1,2,4;\quad 1,3,4;\quad 1,2,3,4$ . Prove your answer with strong induction

share|improve this question
2  
Have you tried a few small cases and found a pattern? This should be your first move. –  Hans Parshall Sep 20 '11 at 13:42
1  
When asking homework related questions, please add the additional tag [homework] the next time. Also try avoid such titles and favour titles which reveal a bit about the actual question (I couldn't really think of a proper title here myself at the moment). –  Asaf Karagila Sep 20 '11 at 13:44
2  
Large Hint: First make a very careful list of the possibilities for $n=2$; $n=3$; $n=4$; $n=5$. The counts should be $1$, $2$, $4$, $8$ respectively. Now let's deal with $n=6$. Any good sequence for $6$ has one of the following shapes: (i) Any one of the earlier sequences, followed by a $6$ or (ii) a bare $6$. So how many sequences are there for $n=6$ (count them without listing). By the way, there are better ways to do the job, without using strong induction! –  André Nicolas Sep 20 '11 at 14:00
1  
HINT Any such sequence has a $1$ in the beginning and an $n$ at the end. The middle elements (those strictly between $1$ and $n$) may or may not be present. But if I told you which of the middle elements are present in the sequence, can you write down the sequence uniquely? –  Srivatsan Sep 20 '11 at 14:02
1  
@André Careful, you cannot have a bare $6$ since the sequence must start with $1$. (The idea works fine though once you take care of this.) –  Srivatsan Sep 20 '11 at 14:04
show 5 more comments

3 Answers

Let's call strictly increasing sequences beginning with 1 and ending with $n$ "good"; let $s(n)$ be the number of good sequences for $n$.

Note there is only one good sequence for each $n$ with no terms between $1$ and $n$. Consider all good sequences with middle terms.

If we have a good sequence $1, a_1, \ldots, a_k, n$, how many choices do we have for $a_k$? We could have $a_k = 2$, $a_k = 3$, $\ldots$, or $a_k = n - 1$.

How many good sequences could we possibly have for each $a_k$? Observe this is completely determined by the increasing sequence $1, a_1, \ldots, a_k$, which is a good sequence (for $a_k$ rather than $n$). This is counted by $s(a_k)$. If you have an inductive hypothesis for the values of $s(2), \ldots, s(n-1)$, then you have a value (in terms of $a_k$) for each $s(a_k)$. Add each of these up for each possible value of $a_k$, and this will be very close to $s(n)$.

I'll leave it to you to find the pattern so you have a value for each $a_k$ in your inductive hypothesis.

share|improve this answer
add comment

These sequences are in $1$-$1$ correspondence with the subsets of $\{1,2,\ldots,n\}$ containing $1$ and $n$. There are $2^{n-2}$ such subsets.

share|improve this answer
add comment

That's just binary counting no ? You always have $1$ and $n$ in you sequence. Let's focus on digits $2$ to $n-1$. Write it in a tabluar : you have $n-2$ columns entiteled $(n-1)$, $(n-2)$, $\ldots$, $4$, $3$, $2$. write a $1$ in a column if the digit is in the sequence, and $0$ if not... and count the number of lines corresponding to your constraint "strictly inclreasing" (don't forget the first one corresponding to sequence "1-n", i.e. 0 everywhere in cols $2$ to $(n-1)$). Don't you see anything ? (for example that you have $2^{(n-2)}$ possibilities ?)

share|improve this answer
    
@Norbert: I don't really see the need to bump a 10-month-old question to the front page just to add some LaTeX tags. –  Rahul Jul 31 '12 at 6:56
    
@RahulNarain, I just edit questions which proposed on the review page as bad formatted. –  Norbert Jul 31 '12 at 6:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.