finite sum with combinatorics 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!
 A: 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.$$
