Olympiad problems

1988 Bundeswettbewerb Mathematik, 4

Starting with four given integers $a_1, b_1, c_1, d_1$ is defined recursively for all positive integers $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 there is a natural number $k$ such that all terms $a_k, b_k, c_k, d_k$ take the value zero.

1981 IMO Shortlist, 9

Tags: sequence , recurrence , algebra , recurrence relation

A sequence $(a_n)$ is defined by means of the recursion \[a_1 = 1, a_{n+1} = \frac{1 + 4a_n +\sqrt{1+ 24a_n}}{16}.\] Find an explicit formula for $a_n.$

1969 IMO Shortlist, 31

Tags: permutation , recurrence relation , counting , combinatorics

$(GDR 3)$ Find the number of permutations $a_1, \cdots, a_n$ of the set $\{1, 2, . . ., n\}$ such that $|a_i - a_{i+1}| \neq 1$ for all $i = 1, 2, . . ., n - 1.$ Find a recurrence formula and evaluate the number of such permutations for $n \le 6.$

1972 IMO, 3

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

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

1980 IMO, 2

Tags: recurrence relation , sequence , inequality , algebra

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

2022 Assara - South Russian Girl's MO, 6

Tags: algebra , sequence , recurrence relation

There are $2022$ numbers arranged in a circle $a_1, a_2, . . ,a_{2022}$. It turned out that for any three consecutive $a_i$, $a_{i+1}$, $a_{i+2}$ the equality $a_i =\sqrt2 a_{i+2} - \sqrt3 a_{i+1}$. Prove that $\sum^{2022}_{i=1} a_ia_{i+2} = 0$, if we know that $a_{2023} = a_1$, $a_{2024} = a_2$.

2005 Czech And Slovak Olympiad III A, 1

Tags: arithmetic sequence , algebra , sequence , maximum , recurrence relation

Consider all arithmetical sequences of real numbers $(x_i)^{\infty}=1$ and $(y_i)^{\infty} =1$ with the common first term, such that for some $k > 1, x_{k-1}y_{k-1} = 42, x_ky_k = 30$, and $x_{k+1}y_{k+1} = 16$. Find all such pairs of sequences with the maximum possible $k$.

1975 Kurschak Competition, 3

Tags: recurrence relation , sequence , inequalities , algebra

Let $$x_0 = 5\,\, ,\, \,\,x_{n+1} = x_n +\frac{1}{x_n}.$$ Prove that $45 < x_{1000} < 45.1$.

1969 IMO Longlists, 31

Tags: recurrence relation , permutation , counting , combinatorics

$(GDR 3)$ Find the number of permutations $a_1, \cdots, a_n$ of the set $\{1, 2, . . ., n\}$ such that $|a_i - a_{i+1}| \neq 1$ for all $i = 1, 2, . . ., n - 1.$ Find a recurrence formula and evaluate the number of such permutations for $n \le 6.$

2007 India IMO Training Camp, 1

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

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]

2005 VTRMC, Problem 3

Tags: counting , recurrence relation , combinatorics

We wish to tile a strip of $n$ $1$-inch by $1$-inch squares. We can use dominos which are made up of two tiles that cover two adjacent squares, or $1$-inch square tiles which cover one square. We may cover each square with one or two tiles and a tile can be above or below a domino on a square, but no part of a domino can be placed on any part of a different domino. We do not distinguish whether a domino is above or below a tile on a given square. Let $t(n)$ denote the number of ways the strip can be tiled according to the above rules. Thus for example, $t(1)=2$ and $t(2)=8$. Find a recurrence relation for $t(n)$, and use it to compute $t(6)$.

1992 French Mathematical Olympiad, Problem 4

Tags: sequence , recurrence relation , algebra

Given $u_0,u_1$ with $0<u_0,u_1<1$, define the sequence $(u_n)$ recurrently by the formula $$u_{n+2}=\frac12\left(\sqrt{u_{n+1}}+\sqrt{u_n}\right).$$(a) Prove that the sequence $u_n$ is convergent and find its limit. (b) Prove that, starting from some index $n_0$, the sequence $u_n$ is monotonous.

