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

  • 2
    $\begingroup$ @JackD'Aurizio Here's the original problem, no mention of $\mod$. Taken from this page, the 1998 Round 1 link. $\endgroup$ Aug 30, 2021 at 16:07
  • $\begingroup$ @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. $\endgroup$
    – Milten
    Aug 30, 2021 at 16:10
  • $\begingroup$ Apparently the answer is now $\frac{999}{2^{1996}}$, which seems a lot more reasonable. $\endgroup$
    – Milten
    Aug 30, 2021 at 16:12
  • $\begingroup$ In general $a_n = \frac{n+1}{2^n}$ is apparent from running the numbers. $\endgroup$
    – Milten
    Aug 30, 2021 at 16:16

2 Answers 2


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

  • $\begingroup$ 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. $\endgroup$
    – Milten
    Aug 30, 2021 at 16:32
  • 1
    $\begingroup$ Well obviously you can get around "characteristic polynomial" by guessing the pattern and proving it with induction. $\endgroup$ Aug 30, 2021 at 23:31
  • $\begingroup$ 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. $\endgroup$
    – okw1124
    Sep 4, 2021 at 1:42
  • 1
    $\begingroup$ @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. $\endgroup$ Sep 4, 2021 at 2:03
  • $\begingroup$ @MikeEarnest Thank you for nice supplement. Now I fully understood your solution, and it is brilliant! $\endgroup$
    – okw1124
    Sep 5, 2021 at 10:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.