"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?

• @JackD'Aurizio Here's the original problem, no mention of $\mod$. Taken from this page, the 1998 Round 1 link. Aug 30, 2021 at 16:07
• @MikeEarnest Thank you Mike, I wasn't able to find it in my quick search. It appears OP did make a typo in the binomial coefficient. Aug 30, 2021 at 16:10
• Apparently the answer is now $\frac{999}{2^{1996}}$, which seems a lot more reasonable. Aug 30, 2021 at 16:12
• In general $a_n = \frac{n+1}{2^n}$ is apparent from running the numbers. Aug 30, 2021 at 16:16

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.

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.$$

• Yes, this is my solution too, and I don't see why it shouldn't be intended. It's pretty straightforward, and I would guess linear reccurences are considered "curriculum" on the level of these constests. Aug 30, 2021 at 16:32
• Well obviously you can get around "characteristic polynomial" by guessing the pattern and proving it with induction. Aug 30, 2021 at 23:31
• I am not certain about is it okay to omit the order of partial sum (I mean, the upper bound of the sum), but it is still a nice solution! Thanks a lot. Sep 4, 2021 at 1:42
• @okw1124 That's a good point. I have now fixed this gap. In general, you usually don't have to worry about the limits of binomial coefficient summations; since $\binom{m}{j}$ is zero when $j<0$ or when $j>m$, $\sum_{k=0}^n \binom{n-k}{k}=\sum_{j=-\infty}^\infty \binom{n-k}{k}$. But it never hurts to be precise. Sep 4, 2021 at 2:03
• @MikeEarnest Thank you for nice supplement. Now I fully understood your solution, and it is brilliant! Sep 5, 2021 at 10:36