Question 3
Let $c_n$ be a sequence which is defined recursively as follows: $c_0 = 1$, $c_{2n+1} = c_n$ for $n \ge 0$, and $c_{2n} = c_n + c_{n-2^e}$ for $n \gt 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} \binom{2n+2}{n+1}.
$$
$$
\sum_{i=0}^{2^n-1} c_i = \frac{1}{n+2} \binom{2n+2}{n+1}.
$$