prove $\sum_{k=0}^{3n+2}\frac{(-1)^k}{6n+5-k}\binom{6n+5-k}{k}=\frac{1}{6n+5}$

Question

I want to prove that $$\sum_{k=0}^{3n+2}\frac{(-1)^k}{6n+5-k}\binom{6n+5-k}{k}=\frac{1}{6n+5}$$ Let $\displaystyle f_n(x)=\sum_{k=0}^{\lfloor (n+1)/2\rfloor}\binom{n-k+1}{k}x^{n-k}$, then we have a recurrence relation $$f_n(x)=xf_{n-1}(x)+xf_{n-2}(x) \quad ; \quad f_1(x)=x+1,\quad f_0(x)=1$$

Hence, $$\sum_{k=0}^{3n+2}\frac{(-1)^k}{6n+5-k}\binom{6n+5-k}{k}=\int_{-1}^0f_{6n+4}(x)dx$$

What will I do from here? Thank you.

Answer 1

Chebyshev polynomials of the second kind have the following closed form:

$$ U_n(x) = \sum_{r=0}^{\lfloor n/2\rfloor}\binom{n-r}{r}(-1)^r (2x)^{n-2r} \tag{1} $$ hence:

$$ x^{n-1}\,U_n(x/2) = \sum_{r=0}^{\lfloor n/2\rfloor}\binom{n-r}{r}(-1)^r (x)^{2n-2r-1} \tag{2} $$

and: $$ S_n=\sum_{r=0}^{\lfloor n/2\rfloor}\binom{n-r}{r}\frac{(-1)^r}{n-r} = 2\int_{0}^{1}x^{n-1} U_n(x/2)\,dx. \tag{3} $$ By substituting $x=2\cos\theta$, the last integral turns into an elementary integral and we get: $$\boxed{ \sum_{r=0}^{\lfloor n/2\rfloor}\binom{n-r}{r}\frac{(-1)^r}{n-r} = \color{red}{\frac{1}{n}}}\tag{4}$$ for any $n\equiv \pm1\pmod{6}$. As an alternative, we may use the generating function for Chebyshev polynomials of the second kind, by replacing $x$ with $x/2$, then $t$ with $xt$. $S_n$ then becomes the coefficient of $t^n$ in a simple analytic function.

Answer 2

Suppose we seek to prove that

$$\sum_{k=0}^{3n+2} \frac{(-1)^k}{6n+5-k} {6n+5-k\choose k} = \frac{1}{6n+5}.$$

This means we must show that

$$\sum_{k=0}^{3n+2} (-1)^k \frac{6n+5}{6n+5-k} {6n+5-k\choose k} = 1.$$

The LHS is

$$\sum_{k=0}^{3n+2} (-1)^k \left(1+\frac{k}{6n+5-k}\right) {6n+5-k\choose k}$$

This has two components, the first is

$$\sum_{k=0}^{3n+2} (-1)^k {6n+5-k\choose k}$$

and the second is

$$\sum_{k=0}^{3n+2} (-1)^k \frac{k}{6n+5-k} {6n+5-k\choose k} \\ = \sum_{k=1}^{3n+2} (-1)^k \frac{k}{6n+5-k} \frac{6n+5-k}{k} {6n+4-k\choose k-1} \\ = \sum_{k=1}^{3n+2} (-1)^k {6n+4-k\choose k-1} \\ = \sum_{k=0}^{3n+1} (-1)^{k+1} {6n+3-k\choose k}.$$

Now for the first sum we introduce

$${6n+5-k\choose k} = {6n+5-k\choose 6n+5-2k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{6n+6-2k}} (1+z)^{6n+5-k} \; dz.$$

This vanishes for $k\ge 3n+3$ as required. We get for the sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{6n+6}} (1+z)^{6n+5} \sum_{k\ge 0} (-1)^k \frac{z^{2k}}{(1+z)^k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{6n+6}} (1+z)^{6n+5} \frac{1}{1+z^2/(1+z)} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{6n+6}} (1+z)^{6n+6} \frac{1}{1+z+z^2} \; dz.$$

