Olympiad problems

1972 IMO Longlists, 15

Prove that $(2m)!(2n)!$ is a multiple of $m!n!(m+n)!$ for any non-negative integers $m$ and $n$.

1985 IMO Longlists, 78

Tags: function , recurrence relation , fixed point , calculus , limit

The sequence $f_1, f_2, \cdots, f_n, \cdots $ of functions is defined for $x > 0$ recursively by \[f_1(x)=x , \quad f_{n+1}(x) = f_n(x) \left(f_n(x) + \frac 1n \right)\] Prove that there exists one and only one positive number $a$ such that $0 < f_n(a) < f_{n+1}(a) < 1$ for all integers $n \geq 1.$

1997 Belarusian National Olympiad, 2

Tags: recurrence relation , algebra , number theory with sequences , number theory

A sequence $(a_n)_{-\infty}^{-\infty}$ of zeros and ones is given. It is known that $a_n = 0$ if and only if $a_{n-6} + a_{n-5} +...+ a_{n-1}$ is a multiple of $3$, and not all terms of the sequence are zero. Determine the maximum possible number of zeros among $a_0,a_1,...,a_{97}$.

1992 Yugoslav Team Selection Test, Problem 2

Tags: recurrence relation , sequence , algebra

Periodic sequences $(a_n),(b_n),(c_n)$ and $(d_n)$ satisfy the following conditions: $$a_{n+1}=a_n+b_n,\enspace\enspace b_{n+1}=b_n+c_n,$$ $$c_{n+1}=c_n+d_n,\enspace\enspace d_{n+1}=d_n+a_n,$$ for $n=1,2,\ldots$. Prove that $a_2=b_2=c_2=d_2=0$.

2024 CIIM, 1

Tags: integration , function , recurrence relation , calculus , sequence

Let $(a_n)_{n \geq 1}$ be a sequence of real numbers. We define a sequence of real functions $(f_n)_{n \geq 0}$ such that for all $x \in \mathbb{R}$, the following holds: \[ f_0(x) = 1 \quad \text{and} \quad f_n(x) = \int_{a_n}^{x} f_{n-1}(t) \, dt \quad \text{for } n \geq 1. \] Find all possible sequences $(a_n)_{n \geq 1}$ such that $f_n(0) = 0$ for all $n \geq 2$.\\ [b]Note:[/b] It is not necessarily true that $f_1(0) = 0$.

2014 Costa Rica - Final Round, 6

Tags: algebra , polynomial , recurrence relation , sequence

The sequences $a_n$, $b_n$ and $c_n$ are defined recursively in the following way: $a_0 = 1/6$, $b_0 = 1/2$, $c_0 = 1/3,$ $$a_{n+1}= \frac{(a_n + b_n)(a_n + c_n)}{(a_n - b_n)(a_n - c_n)},\,\, b_{n+1}= \frac{(b_n + a_n)(b_n + c_n)}{(b_n - a_n)(b_n - c_n)},\,\, c_{n+1}= \frac{(c_n + a_n)(c_n + b_n)}{(c_n - a_n)(c_n - b_n)}$$ For each natural number $N$, the following polynomials are defined: $A_n(x) =a_o+a_1 x+ ...+ a_{2N}x^{2N}$ $B_n(x) =b_o+a_1 x+ ...+ a_{2N}x^{2N}$ $C_n(x) =a_o+a_1 x+ ...+ a_{2N}x^{2N}$ Assume the sequences are well defined. Show that there is no real $c$ such that $A_N(c) = B_N(c) = C_N(c) = 0$.

2008 Federal Competition For Advanced Students, P1, 3

Tags: inequalities , sequence , recurrence relation , algebra

Let $p > 1$ be a natural number. Consider the set $F_p$ of all non-constant sequences of non-negative integers that satisfy the recursive relation $a_{n+1} = (p+1)a_n - pa_{n-1}$ for all $n > 0$. Show that there exists a sequence ($a_n$) in $F_p$ with the property that for every other sequence ($b_n$) in $F_p$, the inequality $a_n \le b_n$ holds for all $n$.

1983 IMO Shortlist, 7

Tags: number theory , sequence , recurrence relation , algebra

