<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] You're almost there. You just have to use your hypothesis in your final case for $k+1$.
You found for $n=k$ that
$$2^0+2^1+2^2+...+2^{k-2}+1=2^{k-1}.$$
You want to prove for $n=k+1$ that
$$2^0+2^1+2^2+...2^{k-2}+2^{k-1}+1=2^{k},$$
Fill in the first equation into the second
\begin{align*}
2^0+2^1+2^2+...+ 2^{k-2}+&(2^0+2^1+2^2+...+2^{k-2}+1)+1\\
=2&(2^0+2^1+2^2+...+2^{k-2}+1)
\end{align*}
Now using the induction hypothesis again
\begin{align*}
&=2(2^{k-1})\\&=2^{k}.
\end{align*}
By mathematical induction we have now proven this for all $n\geq 5$.
The theorem does however hold for any $n\geq 2$, so I suggest making your basecase be $n=2$.
</s>