Olympiad problems

2025 VJIMC, 1

Tags: Sequences , Recurrence , characteristic polynomial , limits , college contests , VJIMC

Let $x_0=a, x_1= b, x_2 = c$ be given real numbers and let $x_{n+2} = \frac{x_n + x_{n-1}}{2}$ for all $n\geq 1$. Show that the sequence $(x_n)_{n\geq 0}$ converges and find its limit.

2013 AIME Problems, 9

Tags: modular arithmetic , AMC , Recurrence , combinatorics , AIME

A $7 \times 1$ board is completely covered by $m \times 1$ tiles without overlap; each tile may cover any number of consecutive squares, and each tile lies completely on the board. Each tile is either red, blue, or green. Let $N$ be the number of tilings of the $7 \times 1$ board in which all three colors are used at least once. For example, a $1 \times 1$ red tile followed by a $2 \times 1$ green tile, a $1 \times 1$ green tile, a $2 \times 1$ blue tile, and a $1 \times 1$ green tile is a valid tiling. Note that if the $2 \times 1$ blue tile is replaced by two $1 \times 1$ blue tiles, this results in a different tiling. Find the remainder when $N$ is divided by $1000$.

1978 Putnam, B3

Tags: Putnam , Polynomials , Recurrence , Sequences

The sequence $(Q_{n}(x))$ of polynomials is defined by $$Q_{1}(x)=1+x ,\; Q_{2}(x)=1+2x,$$ and for $m \geq 1 $ by $$Q_{2m+1}(x)= Q_{2m}(x) +(m+1)x Q_{2m-1}(x),$$ $$Q_{2m+2}(x)= Q_{2m+1}(x) +(m+1)x Q_{2m}(x).$$ Let $x_n$ be the largest real root of $Q_{n}(x).$ Prove that $(x_n )$ is an increasing sequence and that $\lim_{n\to \infty} x_n =0.$

1996 IMO Shortlist, 3

Tags: inequalities , algebra , Sequence , Recurrence , IMO Shortlist

Let $ a > 2$ be given, and starting $ a_0 \equal{} 1, a_1 \equal{} a$ define recursively: \[ a_{n\plus{}1} \equal{} \left(\frac{a^2_n}{a^2_{n\minus{}1}} \minus{} 2 \right) \cdot a_n.\] Show that for all integers $ k > 0,$ we have: $ \sum^k_{i \equal{} 0} \frac{1}{a_i} < \frac12 \cdot (2 \plus{} a \minus{} \sqrt{a^2\minus{}4}).$

2016 Puerto Rico Team Selection Test, 6

Tags: composition , function , algebra , Recurrence

$N$ denotes the set of all natural numbers. Define a function $T: N \to N$ such that $T (2k) = k$ and $T (2k + 1) = 2k + 2$. We write $T^2 (n) = T (T (n))$ and in general $T^k (n) = T^{k-1} (T (n))$ for all $k> 1$. (a) Prove that for every $n \in N$, there exists $k$ such that $T^k (n) = 1$. (b) For $k \in N$, $c_k$ denotes the number of elements in the set $\{n: T^k (n) = 1\}$. Prove that $c_{k + 2} = c_{k + 1} + c_k$, for $1 \le k$.

2025 NEPALTST, 1

Tags: algebra , Recurrence , Inequality

Let the sequence $\{a_n\}_{n \geq 1}$ be defined by \[ a_1 = 1, \quad a_{n+1} = a_n + \frac{1}{\sqrt[2024]{a_n}} \quad \text{for } n \geq 1, \, n \in \mathbb{N} \] Prove that \[ a_n^{2025} >n^{2024} \] for all positive integers $n \geq 2$. $\textbf{Proposed by Prajit Adhikari, Nepal.}$

2025 India National Olympiad, P1

Tags: INMO 2025 , Recurrence , Divisibility , Induct

Consider the sequence defined by $a_1 = 2$, $a_2 = 3$, and \[ a_{2k+1} = 2 + 2a_k, \quad a_{2k+2} = 2 + a_k + a_{k+1}, \] for all integers $k \geq 1$. Determine all positive integers $n$ such that \[ \frac{a_n}{n} \] is an integer. Proposed by Niranjan Balachandran, SS Krishnan, and Prithwijit De.

2013 Iran MO (2nd Round), 3

Tags: function , inequalities , algebra proposed , algebra , Recurrence

Let $\{a_n\}_{n=1}^{\infty}$ be a sequence of positive integers for which \[ a_{n+2} = \left[\frac{2a_n}{a_{n+1}}\right]+\left[\frac{2a_{n+1}}{a_n}\right]. \] Prove that there exists a positive integer $m$ such that $a_m=4$ and $a_{m+1} \in\{3,4\}$. [b]Note.[/b] $[x]$ is the greatest integer not exceeding $x$.