<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 actually don't need induction to prove this. There's a telescoping effect.
$$Claim:2^0+2^1+2^2+...+(2^{n-2}+1)=2^{n-1}$$
Carry the one.
$$(1 + 2^0)+2^1+2^2 + ... + 2^{n-2}=2^{n-1}$$
$1 = 2^0$
$$(2^0 + 2^0)+2^1+2^2 + ... + 2^{n-2}=2^{n-1}$$
Collapse the parentheses
$$(2^1 + 2^1) + 2^2 + ... + 2^{n-2}=2^{n-1}$$
Collapse the parentheses.
$$(2^2 + 2^2) + ... + 2^{n-2}=2^{n-1}$$
Keep doing this until
$$2^{n-2} + 2^{n-2} = 2^{n-1}$$.
</s>