Recursive relation induction problem: $c_n = \frac{1}{2^n} \cdot \sum_{k \text{ even}}^{0~ \leq ~k~ \leq ~n} {n \choose k}c_k$ This is part of problem 18 of chapter 13 of Michael Spivak's Calculus:
Define $c_n = \int_{0}^{1}x^n dx$
(b) Prove: $$c_n = \frac{1}{2^n} \cdot \sum_{k \text{ even}}^{0~ \leq ~k~ \leq ~n} {n \choose k}c_k$$
(c) Prove $c_n = \frac{1}{n+1}$ from this (without calculating the integral).
Note the actual question in the book is more than this, I am just condensing it to the parts I'm stuck on. I was able to do (b), but not (c). It seems to me to be another induction problem, but I am going in circles. So I assume it's true for $\forall n \leq p$, i.e. $ \forall n \leq p : c_n = \frac{1}{n+1}$. Then for $c_{p+1}$, we have:
$$c_{p+1} = \frac{1}{2^{p+1}} \cdot \sum_{k \text{ even}}^{0~ \leq ~k~ \leq ~{p+1}} {p+1 \choose k}c_k$$
Now already there's some technical issues as to whether the last term in the sum will be $c_{p+1}$ or $(p+1)c_p$, depending on whether $p+1$ is even or odd. So I split up the formula into those 2 separate cases, like so:
$$c_{n} = \frac{1}{2^{n} - 1} \cdot \sum_{k~ =~ 0}^{k ~= ~n/2-1} {n \choose 2k}c_{2k} ~~~: ~~\text{for n = even}$$
$$c_{n} = \frac{1}{2^{n}} \cdot \sum_{k~ =~ 0}^{k ~= ~(n-1)/2} {n \choose 2k}c_{2k} ~~~~~~: ~~\text{for n = odd}$$
Ok so we'll probably have to do 2 separate proofs by induction, one for when $p$ is odd, one when $p$ is even. Also we'll need to prove both the $n = 0$ and $n = 1$ base cases, but that's trivial, no problems there.
Let's try when $p$ is even. So we assume $p$ is even and $ \forall n \leq p : c_n = \frac{1}{n+1}$. Then $p+1$ is odd, so:
$$c_{p+1} = \frac{1}{2^{p+1}} \cdot \sum_{k~ =~ 0}^{k ~= ~p/2} {p+1 \choose 2k}c_{2k}$$
$$~~~~~~~~~~~~~~= \frac{1}{2^{p+1}} \cdot \sum_{k~ =~ 0}^{k ~= ~p/2} {p+1 \choose 2k}\frac{1}{2k+1}$$
And now I am stuck.
I need to somehow show $\frac{1}{2^{p+1}} \cdot \sum_{k~ =~ 0}^{k ~= ~p/2} {p+1 \choose 2k}\frac{1}{2k+1} = \frac{1}{p+2}$. I tried using the identity ${n+1 \choose k} = {n \choose k} + {n \choose k-1}$, which gives us:
$$c_{p+1} = \frac{1}{2^{p+1}} \cdot \sum_{k~ =~ 0}^{k ~= ~p/2} {p+1 \choose 2k}\frac{1}{2k+1}$$
$$~~~~~~~~~~~~~~~~~~~~~~~~~~= \frac{1}{2^{p+1}} \cdot \sum_{k~ =~ 0}^{k ~= ~p/2} \Bigr[{p \choose 2k} + {p \choose 2k-1}\Bigr]\frac{1}{2k+1}$$
$$~~~~~~~~~~~~~~~~~~~~~~~~~= \frac{1}{2^{p+1}} \cdot \biggr[c_p ~+~ \Bigr[ \sum_{k~ =~ 0}^{k ~= ~p/2} {p \choose 2k-1}\frac{1}{2k+1}\Bigr]\biggr]$$
But now how to deal with this new summation that runs on odd numbers; $2k - 1$, instead of the even numbers; $2k$, that we have in our definition of $c_p$ (which we need to incorporate somehow)? I tried to transform the ${p \choose 2k - 1}$ to ${p \choose 2k - 2}$ or ${p \choose 2k}$, using the identity ${n \choose k} = \frac{n - k + 1}{k}{n \choose k - 1}$ but the coefficients didn't cancel and looked very ugly so now I have no ideas.
Any?
 A: You say you are stuck on proving $$\frac{1}{2^{p+1}}\sum_{k=0}^{p/2}\binom{p+1}{2k}\frac{1}{2k+1}=\frac{1}{p+2}$$ when $p$ is even. We have
$$\frac{1}{2^{p+1}}\sum_{k=0}^{p/2}\binom{p+1}{2k}\frac{1}{2k+1}=\frac{1}{2^{p+1}(p+2)}\sum_{k=0}^{p/2}\binom{p+2}{2k+1}.$$ The sum computes the sum of coefficients of odd power terms in polynomial $f(x)=(1+x)^{p+2}$. That is equal to $(f(1)-f(-1))/2$ for any polynomial $f$. In this case it evaluates to $2^{p+1}$, which is what you want.
A: Note that $$\sum_{k \ge 0} a_{2k} = \sum_{k \ge 0} \frac{1+(-1)^k}{2}a_k.$$
Taking $a_k=\binom{p+1}{k}\frac{1}{k+1}$ yields
\begin{align}
\frac{1}{2^{p+1}}\sum_{k\ge 0} \binom{p+1}{2k}\frac{1}{2k+1}
&=\frac{1}{2^{p+1}}\sum_{k\ge 0} \frac{1+(-1)^k}{2} \binom{p+1}{k}\frac{1}{k+1} \\
&=\frac{1}{2^{p+1}(p+2)}\sum_{k\ge 0} \frac{1+(-1)^k}{2} \binom{p+2}{k+1} \\
&=\frac{1}{2^{p+2}(p+2)}\left(\sum_{k\ge 0} \binom{p+2}{k+1} - \sum_{k\ge 0} (-1)^{k+1} \binom{p+2}{k+1}\right) \\
&=\frac{((1+1)^{p+2}-(p+2)) - ((1-1)^{p+2}-(p+2))}{2^{p+2}(p+2)} \\
&=\frac{2^{p+2}}{2^{p+2}(p+2)} \\
&=\frac{1}{p+2}.
\end{align}
