One step away from finishing my proof but not sure how to do this sum:
$$\sum_{k=0}^{i+1} \begin{pmatrix} i\\ k-1\end{pmatrix}$$
If it's not easy, if you could explain why, that would be great so I remember for next time
This is what I've done so far $$\sum_{k=0}^{i+1} \begin{pmatrix} i+1\\ k\end{pmatrix} = \sum_{k=0}^{i+1} (\begin{pmatrix} i\\ k\end{pmatrix} + \begin{pmatrix}i\\ k-1\end{pmatrix}) = 2^{i} + \sum_{k=0}^{i+1} \begin{pmatrix}i\\ k-1\end{pmatrix}$$
Reading my own answer is this correct?:
$$\sum_{k=0}^{i+1} (\begin{pmatrix} i\\ k\end{pmatrix} = 2^{i} $$
You can recognize this as Newtons binomium (http://en.wikipedia.org/wiki/Binomial_theorem), which says that $$ \sum_{i=0}^{n}\binom{n}{i}x^iy^{n-i} = (x+y)^n. $$ You can prove this by induction. In your case the answer would be $2^i$.
An intuitive way to see the solution is to realize that this sum represents all possible ways to choose a subset from a set of $i$ elements. For each element in the whole set you can choose to include it or not, giving two different subsets. Thus the total sum must be $2^i$.