Using the substitution $z/(1+z)=w$ (which is a linear fractional transformation that maps circles to circles) so that $z=w/(1-w)$ and $dz=1/(1-w)^2\; dw$ we obtain

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{6n+6}} \frac{1}{1+w/(1-w)+w^2/(1-w)^2} \frac{1}{(1-w)^2} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{6n+6}} \frac{1}{(1-w)^2+w(1-w)+w^2} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{6n+6}} \frac{1}{1-w+w^2} \; dw.$$

In the substitution into the first integral we have used the fact that the image circle of $|z|=\epsilon$ can be deformed to obtain the circle $|w|=\gamma$.

Now we can solve this by inspection having a linear recurrence with constant coefficients whose solution is periodic but we may also use that $1-w+w^2 = (w-\rho)(w-1/\rho)$ with $\rho=-\exp(2\pi i/3)$ so that with partial fractions by residues we get

$$\frac{1}{1-w+w^2} = \frac{1}{2\rho-1}\frac{1}{w-\rho} + \frac{1}{2/\rho-1}\frac{1}{w-1/\rho} \\ = \frac{1}{2\rho^2-\rho}\frac{1}{w/\rho-1} + \frac{1}{2/\rho^2-1/\rho}\frac{1}{w\rho-1}.$$

We are extracting the coefficient on $[w^{6n+5}]$ and with the powers of $\rho$ being periodic with period six (period of $\exp(\pi i)$ is two and period of $\exp(2\pi i/3)$ is three, lcm is six) this is $[w^5]$ so we get

$$-\frac{1}{2\rho^2-\rho}\frac{1}{\rho^5} - \frac{1}{2/\rho^2-1/\rho}\frac{1}{(1/\rho)^5}.$$

Using periodicity we get

$$-\frac{1}{2\rho-1} - \frac{1}{2/\rho-1} = -\frac{2/\rho-1+2\rho-1}{(2\rho-1)(2/\rho-1)} = -\frac{2\rho^2-2\rho+2}{\rho(2\rho-1)(2/\rho-1)} =0,$$

because the numerator is zero here, and we get zero as the value of the first component being sought. Continuing with the second component we see the parameter three takes the place of five and there is an extra sign present and we find

$$-\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{6n+4}} (1+z)^{6n+4} \frac{1}{1+z+z^2} \; dz.$$

The substitution with $w$ now yields

$$-\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{6n+4}} \frac{1}{1-w+w^2} \; dw.$$

This is the coefficient on $[w^3]$ and we obtain

$$\frac{1}{2\rho^2-\rho}\frac{1}{\rho^3} + \frac{1}{2/\rho^2-1/\rho}\frac{1}{(1/\rho)^3}.$$

With $2\rho^5-\rho^4 = 2/\rho - 1/\rho^2 = (2\rho-1)/\rho^2 = (2\rho-1)/(\rho-1)$ the inverse is $1/2 - 1/(2\rho-1)/2$ and we find

$$1 - \frac{1}{2} \frac{1}{2\rho-1} -\frac{1}{2} \frac{1}{2/\rho-1} = 1$$

as we already evaluated this term. The two components add to $0+1$ and we have the claim.

Remark. We can avoid the somewhat tedious algebra by appealing to basic recurrences as pointed out earlier. The generating function yields the recurrence $a_{n+2} = a_{n+1} - a_{n}.$ The constant term is

$$\left.\frac{1}{1-w+w^2}\right|_{w=0} = 1$$

and the term on $[w]$ is

$$\left.-\frac{2w-1}{(1-w+w^2)^2}\right|_{w=0} = 1.$$

We then use the recurrence until it becomes periodic, getting

$$1,1,0,-1,-1,0,1,1,\ldots$$

and we have the required values with minimal effort. One of the guiding design parameters here was not to bring in algebra of instantiated complex numbers.