Maths Olympiad Prep

Library / HMMT February /401 of 1302

HMMT February

Algebra Difficulty 5.1 AIME, harder Find the answer

Define the sequence {xi}i≥0\{x_{i}\}_{i \geq 0} by x0=2009x_{0}=2009 and xn=−2009n∑k=0n−1xkx_{n}=-\frac{2009}{n} \sum_{k=0}^{n-1} x_{k} for all n≥1n \geq 1. Compute the value of ∑n=020092nxn\sum_{n=0}^{2009} 2^{n} x_{n}

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

We have −nxn2009=xn−1+xn−2+…+x0=xn−1+(n−1)xn−12009-\frac{n x_{n}}{2009}=x_{n-1}+x_{n-2}+\ldots+x_{0}=x_{n-1}+\frac{(n-1) x_{n-1}}{2009}, which yields the recursion xn=n−2010nxn−1x_{n}=\frac{n-2010}{n} x_{n-1}. Unwinding this recursion, we find xn=(−1)n⋅2009x_{n}=(-1)^{n} \cdot 2009. (2008n)\binom{2008}{n}. Thus ∑k=020092nxn=∑k=02009(−2)n⋅2009⋅(2008n)=2009∑k=02008(−2)n(2008n)=2009(−2+1)2008\sum_{k=0}^{2009} 2^{n} x_{n} =\sum_{k=0}^{2009}(-2)^{n} \cdot 2009 \cdot\binom{2008}{n} =2009 \sum_{k=0}^{2008}(-2)^{n}\binom{2008}{n} =2009(-2+1)^{2008} as desired.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.