US-TST 2011 Problem 5

Let $c_n$ be a sequence which is defined recursively as follows: $c_0 = 1$ , $c_{2n+1} = c_n$ for $n \geq 0$ , and $c_{2n} = c_n + c_{n-2^e}$ for $n > 0$ where $e$ is the maximal nonnegative integer such that $2^e$ divides $n$ . Prove that $$\sum_{i=0}^{2^n-1} c_i = \frac{1}{n+2} {2n+2 \choose n+1}.$$