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}$$
 A: 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}$$.
A: 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.  
A: $n=k$ $$2^0+2^1+2^2+...+(2^{k-2}+1)=2^{k-1}$$ so
$$\underbrace{2^0+2^1+2^2+...+2^{k-2}}=\overbrace{2^{k-1} -1}$$
Now show for k+1
$$\underbrace{2^0+2^1+2^2+...+2^{k-2}}+(2^{k-1}+1)=\overbrace{2^{k-1} -1}+(2^{k-1}+1)$$
$$=2^{k-1}+2^{k-1}=2*2^{k-1}=2^{k}$$
A: 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$.
A: 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}$.
