Olympiad problems

2018 Peru IMO TST, 10

For each positive integer $m> 1$, let $P (m)$ be the product of all prime numbers that divide $m$. Define the sequence $a_1, a_2, a_3,...$ as followed: $a_1> 1$ is an arbitrary positive integer, $a_{n + 1} = a_n + P (a_n)$ for each positive integer $n$. Prove that there exist positive integers $j$ and $k$ such that $a_j$ is the product of the first $k$ prime numbers.

2011 Dutch IMO TST, 4

Tags: number theory , recurrence relation , sequence , prime number

Prove that there exists no innite sequence of prime numbers $p_0, p_1, p_2,...$ such that for all positive integers $k$: $p_k = 2p_{k-1} + 1$ or $p_k = 2p_{k-1} - 1$.

1994 IMO Shortlist, 1

Tags: algebra , sequence , recurrence relation

Let $ a_{0} \equal{} 1994$ and $ a_{n \plus{} 1} \equal{} \frac {a_{n}^{2}}{a_{n} \plus{} 1}$ for each nonnegative integer $ n$. Prove that $ 1994 \minus{} n$ is the greatest integer less than or equal to $ a_{n}$, $ 0 \leq n \leq 998$

1953 Moscow Mathematical Olympiad, 257

Tags: inequalities , algebra , recurrence relation , sequence

Let $x_0 = 10^9$, $x_n = \frac{x^2_{n-1}+2}{2x_{n-1}}$ for $n > 0$. Prove that $0 < x_{36} - \sqrt2 < 10^{-9}$.

1980 Austrian-Polish Competition, 7

Tags: recurrence relation , number theory , sequence

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}.\]

2008 Postal Coaching, 1

Tags: algebra , recurrence relation , sequence , integer

Define a sequence $<x_n>$ by $x_0 = 0$ and $$\large x_n = \left\{ \begin{array}{ll} x_{n-1} + \frac{3^r-1}{2} & if \,\,n = 3^{r-1}(3k + 1)\\ & \\ x_{n-1} - \frac{3^r+1}{2} & if \,\, n = 3^{r-1}(3k + 2)\\ \end{array} \right. $$ where $k, r$ are integers. Prove that every integer occurs exactly once in the sequence.

1992 IMO Longlists, 55

Tags: induction , recurrence relation , algebra , sequence

For any positive integer $ x$ define $ g(x)$ as greatest odd divisor of $ x,$ and \[ f(x) \equal{} \begin{cases} \frac {x}{2} \plus{} \frac {x}{g(x)} & \text{if \ $x$ is even}, \\ 2^{\frac {x \plus{} 1}{2}} & \text{if \ $x$ is odd}. \end{cases} \] Construct the sequence $ x_1 \equal{} 1, x_{n \plus{} 1} \equal{} f(x_n).$ Show that the number 1992 appears in this sequence, determine the least $ n$ such that $ x_n \equal{} 1992,$ and determine whether $ n$ is unique.

1989 IMO Shortlist, 16

Tags: algebra , recurrence relation , sequence , inequality

The set $ \{a_0, a_1, \ldots, a_n\}$ of real numbers satisfies the following conditions: [b](i)[/b] $ a_0 \equal{} a_n \equal{} 0,$ [b](ii)[/b] for $ 1 \leq k \leq n \minus{} 1,$ \[ a_k \equal{} c \plus{} \sum^{n\minus{}1}_{i\equal{}k} a_{i\minus{}k} \cdot \left(a_i \plus{} a_{i\plus{}1} \right)\] Prove that $ c \leq \frac{1}{4n}.$

KoMaL A Problems 2018/2019, A. 738

Tags: algebra , number theory , recurrence relation

Consider the following sequence: $a_1 = 1$, $a_2 = 2$, $a_3 = 3$, and \[a_{n+3} = \frac{a_{n+1}^2 + a_{n+2}^2 - 2}{a_n}\] for all integers $n \ge 1$. Prove that every term of the sequence is a positive integer.

2021 Chile National Olympiad, 1

Tags: number theory , last digit , recurrence relation

Consider the sequence of numbers defined by $a_1 = 7$, $a_2 = 7^7$ , $ ...$ , $a_n = 7^{a_{n-1}}$ for $n \ge 2$. Determine the last digit of the decimal representation of $a_{2021}$.

1979 Dutch Mathematical Olympiad, 3

Tags: number theory , recurrence relation , sequence , last digit

Define $a_1 = 1979$ and $a_{n+1} = 9^{a_n}$ for $n = 1,2,3,...$. Determine the last two digits of $a_{1979}$.

1979 Chisinau City MO, 170

Tags: inequalities , algebra , recurrence relation

The numbers $a_1,a_2,...,a_n$ ( $n\ge 3$) satisfy the relations $$a_1=a_n = 0, a_{k-1}+ a_{k+1}\le 2a_k \,\,\, (k = 2, 3,..., n-1)$$ Prove that the numbers $a_1,a_2,...,a_n$ are non-negative.

2001 All-Russian Olympiad Regional Round, 11.5

Tags: algebra , sequence , periodic , trigonometry , recurrence relation

Given a sequence $\{x_k\}$ such that $x_1 = 1$, $x_{n+1} = n \sin x_n+ 1$. Prove that the sequence is non-periodic.

1973 Dutch Mathematical Olympiad, 4

Tags: limit , algebra , recurrence relation , sequence

We have an infinite sequence of real numbers $x_0,x_1, x_2, ... $ such that $x_{n+1} = \sqrt{x_n -\frac14}$ holds for all natural $n$ and moreover $x_0 \in \frac12$. (a) Prove that for every natural $n$ holds: $x_n > \frac12$ (b) Prove that $\lim_{n \to \infty} x_n$ exists. Calculate this limit.

2022 China Northern MO, 3

Tags: inequalities , algebra , recurrence relation

Let $\{a_n\}$ be a sequence of positive terms such that $a_{n+1}=a_n+ \frac{n^2}{a_n}$ . Let $b_n =a_n-n$ . (1) Are there infinitely many $n$ such that $b_n \ge 0$ ? (2) Prove that there is a positive number $M$ such that $\sum^{\infty}_{n=3} \frac{b_n}{n+1}<M$.

2014 Belarus Team Selection Test, 2

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

Find all sequences $(a_n)$ of positive integers satisfying the equality $a_n=a_{a_{n-1}}+a_{a_{n+1}}$ a) for all $n\ge 2$ b) for all $n \ge 3$ (I. Gorodnin)

