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}$$

What you know:  $\color{blue}{2^0+2^1+2^2+...+(2^{k-2}+1)=2^{k-1}}$
What you want to show:  $\color{green}{2^0+2^1+2^2+...+(2^{k-1}+1)=2^{k}}$
Use what you know:
$\color{green}{2^0+2^1+2^2+...+2^{k-2} + (2^{k-1}+1)} =$
$\color{blue}{2^0+2^1+2^2+...+2^{k-2}} + (\color{green}{2^{k-1}} + \color{blue}1) =$
$\color{blue}{2^0+2^1+2^2+...+(2^{k-2}+1)}+\color{green}{2^{k-1}}=$
$\color{blue}{2^{k-1}} + \color{green}{2^{k-1}}=$
$\color{green}{2\times 2^{k-1}} =$
$\color{green}{2^{(k-1) + 1}} =$
$\color{green}{2^k}$.
