Competition problem — Algebra — Maths Olympiad Prep

Library / /53 of 196

Algebra Difficulty 4.7 AIME Prove it Soviet Union

Problem:

Given integers $a_0$ , $a_1$ , ..., $a_{100}$ , satisfying $a_1 > a_0$ , $a_1 > 0$ , and $a_{r + 2} = 3 a_{r + 1} - 2 a_r$ for $r = 0$ , $1$ , ..., $98$ . Prove $a_{100} > 2^{99}$ .

Solution

Solution:

An easy induction gives $a_r = (2^{r} - 1)a_1 - (2^{r} - 2)a_0$ for $r = 2$ , $3$ , ..., $100$ . Hence, in particular, $a_{100} = (2^{100} - 2)(a_1 - a_0) + a_1$ . But $a_1$ and $(a_1 - a_0)$ are both at least $1$ . Hence result.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.