Olympiad problems

2015 Balkan MO Shortlist, N2

Sequence $(a_n)_{n\geq 0}$ is defined as $a_{0}=0, a_1=1, a_2=2, a_3=6$, and $ a_{n+4}=2a_{n+3}+a_{n+2}-2a_{n+1}-a_n, n\geq 0$. Prove that $n^2$ divides $a_n$ for infinite $n$. (Romania)

2009 Argentina National Olympiad, 6

Tags: sum of digits , digit , recurrence relation , number theory

A sequence $a_0,a_1,a_2,...,a_n,...$ is such that $a_0=1$ and, for each $n\ge 0$ , $a_{n+1}=m \cdot a_n$ , where $m$ is an integer between $2$ and $9$ inclusive. Also, every integer between $2$ and $9$ has even been used at least once to get $a_{n+1} $ from $a_n$ . Let $Sn$ the sum of the digits of $a_n$ , $n=0,1,2,...$ . Prove that $S_n \ge S_{n+1}$ for infinite values of $n$.

1992 IMO Longlists, 49

Tags: algebra , recurrence relation , inequality , sequence

Given real numbers $x_i \ (i = 1, 2, \cdots, 4k + 2)$ such that \[\sum_{i=1}^{4k +2} (-1)^{i+1} x_ix_{i+1} = 4m \qquad ( \ x_1=x_{4k+3} \ )\] prove that it is possible to choose numbers $x_{k_{1}}, \cdots, x_{k_{6}}$ such that \[\sum_{i=1}^{6} (-1)^{i} k_i k_{i+1} > m \qquad ( \ x_{k_{1}} = x_{k_{7}} \ )\]

2019 Saudi Arabia BMO TST, 2

Tags: sequence , algebra , recurrence relation

Let sequences of real numbers $(x_n)$ and $(y_n)$ satisfy $x_1 = y_1 = 1$ and $x_{n+1} =\frac{x_n + 2}{x_n + 1}$ and $y_{n+1} = \frac{y_n^2 + 2}{2y_n}$ for $n = 1,2, ...$ Prove that $y_{n+1} = x_{2^n}$ holds for $n =0, 1,2, ... $

2020 Kyiv Mathematical Festival, 1.1

Tags: recurrence relation , sequence , algebra

(a) Find the numbers $a_0,. . . , a_{100}$, such that $a_0 = 0, a_{100} = 1$ and for all $k = 1,. . . , 99$ : $$a_k = \frac12 a_{k- 1} + \frac12 a_{k+1 }$$ (b) Find the numbers $a_0,. . . , a_{100}$, such that $a_0 = 0, a_{100} = 1$ and for all $k = 1,. . . , 99$ : $$a_k = 1+\frac12 a_{k- 1} + \frac12 a_{k+1 }$$.

1987 IMO Shortlist, 14

Tags: symmetry , combinatorics of words , counting , digit , recurrence relation , combinatorics

How many words with $n$ digits can be formed from the alphabet $\{0, 1, 2, 3, 4\}$, if neighboring digits must differ by exactly one? [i]Proposed by Germany, FR.[/i]

2015 Saudi Arabia BMO TST, 1

Tags: sequence , recurrence relation

Prove that for any integer $n \ge 2$, there exists a unique finite sequence $x_0, x_1,..., x_n$ of real numbers which satisfies $x_0 = x_n = 0$ and $x_{i+1} - 8x_i^3 -4x_i + 3x_{i-1} + 1 = 0$ for all $i = 1,2,...,n - 1$. Prove moreover that $ |x_i| \le \frac12$ for all $i = 1,2,...,n - 1$. Nguyễn Duy Thái Sơn

1980 IMO Shortlist, 19

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

1976 IMO Longlists, 11

Tags: polynomial , recurrence relation , root , chebyshev polynomial , algebra

Let $P_{1}(x)=x^{2}-2$ and $P_{j}(x)=P_{1}(P_{j-1}(x))$ for j$=2,\ldots$ Prove that for any positive integer n the roots of the equation $P_{n}(x)=x$ are all real and distinct.

2009 Kyiv Mathematical Festival, 5

Tags: algebra , sequence , recurrence relation , recursion , inequalities

a) Suppose that a sequence of numbers $x_1,x_2,x_3,...$ satisfies the inequality $x_n-2x_{n+1}+x_{n+2} \le 0$ for any $n$ . Moreover $x_o=1,x_{20}=9,x_{200}=6$. What is the maximal value of $x_{2009}$ can be? b) Suppose that a sequence of numbers $x_1,x_2,x_3,...$ satisfies the inequality $2x_n-3x_{n+1}+x_{n+2} \le 0$ for any $n$. Moreover $x_o=1,x_1=2,x_3=1$. Can $x_{2009}$ be greater then $0,678$ ?

2018 MMATHS, 4

Tags: recurrence relation , algebra

A sequence of integers fsng is defined as follows: fix integers $a$, $b$, $c$, and $d$, then set $s_1 = a$, $s_2 = b$, and $$s_n = cs_{n-1} + ds_{n-2}$$ for all $n \ge 3$. Create a second sequence $\{t_n\}$ by defining each $t_n$ to be the remainder when $s_n$ is divided by $2018$ (so we always have $0 \le t_n \le 2017$). Let $N = (2018^2)!$. Prove that $t_N = t_{2N}$ regardless of the choices of $a$, $b$, $c$, and $d$.

2019 IMC, 4