Let $a$ be a positive integer and let $\{a_n\}$ be defined by $a_0 = 0$ and \[a_{n+1 }= (a_n + 1)a + (a + 1)a_n + 2 \sqrt{a(a + 1)a_n(a_n + 1)} \qquad (n = 1, 2 ,\dots ).\] Show that for each positive integer $n$, $a_n$ is a positive integer.

1987 Bulgaria National Olympiad, Problem 4

Tags: algebra , recurrence relation , sequence

The sequence $(x_n)_{n\in\mathbb N}$ is defined by $x_1=x_2=1$, $x_{n+2}=14x_{n+1}-x_n-4$ for each $n\in\mathbb N$. Prove that all terms of this sequence are perfect squares.

1976 IMO Shortlist, 4

Tags: algebra , recurrence relation , power of 2 , sequence , floor function

A sequence $(u_{n})$ is defined by \[ u_{0}=2 \quad u_{1}=\frac{5}{2}, u_{n+1}=u_{n}(u_{n-1}^{2}-2)-u_{1} \quad \textnormal{for } n=1,\ldots \] Prove that for any positive integer $n$ we have \[ [u_{n}]=2^{\frac{(2^{n}-(-1)^{n})}{3}} \](where [x] denotes the smallest integer $\leq$ x)$.$

1986 Bulgaria National Olympiad, Problem 6

Tags: inequalities , recurrence relation , algebra , sequence

Let $0<k<1$ be a given real number and let $(a_n)_{n\ge1}$ be an infinite sequence of real numbers which satisfies $a_{n+1}\le\left(1+\frac kn\right)a_n-1$. Prove that there is an index $t$ such that $a_t<0$.

2024 Regional Olympiad of Mexico West, 5

Tags: number theory , recurrence relation

Consider a sequence of positive integers $a_1,a_2,a_3,...$ such that $a_1>1$ and $$a_{n+1}=\frac{a_n}{p}+p,$$ where $p$ is the greatest prime factor of $a_n$. Prove that for any choice of $a_1$, the sequence $a_1,a_2,a_3,...$ has an infinite terms that are equal between them.

1980 IMO Shortlist, 2

Tags: algebra , recurrence relation , sequence , inequality

Define the numbers $a_0, a_1, \ldots, a_n$ in the following way: \[ a_0 = \frac{1}{2}, \quad a_{k+1} = a_k + \frac{a^2_k}{n} \quad (n > 1, k = 0,1, \ldots, n-1). \] Prove that \[ 1 - \frac{1}{n} < a_n < 1.\]

1980 IMO, 2

Tags: number theory , sequence , recurrence relation

Find the greatest natural number $n$ such there exist natural numbers $x_{1}, x_{2}, \ldots, x_{n}$ and natural $a_{1}< a_{2}< \ldots < a_{n-1}$ satisfying the following equations for $i =1,2,\ldots,n-1$: \[x_{1}x_{2}\ldots x_{n}= 1980 \quad \text{and}\quad x_{i}+\frac{1980}{x_{i}}= a_{i}.\]

1972 IMO Shortlist, 8

Tags: binomial coefficient , factorial , number theory , recurrence relation

Prove that $(2m)!(2n)!$ is a multiple of $m!n!(m+n)!$ for any non-negative integers $m$ and $n$.

2024 Brazil Cono Sur TST, 4

Tags: inequalities , recurrence relation

An infinite sequence of positive real numbers $x_0,x_1,x_2,...$ is called $vasco$ if it satisfies the following properties: (a) $x_0=1,x_1=3$; and (b) $x_0+x_1+...+x_{n-1}\ge3x_{n}-x_{n+1}$, for every $n\ge1$. Find the greatest real number $M$ such that, for every $vasco$ sequence, the inequality $\frac{x_{n+1}}{x_{n}}>M$ is true for every $n\ge0$.

1977 IMO Shortlist, 11

Tags: algebra , recurrence relation , sequence , equation , floor function

Let $n$ be an integer greater than $1$. Define \[x_1 = n, y_1 = 1, x_{i+1} =\left[ \frac{x_i+y_i}{2}\right] , y_{i+1} = \left[ \frac{n}{x_{i+1}}\right], \qquad \text{for }i = 1, 2, \ldots\ ,\] where $[z]$ denotes the largest integer less than or equal to $z$. Prove that \[ \min \{x_1, x_2, \ldots, x_n \} =[ \sqrt n ]\]

