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.



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.

  • $\begingroup$ nice $~~~~~~~~~$ $\endgroup$ – 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}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy