uniolympiads Ελληνικά

IMC 2008, Day 2, Problem 3

Let nn be a positive integer. Prove that 2n−12^{n-1} divides

∑0≤k<n/2(n2k+1)5k.\sum_{0 \le k < n/2} \binom{n}{2k+1} 5^k.
Original from the official PDFLet n be a positive integer. Prove that 2 n−1 divides X n 5 k . 2k + 1 0≤k<n/2

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. As is known, the Fibonacci numbers FnF_n can be expressed as Fn=15((1+52)n−(1−52)n)F_n = \frac{1}{\sqrt5}\left(\left(\frac{1+\sqrt5}{2}\right)^n - \left(\frac{1-\sqrt5}{2}\right)^n\right). Expanding this expression, we obtain that Fn=12n−1((n1)+(n3)5+...+(nl)5l−12)F_n = \frac{1}{2^{n-1}}\left(\binom{n}{1} + \binom{n}{3}5 + ... + \binom{n}{l}5^{\frac{l-1}{2}}\right), where ll is the greatest odd number such that l≤nl \le n and s=l−12≤n2s = \frac{l-1}{2} \le \frac{n}{2}.

So, Fn=12n−1∑k=0s(n2k+1)5kF_n = \frac{1}{2^{n-1}}\sum\limits_{k=0}^{s}\binom{n}{2k+1}5^k, which implies that 2n−12^{n-1} divides ∑0≤k<n/2(n2k+1)5k\sum_{0\le k<n/2}\binom{n}{2k+1}5^k.

Transcribed from the official solutions, page 1. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?