# 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?

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.
• nice $~~~~~~~~~$ – user838035 Dec 7 '20 at 3:41
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}