2021 Regional Olympiad of Mexico West, 3

Tags: number theory , sequence , recurrence relation

The sequence of real numbers $a_1, a_2, a_3, ...$ is defined as follows: $a_1 = 2019$, $a_2 = 2020$, $a_3 = 2021$ and for all $n \ge 1$ $$a_{n+3} = 5a^6_{n+2} + 3a^3_{n+1} + a^2_n.$$ Show that this sequence does not contain numbers of the form $m^6$ where $m$ is a positive integer.

1986 Bundeswettbewerb Mathematik, 4

Tags: algebra , recurrence relation

The sequence $a_1, a_2, a_3,...$ is defined by $$a_1 = 1\,\,\,, \,\,\,a_{n+1} =\frac{1}{16}(1 + 4a_n +\sqrt{1 + 24a_n}) \,\,\,(n \in N^* ).$$ Determine and prove a formula with which for every natural number $n$ the term $a_n$ can be computed directly without having to determine preceding terms of the sequence.

1984 IMO Shortlist, 6

Tags: linear recurrence , algebra , sequence , recurrence relation

Let $c$ be a positive integer. The sequence $\{f_n\}$ is defined as follows: \[f_1 = 1, f_2 = c, f_{n+1} = 2f_n - f_{n-1} + 2 \quad (n \geq 2).\] Show that for each $k \in \mathbb N$ there exists $r \in \mathbb N$ such that $f_kf_{k+1}= f_r.$

1976 Polish MO Finals, 2

Tags: algebra , recurrence relation

Four sequences of real numbers $(a_n), (b_n), (c_n), (d_n)$ satisfy for all $n$, $$a_{n+1} = a_n +b_n, b_{n+1} = b_n +c_n,$$ $$c_{n+1} = c_n +d_n, d_{n+1} = d_n +a_n.$$ Prove that if $a_{k+m} = a_m, b_{k+m} = b_m, c_{k+m} = c_m, d_{k+m} = d_m$ for some $k\ge 1,n \ge 1$, then $a_2 = b_2 = c_2 = d_2 = 0$.

V Soros Olympiad 1998 - 99 (Russia), 11.9

Tags: recurrence , recurrence relation , sequence , algebra

The sequence of $a_n$ is determined by the relation $$a_{n+1}=\frac{k+a_n}{1-a_n}$$ where $k > 0$. It is known that $a_{13} = a_1$. What values can $k$ take?

1982 Austrian-Polish Competition, 4

Tags: number theory , sequence , recurrence relation , bounded , unbounded , digit , product of digits

Let $P(x)$ denote the product of all (decimal) digits of a natural number $x$. For any positive integer $x_1$, define the sequence $(x_n)$ recursively by $x_{n+1} = x_n + P(x_n)$. Prove or disprove that the sequence $(x_n)$ is necessarily bounded.

2007 Germany Team Selection Test, 1

Tags: floor function , algebra , sequence , recurrence relation , periodic sequence

A sequence of real numbers $ a_{0},\ a_{1},\ a_{2},\dots$ is defined by the formula \[ a_{i \plus{} 1} \equal{} \left\lfloor a_{i}\right\rfloor\cdot \left\langle a_{i}\right\rangle\qquad\text{for}\quad i\geq 0; \]here $a_0$ is an arbitrary real number, $\lfloor a_i\rfloor$ denotes the greatest integer not exceeding $a_i$, and $\left\langle a_i\right\rangle=a_i-\lfloor a_i\rfloor$. Prove that $a_i=a_{i+2}$ for $i$ sufficiently large. [i]Proposed by Harmel Nestra, Estionia[/i]

1997 Singapore Team Selection Test, 3

Tags: inequalities , sequence , algebra , recurrence relation

Suppose the numbers $a_0, a_1, a_2, ... , a_n$ satisfy the following conditions: $a_0 =\frac12$, $a_{k+1} = a_k +\frac{1}{n}a_k^2$ for $k = 0, 1, ... , n - 1$. Prove that $1 - \frac{1}{n}< a_n < 1$