2000 All-Russian Olympiad Regional Round, 10.6

Tags: recurrence relation , number theory

Given a natural number $a_0$, we construct the sequence $\{a_n\}$ as follows $a_{n+1} = a^2_n-5$ if $a_n$ is odd, and $\frac{a_n}{2}$ if $a_n$ is even. Prove that for any odd $a_0 > 5$ in the sequence $\{a_n\}$ arbitrarily large numbers will occur.

2020 Dutch Mathematical Olympiad, 2

Tags: sequence , recurrence relation , algebra

For a given value $t$, we consider number sequences $a_1, a_2, a_3,...$ such that $a_{n+1} =\frac{a_n + t}{a_n + 1}$ for all $n \ge 1$. (a) Suppose that $t = 2$. Determine all starting values $a_1 > 0$ such that $\frac43 \le a_n \le \frac32$ holds for all $n \ge 2$. (b) Suppose that $t = -3$. Investigate whether $a_{2020} = a_1$ for all starting values $a_1$ different from $-1$ and $1$.

1996 IMO Shortlist, 3

Tags: recurrence relation , integer sequence , extremal combinatorics , perfect square , number theory

A finite sequence of integers $ a_0, a_1, \ldots, a_n$ is called quadratic if for each $ i$ in the set $ \{1,2 \ldots, n\}$ we have the equality $ |a_i \minus{} a_{i\minus{}1}| \equal{} i^2.$ a.) Prove that any two integers $ b$ and $ c,$ there exists a natural number $ n$ and a quadratic sequence with $ a_0 \equal{} b$ and $ a_n \equal{} c.$ b.) Find the smallest natural number $ n$ for which there exists a quadratic sequence with $ a_0 \equal{} 0$ and $ a_n \equal{} 1996.$

2013 Saudi Arabia BMO TST, 4

Tags: recurrence relation , function , algebra

Let $f : Z_{\ge 0} \to Z_{\ge 0}$ be a function which satisfies for all integer $n \ge 0$: (a) $f(2n + 1)^2 - f(2n)^2 = 6f(n) + 1$, (b) $f(2n) \ge f(n)$ where $Z_{\ge 0}$ is the set of nonnegative integers. Solve the equation $f(n) = 1000$

1972 IMO Shortlist, 8

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

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

2020 Australian Maths Olympiad, 4

Tags: recurrence relation , australia , sequence , recursive , algebra

Define the sequence $A_1, A_2, A_3, \dots$ by $A_1 = 1$ and for $n=1,2,3,\dots$ $$A_{n+1}=\frac{A_n+2}{A_n +1}.$$ Define the sequences $B_1, B_2, B_3,\dots$ by $B_1=1$ and for $n=1,2,3,\dots$ $$B_{n+1}=\frac{B_n^2 +2}{2B_n}.$$ Prove that $B_{n+1}=A_{2^n}$ for all non-negative integers $n$.

1979 IMO Shortlist, 9

Tags: combinatorics , linear recurrence , counting , recurrence relation

Let $A$ and $E$ be opposite vertices of an octagon. A frog starts at vertex $A.$ From any vertex except $E$ it jumps to one of the two adjacent vertices. When it reaches $E$ it stops. Let $a_n$ be the number of distinct paths of exactly $n$ jumps ending at $E$. Prove that: \[ a_{2n-1}=0, \quad a_{2n}={(2+\sqrt2)^{n-1} - (2-\sqrt2)^{n-1} \over\sqrt2}. \]

2024 IMC, 8

Tags: recurrence relation , sequence , limit

Define the sequence $x_1,x_2,\dots$ by the initial terms $x_1=2, x_2=4$, and the recurrence relation \[x_{n+2}=3x_{n+1}-2x_n+\frac{2^n}{x_n} \quad \text{for} \quad n \ge 1.\] Prove that $\lim_{n \to \infty} \frac{x_n}{2^n}$ exists and satisfies \[\frac{1+\sqrt{3}}{2} \le \lim_{n \to \infty} \frac{x_n}{2^n} \le \frac{3}{2}.\]