<s>[INST] induction proof: number of compositions of a positive number $n$ is $2^{n-1}$ So my problem was to find the formula for the number of composition for a positive number $n$. Then prove its validity. I found the formula which was $2^{n-1}$. Having trouble with the induction.
$$Claim:2^0+2^1+2^2+...+(2^{n-2}+1)=2^{n-1}$$
When $n=5$ $$ 1+2+4+(2^{5-2}+1)=2^{5-1}$$
$$ 1+2+4+(2^{3}+1)=2^{4}$$
$$ 1+2+4+(8+1)=16$$
$$ 16=16$$
Assume that $n=k$
$$2^0+2^1+2^2+...+(2^{k-2}+1)=2^{k-1}$$
Now show for $k+1$
$$2^0+2^1+2^2+...+(2^{k-1}+1)=2^{k}$$
Don't know what to do after. Help is appreciated.
$$2^0+2^1+2^2+...+(2^k)+(2^{k-1}+1)=2^{k}$$
 [/INST] Let's return to the original problem.  A composition of a positive integer $n$ is a way of writing $n$ as the sum of a sequence of strictly positive integers.
For $n = 5$, there are indeed $2^{5 - 1} = 2^4 = 16$ compositions since each composition corresponds to placing or omitting an addition sign in the four spaces between successive ones in a row of five ones.
\begin{array}{c c}
\text{composition} & \text{representation}\\ \hline
5 & 1 1 1 1 1\\
4 + 1 & 1 1 1 1 + 1\\
3 + 2 & 1 1 1 + 1 1\\
3 + 1 + 1 & 1 1 1 + 1 + 1\\
2 + 3 & 1 1 + 1 1 1\\
2 + 2 + 1 & 1 1 + 1 1 + 1\\
2 + 1 + 2 & 1 1 + 1 + 1 1\\
2 + 1 + 1 + 1 & 1 1 + 1 + 1 + 1\\
1 + 4 & 1 + 1 1 1 1\\
1 + 3 + 1 & 1 + 1 1 1 + 1\\
1 + 2 + 2 & 1 + 1 1 + 1 1\\
1 + 2 + 1 + 1 & 1 + 1 1 + 1 + 1\\
1 + 1 + 3 & 1 + 1 + 1 1 1\\
1 + 1 + 2 + 1 & 1 + 1 + 1 1 + 1\\
1 + 1 + 1 + 2 & 1 + 1 + 1 + 1 1\\
1 + 1 + 1 + 1 + 1 & 1 + 1 + 1 + 1 + 1
\end{array}
Using this observation, we can write a combinatorial proof.  A positive integer $n$ has $2^{n - 1}$ compositions since each composition is uniquely determined by choosing to include or omit an addition sign in each of the $n - 1$ spaces between successive ones in a row of $n$ ones.  
</s>