I have two finite sum with combinatorics:$$f(n)=\sum_{k=0}^n (-1)^k 4^{n-k} \binom{2n-k+1}{k}$$ and $$g(n)=\sum_{k=0}^n (-1)^k 4^{n-k}\binom{2n-k}{k}$$
I tried several methods but have no clue how to derive that $f(n)=n+1$ and $g(n)=2n+1$. Can anybody help me?
Any hint is appreciated in advance!
On
For the second one, we start as follows:
$$\sum_{k=0}^n (-1)^k 4^{n-k} {2n-k\choose k} = \sum_{k=0}^n (-1)^k 4^{n-k} {2n-k\choose 2n-2k} \\ = \sum_{k=0}^n (-1)^k 4^{n-k} [z^{2n-2k}] (1+z)^{2n-k} \\ = [z^{2n}] (1+z)^{2n} \sum_{k=0}^n (-1)^k 4^{n-k} z^{2k} (1+z)^{-k}.$$
Now when $k\gt n$ we get zero contribution due to the coefficient extractor $[z^{2n}]$ and the factor $z^{2k}$, so this enforces the range of the sum and we may continue with
$$[z^{2n}] (1+z)^{2n} \sum_{k\ge 0} (-1)^k 4^{n-k} z^{2k} (1+z)^{-k} \\ = 4^n [z^{2n}] (1+z)^{2n} \frac{1}{1+z^2/(1+z)/4} \\ = 4^{n+1} [z^{2n}] (1+z)^{2n+1} \frac{1}{4+4z+z^2} = 4^{n+1} [z^{2n}] (1+z)^{2n+1} \frac{1}{(z+2)^2}.$$
This is
$$4^{n+1} \;\underset{z}{\mathrm{res}}\; \frac{1}{z^{2n+1}} (1+z)^{2n+1} \frac{1}{(z+2)^2}.$$
We introduce $z/(1+z)=w$ so that $z = w/(1-w)$ and $dz = 1/(1-w)^2 \; dw,$ to obtain
$$4^{n+1} \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{2n+1}} \frac{1}{(w/(1-w)+2)^2} \frac{1}{(1-w)^2} \\ = 4^{n+1} \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{2n+1}} \frac{1}{(2-w)^2} \\ = 4^{n+1} [w^{2n}] \frac{1}{(2-w)^2} = 4^{n} [w^{2n}] \frac{1}{(1-w/2)^2} = 4^n (2n+1) \frac{1}{2^{2n}} \\ = 2n+1.$$
Remark. This can also be done using the fact that residues sum to zero, which starting from the residue in $z$ we see that the residue at infinity is zero, so our sum is
$$- 4^{n+1} \mathrm{Res}_{z=-2} \frac{1}{z^{2n+1}} (1+z)^{2n+1} \frac{1}{(z+2)^2} \\ = - 4^{n+1} \left.\left(\frac{1}{z^{2n+1}} (1+z)^{2n+1}\right)'\right|_{z=-2} \\ = - 4^{n+1} \left.\left(-\frac{2n+1}{z^{2n+2}} (1+z)^{2n+1}+ \frac{(2n+1)}{z^{2n+1}} (1+z)^{2n}\right) \right|_{z=-2} \\ = (2n+1) \times 4^{n+1} \left(\frac{(-1)^{2n+1}}{(-2)^{2n+2}} - \frac{(-1)^{2n}}{(-2)^{2n+1}}\right) \\ = (2n+1) \times 2^{2n+2} \left(- \frac{1}{2^{2n+2}} + \frac{1}{2^{2n+1}}\right) = 2n+1.$$
For $g(n)$, see Problem 10F in Van Lint and Wilson's A Course in Combinatorics. One approach is to note that $$\sum_{n=0}^\infty (2n+1) x^{2n} = \frac{d}{dx}\left(\sum_{n=0}^\infty x^{2n+1}\right) = \frac{d}{dx}\left(\frac{x}{1-x^2}\right) = \frac{1+x^2}{(1-x^2)^2}$$ and then show that $\sum_{n=0}^\infty g(n) x^{2n}$ reduces to the same expression, as follows: \begin{align} \sum_{n=0}^\infty g(n) x^{2n} &= \sum_{n=0}^\infty \sum_{k=0}^n(−1)^k 4^{n−k}\binom{2n−k}{k} x^{2n}\\ &= \sum_{k=0}^\infty (−1)^k x^{2k} \sum_{n=k}^\infty \binom{2n−k}{k} 4^{n-k}x^{2n-2k}\\ &= \sum_{k=0}^\infty (−x^2)^k \sum_{n=k}^\infty \binom{2n−k}{2n-2k} (2x)^{2n-2k}\\ &= \sum_{k=0}^\infty (−x^2)^k \sum_{r=0}^\infty \binom{2r+k}{2r} (2x)^{2r}\\ &= \sum_{k=0}^\infty (−x^2)^k \sum_{r=0}^\infty \frac{1+(-1)^r}{2}\binom{r+k}{r} (2x)^r\\ &= \frac{1}{2}\sum_{k=0}^\infty (−x^2)^k \left(\sum_{r=0}^\infty \binom{r+k}{r} (2x)^r + \sum_{r=0}^\infty \binom{r+k}{r} (-2x)^r\right)\\ &= \frac{1}{2}\sum_{k=0}^\infty (−x^2)^k \left(\frac{1}{(1-2x)^{k+1}} + \frac{1}{(1+2x)^{k+1}}\right)\\ &= \frac{1}{2(1-2x)}\sum_{k=0}^\infty \left(\frac{-x^2}{1-2x}\right)^k + \frac{1}{2(1+2x)}\sum_{k=0}^\infty \left(\frac{-x^2}{1+2x}\right)^k\\ &= \frac{1}{2(1-2x)}\cdot\frac{1}{1-\frac{-x^2}{1-2x}} + \frac{1}{2(1+2x)}\cdot\frac{1}{1-\frac{-x^2}{1+2x}}\\ &= \frac{1}{2(1-2x+x^2)} + \frac{1}{2(1+2x+x^2)}\\ &= \frac{1+x^2}{(1-x^2)^2} \end{align}
An alternative combinatorial proof (coloring the integers 1 to $2n$ red or blue such that if $i$ is red then $i-1$ is not blue) uses the inclusion-exclusion principle.
For $f(n)$, one approach is to note that $$\sum_{n=0}^\infty (n+1) x^n = \frac{d}{dx}\left(\sum_{n=0}^\infty x^{n+1}\right) = \frac{d}{dx}\left(\frac{x}{1-x}\right) = \frac{1}{(1-x)^2},$$ so $$\sum_{n=0}^\infty (n+1) x^{2n} = \frac{1}{(1-x^2)^2},$$ and then show that $\sum_{n=0}^\infty f(n) x^{2n}$ reduces to the same expression, as follows: \begin{align} \sum_{n=0}^\infty f(n) x^{2n} &= \sum_{n=0}^\infty \sum_{k=0}^n (−1)^k 4^{n−k}\binom{2n−k+1}{k} x^{2n}\\ &= \sum_{k=0}^\infty (−1)^k x^{2k} \sum_{n=k}^\infty \binom{2n−k+1}{k} 4^{n-k}x^{2n-2k}\\ &= \sum_{k=0}^\infty (−x^2)^k \sum_{n=k}^\infty \binom{2n−k+1}{2n-2k+1} (2x)^{2n-2k}\\ &= \frac{1}{2x}\sum_{k=0}^\infty (−x^2)^k \sum_{r=0}^\infty \binom{2r+k+1}{2r+1} (2x)^{2r+1}\\ &= \frac{1}{2x}\sum_{k=0}^\infty (−x^2)^k \sum_{r=0}^\infty \frac{1-(-1)^r}{2}\binom{r+k}{r} (2x)^r\\ &= \frac{1}{4x}\sum_{k=0}^\infty (−x^2)^k \left(\sum_{r=0}^\infty \binom{r+k}{r} (2x)^r - \sum_{r=0}^\infty \binom{r+k}{r} (-2x)^r\right)\\ &= \frac{1}{4x}\sum_{k=0}^\infty (−x^2)^k \left(\frac{1}{(1-2x)^{k+1}} - \frac{1}{(1+2x)^{k+1}}\right)\\ &= \frac{1}{4x(1-2x)}\sum_{k=0}^\infty \left(\frac{-x^2}{1-2x}\right)^k - \frac{1}{4x(1+2x)}\sum_{k=0}^\infty \left(\frac{-x^2}{1+2x}\right)^k\\ &= \frac{1}{4x(1-2x)}\cdot\frac{1}{1-\frac{-x^2}{1-2x}} - \frac{1}{4x(1+2x)}\cdot\frac{1}{1-\frac{-x^2}{1+2x}}\\ &= \frac{1}{4x(1-2x+x^2)} - \frac{1}{4x(1+2x+x^2)}\\ &= \frac{1}{(1-x^2)^2} \end{align}