Tags: recurrence relation , sequence , generating functions

Let $(n+3)a_{n+2}=(6n+9)a_{n+1}-na_n$ and $a_0=1$ and $a_1=2$ prove that all the terms of the sequence are integers

2015 CHMMC (Fall), 2

Tags: algebra , recurrence relation

Let $a_1 = 1$, $a_2 = 1$, and for $n \ge 2$, let $$a_{n+1} =\frac{1}{n} a_n + a_{n-1}.$$ What is $a_{12}$?

1967 IMO Shortlist, 1

Tags: combinatorics , recurrence relation , system of equations

In a sports meeting a total of $m$ medals were awarded over $n$ days. On the first day one medal and $\frac{1}{7}$ of the remaining medals were awarded. On the second day two medals and $\frac{1}{7}$ of the remaining medals were awarded, and so on. On the last day, the remaining $n$ medals were awarded. How many medals did the meeting last, and what was the total number of medals ?

1976 IMO Shortlist, 2

Tags: inequality , convexity , sequence , recurrence relation

Let $a_0, a_1, \ldots, a_n, a_{n+1}$ be a sequence of real numbers satisfying the following conditions: \[a_0 = a_{n+1 }= 0,\]\[ |a_{k-1} - 2a_k + a_{k+1}| \leq 1 \quad (k = 1, 2,\ldots , n).\] Prove that $|a_k| \leq \frac{k(n+1-k)}{2} \quad (k = 0, 1,\ldots ,n + 1).$

1996 VJIMC, Problem 2

Tags: recurrence relation , summation , binomial , algebra , sequence

Let $\{a_n\}^\infty_{n=0}$ be the sequence of integers such that $a_0=1$, $a_1=1$, $a_{n+2}=2a_{n+1}-2a_n$. Decide whether $$a_n=\sum_{k=0}^{\left\lfloor\frac n2\right\rfloor}\binom n{2k}(-1)^k.$$

1998 North Macedonia National Olympiad, 5

Tags: sequence , recurrence relation , inequalities , algebra

The sequence $(a_n)$ is defined by $a_1 =\sqrt2$ and $a_{n+1} =\sqrt{2-\sqrt{4-a_n^2}}$. Let $b_n =2^{n+1}a_n$. Prove that $b_n \le 7$ and $b_n < b_{n+1}$ for all $n$.

2018 Saudi Arabia GMO TST, 1

Tags: sequence , algebra , inequalities , recurrence relation , reciprocal

Let $\{x_n\}$ be a sequence defined by $x_1 = 2$ and $x_{n+1} = x_n^2 - x_n + 1$ for $n \ge 1$. Prove that $$1 -\frac{1}{2^{2^{n-1}}} < \frac{1}{x_1}+\frac{1}{x_2}+ ... +\frac{1}{x_n}< 1 -\frac{1}{2^{2^n}}$$ for all $n$

1975 Kurschak Competition, 3

Tags: recurrence relation , sequence , algebra , inequalities

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

1980 IMO, 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.\]

2008 VJIMC, Problem 2

Tags: fe , functional equation , recurrence relation , algebra , sequence

Find all functions $f:(0,\infty)\to(0,\infty)$ such that $$f(f(f(x)))+4f(f(x))+f(x)=6x.$$

1998 Belarusian National Olympiad, 5

Tags: sequence , recurrence relation , algebra

Is there an infinite sequence of positive real numbers $x_1,x_2,...,x_n$ satisfying for all $n\ge 1$ the relation $x_{n+2}= \sqrt{x_{n+1}}-\sqrt{x_n}$?

1990 IMO Longlists, 37

Tags: number theory , relatively prime , recurrence relation , counting , frobenius

An eccentric mathematician has a ladder with $ n$ rungs that he always ascends and descends in the following way: When he ascends, each step he takes covers $ a$ rungs of the ladder, and when he descends, each step he takes covers $ b$ rungs of the ladder, where $ a$ and $ b$ are fixed positive integers. By a sequence of ascending and descending steps he can climb from ground level to the top rung of the ladder and come back down to ground level again. Find, with proof, the minimum value of $ n,$ expressed in terms of $ a$ and $ b.$

1993 Abels Math Contest (Norwegian MO), 3

Tags: coprime , recurrence relation , number theory , fermat number

The Fermat-numbers are defined by $F_n = 2^{2^n}+1$ for $n\in N$. (a) Prove that $F_n = F_{n-1}F_{n-2}....F_1F_0 +2$ for $n > 0$. (b) Prove that any two different Fermat numbers are coprime

1993 IMO Shortlist, 1

Tags: limit , algebra , sequence , recurrence relation

Define a sequence $\langle f(n)\rangle^{\infty}_{n=1}$ of positive integers by $f(1) = 1$ and \[f(n) = \begin{cases} f(n-1) - n & \text{ if } f(n-1) > n;\\ f(n-1) + n & \text{ if } f(n-1) \leq n, \end{cases}\] for $n \geq 2.$ Let $S = \{n \in \mathbb{N} \;\mid\; f(n) = 1993\}.$ [b](i)[/b] Prove that $S$ is an infinite set. [b](ii)[/b] Find the least positive integer in $S.$ [b](iii)[/b] If all the elements of $S$ are written in ascending order as \[ n_1 < n_2 < n_3 < \ldots , \] show that \[ \lim_{i\rightarrow\infty} \frac{n_{i+1}}{n_i} = 3. \]