Prove that $\sum\limits_{k = 0}^{n}\binom{n-k}{k} (-4)^{-k} = 2^ {-n}(1+n)$ 
Prove that $$\sum\limits_{k = 0}^{n}\binom{n-k}{k} (-4)^{-k} = 2^ {-n}(1+n).$$

I tried to prove it in several ways, but it didn't work because of $\binom{n-k}{k}$. The analogy with the Fibonacci numbers did not help me.
 A: Rewrite as
$$\sum_{k\ge 0} \binom{n-k}{k}(-1)^k 2^{n-2k} = n + 1,$$
which you can prove combinatorially by counting blue-red colorings of $\{1,\dots,n\}$ such that blue is never followed by red.
For a proof that instead uses generating functions, see finite sum with combinatorics
A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{{\displaystyle #1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\on}[1]{\operatorname{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\sr}[2]{\,\,\,\stackrel{{#1}}{{#2}}\,\,\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
$\ds{\bbx{\sum_{k = 0}^{n}{n - k \choose k}\pars{-4}^{-k}\ =\
2^{-n}\pars{1 + n}}:\ {\LARGE ?}.}$

\begin{align}
& \color{#44f}{\sum_{k = 0}^{n}{n - k \choose k}\pars{-4}^{-k}} =
\left.\bracks{z^{n}}\sum_{\ell = 0}^{\infty}z^{\ell}
\sum_{k = 0}^{\ell}{\ell - k \choose k}\pars{-4}^{-k}
\,\right\vert_{\,\verts{z}\ <\ 1}
\\[5mm] = & \
\bracks{z^{n}}\sum_{k = 0}^{\infty}\pars{-4}^{-k}
\sum_{\ell = k}^{\infty}{\ell - k \choose k}z^{\ell} =
\bracks{z^{n}}\sum_{k = 0}^{\infty}\pars{-4}^{-k}
\sum_{\ell = 0}^{\infty}{\ell \choose k}z^{\ell + k}
\\[5mm] = & \
\bracks{z^{n}}\sum_{\ell = 0}^{\infty}z^{\ell}\sum_{k = 0}^{\infty}{\ell \choose k}\pars{-\,{z \over 4}}^{k} =
\bracks{z^{n}}\sum_{\ell = 0}^{\infty}z^{\ell}
\pars{1 - {z \over 4}}^{\ell}
\\[5mm] = & \ \bracks{z^{n}}{1 \over 1 - z\pars{1 - z/4}} =
\bracks{z^{n}}\pars{1 - {z \over 2}}^{-2} = {-2 \choose n}
\pars{-\,{1 \over 2}}^{n}
\\[5mm] = & \ \bracks{{2 + n - 1 \choose n}\pars{-1}^{n}}
\pars{-\,{1 \over 2}}^{n} = {n + 1 \choose n}2^{-n} =
\bbx{\color{#44f}{2^{-n}\pars{1 + n}}} \\ &
\end{align}
