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?
 A: 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.
A: This is a solution which assumes a background in solving homogenous linear recurrences. Perhaps there is a more elementary or clever solution that was intended, but I cannot imagine it.
\begin{aligned}
a_n
&=\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k}(-1/4)^k
\\&=\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k-1}{k}(-1/4)^{k}+\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k-1}{k-1}(-1/4)^k
\\&=\sum_{k=0}^{\lfloor n/2\rfloor}\binom{(n-1)-k}{k}(-1/4)^k+(-1/4)\sum_{k=0}^{\lfloor n/2\rfloor}\binom{(n-2)-(k-1)}{k-1}(-1/4)^{k-1}
\\&=a_{n-1}-(1/4)a_{n-2}
\end{aligned}
You may complain about the last step, since the definition $a_{n-1}$ requires the sum to go to $\lfloor (n-1)/2\rfloor$, and $a_{n-2}$ requires the sum to go to $\lfloor (n-2)/2\rfloor$, but both upper limits are $\lfloor n/2\rfloor$. This means the first summation has either zero or one extra terms, depending on the parity of $n$, while the second has one extra term. You can check that both of these extra terms are zero, so this is no problem.
This is a homogenous linear recurrence with characteristic polynomial $x^2-x+1/4=(x-1/2)^2$. Therefore, the general solution is $$a_n=(Cn+D)(1/2)^n.$$ Since $a_0=a_1=1$, can solve for $C$ and $D$ to find $D=1$ and $C=1$. Therefore,
$$
a_n=(n+1)/2^n.
$$
