$ \sum_{k=0}^{n}\mathrm{C}_{2k}^{n+k} {(-4)}^{k} $

Question

Let $ S_{n}=\sum_{k=0}^{n}\mathrm{C}_{2k}^{n+k} {(-4)}^{k} $ then prove that $ S_{n+1}+2S_{n}+S_{n-1} = 0 $ (where n is a natural number greater than 2 and $ \mathrm{C}_{k}^{n} = \binom{n}{k} $) so far I have tried this
\begin{aligned} = & \sum_{k=0}^{n-1}(-4)^k\left\{{ }^{n+k+1} c_{2 k}+2^{n+k} c_{2 k}+{ }^{n+k-1} c_{2 k}\right\} \\ & +(-4)^{n+1}+(-4)^n \cdot{ }^{2 n+1} c_{2 n}+ \\ & 2 \cdot(-4)^n \\ = & \sum_{k=0}^{n-1}(-4)^k\left\{{ }^{n+k+1} c_{2 k}+2^{n+k} c_{2 k}+{ }^{n+k-1} c_{2 k}\right\} \\ + & (-4)^n[-4+(2 n+1)+2] \\ = & \sum_{k=0}^{n-1}(-4)^k\left\{{ }^{n+k+1} c_{2 k}+2^{n+k} c_{2 k}+{ }^{n+k-1} c_{2 k}\right\} \\ & +(-4)^n(2 n-1) \end{aligned} but after this I am unable to solve .

Answer 1

With

$$S_n = \sum_{k=0}^n {n+k\choose 2k} (-4)^k$$

we have

$$S_n = \sum_{k=0}^n {n+k\choose n-k} (-4)^k \\ = [z^n] (1+z)^n \sum_{k=0}^n z^k (1+z)^k (-4)^k.$$

Here we may extend to infinity because of the extractor in front:

$$[z^n] (1+z)^n \sum_{k\ge 0} z^k (1+z)^k (-4)^k \\ = [z^n] (1+z)^n \frac{1}{1+4z(1+z)} = [z^n] (1+z)^n \frac{1}{(1+2z)^2} \\ = \sum_{q=0}^n {n\choose q} (q+1) (-1)^q 2^q = (-1)^n + \sum_{q=1}^n {n\choose q} q (-1)^q 2^q \\ = (-1)^n - n \times 2 \times \sum_{q=1}^n {n-1\choose q-1} (-1)^{q-1} 2^{q-1} \\ = (-1)^n + 2 n (-1)^n = (-1)^n (1+2n).$$

We then have

$$S_{n+1} + 2 S_n + S_{n-1} \\ = (-1)^{n+1} (2n+3) - (-1)^{n+1} 2 (2n+1) + (-1)^{n+1} (2n-1) = 0$$

as claimed.