# Counting and logic is kicking my behind I

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

-
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
Yes, but that has not yielded an idea to solve this yet. – user10695 Sep 20 '11 at 13:52
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
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
@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

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.

-

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.

-

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 ?)

-
@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