In the book I'm reading, they introduced us to the following result:
Corollary 5.4: For all positive integers $n$, the number of all compositions of $n$ is $2^{n-1}$.
Proof: We prove the statement by induction on $n$. For $n = 1$, the statement is true as the integer $1$ has one composition. Now assume that the statement is true for $n$, and take all $2^{n-1}$ compositions of $n$. For each such composition $C$, we will define two different compositions of $n+1$. First, add one to the first element of $C$. This way we get a composition of $n + 1$ with the first element at least $2$. Second, take $C$, and write an additional $1$ to its front. This way we get a composition of n + 1 with first element 1. It is clear that different compositions of $n$ lead to different compositions of $n + 1$ this way. Each decomposition of $n + 1$ can be obtained in exactly one of these two ways. Therefore, it follows that $n + 1$ has twice as many compositions as $n$, which was to be proved.
(From: Miklos Bona, A Walk Through Combinatorics, 4th edition)
Now the given problem:
What is the number of all compositions of $n$ in which the first part is not $2$?
My thoughts:
- It's maybe easier to find the number of compositions where the first part is $2$.
- I think the book wants me to use an argument based on the proof for the number of all compositions.
My work to get closer to the solution:
- Fnd all compositions of some small $n$.
- For $n=2$, there are two compositions, one has a $2$ in front.
- For $n=3$, there are four compositions, one has a $2$ in front.
- For $n=4$, there are eight compositions, two have a $2$ in front.
Conjecture: For $n \ge 3$, there are in total $2^{n-1}$ compositions, and $1/4$ of those have a $2$ in front, so the total number of compositions with a $2$ in front is given by $2^{n-1} \times 1/4 = 2^{n-3}$.
Proof:
- Assume $n \ge 3$, take all compositions of $n-2$, by Corollary 5.4 there are $2^{n-3}$ of them. Following the procedure described in the proof for said corollary, we can create all compositions of $n$ from the compositions of $n-2$ in the following way:
- We are interested in the compositions created where we first add an additional $1$ in front of each composition of $n-2$ and then we add $1$ to the first element of those, this will surely create compositions of $n$ that have a $2$ in front. From the diagram we can see that from the total $2^{n-1}$ compositions of $n$, $1/4$ of them has this property. Hence there are $2^{n-1} \times 1/4 = 2^{n-3}$ compositions of $n$ which have a $2$ in front.
With that result it should be straightforward to answer the initial question. But is my given proof formally OK? First, it doesn't treat the special case for $n=2$ and I'm a bit worried that it relies too much on "proof by picture"?
I think You may overcomplicate things here. Take any composition of $n$ which have $2$ as the first part. If you delete this $2$, You will end up with a composition of $n-2$ and there are $2^{n-2-1}$ of them