2
$\begingroup$

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

  • 0
    In MSE the title of a question should focus the *contents* of a problem rather than your comment, your opinion or your feeling about it. Please stay in tune with that behave.2012-07-31

3 Answers 3

2

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.

2

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.

0

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

  • 0
    @RahulNarain, I just edit questions which proposed on the review page as bad formatted.2012-07-31