Simple but interesting problem about the binomial coefficient from Olympiad 
"Let's define $a_n=\sum\limits_{k=0}^{\lfloor n/2 \rfloor} {n-k \choose k}\left(-\frac{1}{4}\right)^k$.  Evaluate $a_{1997}$."

This problem is from the final round of an old South Korean Mathematical Olympiad (1997 KMO). 
I think this problem is very simple, but requires some combinatoric ideas, and also is very interesting.
But as a lot of time has passed by, I cannot find any solutions or guidelines about it. 
I tried to divide the explicit form of $(x+y)^{2k}$ with $x^k$, but it doesn't work well. 
Would you help me?

Snake oil:
\begin{align}
\sum_{n=0}^\infty a_n z^n &= \sum_{n=0}^\infty \left(\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k}\left(-\frac{1}{4}\right)^k \right) z^n \\
&= \sum_{k=0}^\infty \left(-\frac{1}{4}\right)^k\sum_{n=2k}^\infty \binom{n-k}{k} z^n \\
&= \sum_{k=0}^\infty \left(-\frac{1}{4}\right)^k z^{2k}\sum_{n=0}^\infty \binom{n+k}{k} z^n \\
&= \sum_{k=0}^\infty \left(-\frac{z^2}{4}\right)^k\frac{1}{(1-z)^{k+1}} \\
&= \frac{1}{1-z}\sum_{k=0}^\infty \left(-\frac{z^2}{4(1-z)}\right)^k \\
&= \frac{1}{1-z}\cdot\frac{1}{1+\frac{z^2}{4(1-z)}} \\
&= \frac{1}{(1-z/2)^2} \\
&= \sum_{n=0}^\infty \binom{n+1}{1} (z/2)^n \\
&= \sum_{n=0}^\infty \frac{n+1}{2^n} z^n
\end{align}
So $a_n= (n+1)/2^n$ for $n \ge 0$.
Note that this approach derives the formula without the need to guess the pattern.