2012 Indonesia TST, 1

Tags: algebra , binary representation , sequence , recurrence relation , induction

The sequence $a_i$ is defined as $a_1 = 2, a_2 = 3$, and $a_{n+1} = 2a_{n-1}$ or $a_{n+1} = 3a_n - 2a_{n-1}$ for all integers $n \ge 2$. Prove that no term in $a_i$ is in the range $[1612, 2012]$.

2010 Bundeswettbewerb Mathematik, 2

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

The sequence of numbers $a_1, a_2, a_3, ...$ is defined recursively by $a_1 = 1, a_{n + 1} = \lfloor \sqrt{a_1+a_2+...+a_n} \rfloor $ for $n \ge 1$. Find all numbers that appear more than twice at this sequence.

2012 Switzerland - Final Round, 4

Tags: number theory , prime , recurrence relation

Show that there is no infinite sequence of primes $p_1, p_2, p_3, . . .$ there any for each $ k$: $p_{k+1} = 2p_k - 1$ or $p_{k+1} = 2p_k + 1$ is fulfilled. Note that not the same formula for every $k$.

2014 Regional Competition For Advanced Students, 3

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

The sequence $(a_n)$ is defined with the recursion $a_{n + 1} = 5a^6_n + 3a^3_{n-1} + a^2_{n-2}$ for $n\ge 2$ and the set of initial values $\{a_0, a_1, a_2\} = \{2013, 2014, 2015\}$. (That is, the initial values are these three numbers in any order.) Show that the sequence contains no sixth power of a natural number.

2011 Indonesia TST, 4

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

Let $a, b$, and $c$ be positive integers such that $gcd(a, b) = 1$. Sequence $\{u_k\}$, is given such that $u_0 = 0$, $u_1 = 1$, and u$_{k+2} = au_{k+1} + bu_k$ for all $k \ge 0$. Let $m$ be the least positive integer such that $c | u_m$ and $n$ be an arbitrary positive integer such that $c | u_n$. Show that $m | n$. [hide=PS.] There was a typo in the last line, as it didn't define what n does. Wording comes from [b]tst-2011-1.pdf[/b] from [url=https://sites.google.com/site/imoidn/idntst/2011tst]here[/url]. Correction was made according to #2[/hide]

1995 Tuymaada Olympiad, 2

Tags: algebra , limit , limit of sequence , recurrence relation , maximum

Let $x_1=a, x_2=a^{x_1}, ..., x_n=a^{x_{n-1}}$ where $a>1$. What is the maximum value of $a$ for which lim exists $\lim_{n\to \infty} x_n$ and what is this limit?

2018 Peru IMO TST, 5

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

Let $d$ be a positive integer. The seqeunce $a_1, a_2, a_3,...$ of positive integers is defined by $a_1 = 1$ and $a_{n + 1} = n\left \lfloor \frac{a_n}{n} \right \rfloor+ d$ for $n = 1,2,3, ...$ . Prove that there exists a positive integer $N$ so that the terms $a_N,a_{N + 1}, a_{N + 2},...$ form an arithmetic progression. Note: If $x$ is a real number, $\left \lfloor x \right \rfloor $ denotes the largest integer that is less than or equal to $x$.

2021 Francophone Mathematical Olympiad, 1

Tags: number theory , sequence , divide , recurrence relation

Let $a_1,a_2,a_3,\ldots$ and $b_1,b_2,b_3,\ldots$ be positive integers such that $a_{n+2} = a_n + a_{n+1}$ and $b_{n+2} = b_n + b_{n+1}$ for all $n \ge 1$. Assume that $a_n$ divides $b_n$ for infinitely many values of $n$. Prove that there exists an integer $c$ such that $b_n = c a_n$ for all $n \ge 1$.

2017 Korea USCM, 3

Tags: real analysis , limit , recurrence relation

Sequence $\{a_n\}$ defined by recurrence relation $a_{n+1} = 1+\frac{n^2}{a_n}$. Given $a_1>1$, find the value of $\lim\limits_{n\to\infty} \frac{a_n}{n}$ with proof.