How to solve this binomial summation Problem where I was stuck at:
$$\sum_{k=0}^{n} (-4)^k\cdot \binom{n+k}{ 2k },$$ what I tried was to get observe that inside term is coefficients in expansion of $(1+2x)^{n+k}$ but evaluating it afterwards is not working for me.
 A: Probably there is a simpler way, but you can write this as
$$(-1)^n\left (2^{2n}-\sum _{k=1}^n(-1)^{k-1}2^{2n-2k}\binom{2n-k}{k}\right ),$$
this expression counts the number of binary words of size $2n$ avoiding the substring $01$. You can make sense of this expression using the inclusion-exclusion principle, where $\binom{2n-k}{k}$ is choosing the positions for $01$. Notice that it is impossible to have two substrings "01" together overlapping. 
This suggests that your sum is $(-1)^n(2n+1).$ This is because your words have to be of the form $1^k0^{2n-k}$ and there are $2n+1$ choices for $k$.

Edit:
To get the first expression, factor a $(-1)^n$ to get
$$(-1)^n\sum _{k=0}^n(-1)^{n-k}4^k\binom{n+k}{2k},$$
now transverse the sum from $n$ to $0$ so do the change of variable $k=n-k$ and use the symmetry of the binomial coefficient to get
$$(-1)^n\sum _{k=0}^n(-1)^{k}2^{2(n-k)}\binom{2n-k}{2(n-k)}=(-1)^n\sum _{k=0}^n(-1)^{k}2^{2(n-k)}\binom{2n-k}{k}.$$
Isolate the first term and you are in the form of the beginning of the answer.

Edit 2:
Consider the problem of counting the number of binary words of size $2n$ such that the subword $01$ is not allowed. On one part, if you take a binary string $x\in \{0,1\}^{2n}$ and you factor it as $0^{a_1}1^{b_1}\cdots 0^{a_n}1^{a_n}$ then because $01$ is not allowed, then the only option is the word to be either $\underbrace{00\cdots 00}_{2n\text{ times}}$ or $1^{b_1}0^{a_2}$ with $b_1+a_2=2n$ there are $2n+1$ of this cases.
On the other hand, consider the sets $A_i=\{x\in \{0,1\}^{2n}:x_ix_{i+1}=01\}$ so the patterns that we want to avoid is exactly in position $i$ of the string. You want then
$$\left |\{0,1\}^{2n}\setminus \bigcup _{i=1}^{2n-1}A_i\right |,$$
notice that $A_{i}\bigcap A_{i+1}=\emptyset$ and $|A_i|=2^{2n-2}$. In general $\left |\bigcap _{x\in X}A_x\right |=2^{2n-2|X|}$ if there is no $\{i,i+1\}\subseteq X$ and is $0$ otherwise. If you apply directly the principle of inclusion exclusion and you show that the number of ways to pick $k$ non consecutive indices on $2n$ positions is $\binom{2n-k}{k}$ you are done.
A: We seek to evaluate
$$\sum_{k=0}^n (-1)^k 2^{2k} {n+k\choose 2k}$$
which is
$$\sum_{k=0}^n (-1)^k 2^{2k} {n+k\choose n-k}
= [z^n] (1+z)^n \sum_{k=0}^n (-1)^k 2^{2k} (1+z)^k z^k.$$
Here the coefficient extractor enforces the upper limit of the sum and
we find
$$[z^n] (1+z)^n \frac{1}{1+4z(1+z)} =
[z^n] (1+z)^n \frac{1}{(1+2z)^2}.$$
This is
$$\frac{1}{4} \mathrm{Res}_{z=0} \frac{1}{z^{n+1}} (1+z)^n
\frac{1}{(z+1/2)^2}.$$
Residues sum to zero and the residue at infinity is zero by inspection.
Hence the residue at zero is minus the residue at $-1/2.$ We have
$$\frac{1}{4}
\left.\left( \frac{1}{z^{n+1}} (1+z)^n \right)'\right|_{z=-1/2}
= \frac{1}{4}
\left.\left( - \frac{n+1}{z^{n+2}} (1+z)^n
+ \frac{n}{z^{n+1}} (1+z)^{n-1}\right)\right|_{z=-1/2}
\\ = \frac{1}{4} \left( - (n+1) (-1)^n 2^{n+2} \frac{1}{2^n}
+ n (-1)^{n+1} 2^{n+1} \frac{1}{2^{n-1}} \right)
\\ = -(n+1) (-1)^n + n (-1)^{n+1}.$$
Taking into account the sign we get at last
$$\bbox[5px,border:2px solid #00A000]{
(-1)^n \times (2n+1).}$$
