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
 A: 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.
A: 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.
A: 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 ?)
