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

  • 2
    Have you tried a few small cases and found a pattern? This should be your first move.2011-09-20
  • 0
    Yes, but that has not yielded an idea to solve this yet.2011-09-20
  • 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!2011-09-20
  • 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?2011-09-20
  • 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.)2011-09-20
  • 0
    @Srivatsan Narayanan: Thanks, by a bare $6$ I *meant* $(1,6)$. But that's definitely not what I *wrote*.2011-09-20
  • 0
    @AndréNicolas: +1 for mentioning that there are better ways to do this than strong induction.2011-09-20
  • 0
    @Hans Parshall: I thought however that I should give the strong induction idea, since it is probably what the instructor/book had in mind.2011-09-20
  • 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