Olympiad problems

1985 Tournament Of Towns, (102) 6

The numerical sequence $x_1 , x_2 ,.. $ satisfies $x_1 = \frac12$ and $x_{k+1} =x^2_k+x_k$ for all natural integers $k$ . Find the integer part of the sum $\frac{1}{x_1+1}+\frac{1}{x_2+1}+...+\frac{1}{x_{100}+1}$ {A. Andjans, Riga)

1990 Czech and Slovak Olympiad III A, 1

Tags: algebra , recurrence relation , periodic , sequence

Let $(a_n)_{n\ge1}$ be a sequence given by \begin{align*} a_1 &= 1, \\ a_{2^k+j} &= -a_j\text{ for any } k\ge0,1\le j\le 2^k. \end{align*} Show that the sequence is not periodic.

1998 Moldova Team Selection Test, 10

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.

1981 Austrian-Polish Competition, 6

Tags: recurrence relation , sequence , unbounded , bounded , algebra

The sequences $(x_n), (y_n), (z_n)$ are given by $x_{n+1}=y_n +\frac{1}{x_n}$,$ y_{n+1}=z_n +\frac{1}{y_n}$,$z_{n+1}=x_n +\frac{1}{z_n} $ for $n \ge 0$ where $x_0,y_0, z_0$ are given positive numbers. Prove that these sequences are unbounded.

1990 Bundeswettbewerb Mathematik, 2

Tags: sequence , perfect square , recurrence relation , algebra

The sequence $a_0,a_1,a_2,...$ is defined by $a_0 = 0, a_1 = a_2 = 1$ and $a_{n+2} +a_{n-1} = 2(a_{n+1} +a_n)$ for all $n \in N$. Show that all $a_n$ are perfect squares .

2019 Pan-African, 1

Tags: linear recurrence , recurrence relation , algebra , induction

Let $(a_n)_{n=0}^{\infty}$ be a sequence of real numbers defined as follows: [list] [*] $a_0 = 3$, $a_1 = 2$, and $a_2 = 12$; and [*] $2a_{n + 3} - a_{n + 2} - 8a_{n + 1} + 4a_n = 0$ for $n \geq 0$. [/list] Show that $a_n$ is always a strictly positive integer.

2018 Estonia Team Selection Test, 10

Tags: algebra , sequence , recurrence relation , inequalities

A sequence of positive real numbers $a_1, a_2, a_3, ... $ satisfies $a_n = a_{n-1} + a_{n-2}$ for all $n \ge 3$. A sequence $b_1, b_2, b_3, ...$ is defined by equations $b_1 = a_1$ , $b_n = a_n + (b_1 + b_3 + ...+ b_{n-1})$ for even $n > 1$ , $b_n = a_n + (b_2 + b_4 + ... +b_{n-1})$ for odd $n > 1$. Prove that if $n\ge 3$, then $\frac13 < \frac{b_n}{n \cdot a_n} < 1$

2007 India IMO Training Camp, 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]

1998 Portugal MO, 6

Tags: inequalities , algebra , sequence , recurrence relation

Let $a_0$ be a positive real number and consider the general term sequence $a_n$ defined by $$a_n =a_{n-1} + \frac{1}{a_{n-1}} \,\,\, n=1,2,3,...$$ Prove that $a_{1998} > 63$.

1995 Tuymaada Olympiad, 2

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

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?

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.

2007 IMO Shortlist, 5

Tags: inequalities , sequence , bounded , recurrence relation , bodan last post

Let $ c > 2,$ and let $ a(1), a(2), \ldots$ be a sequence of nonnegative real numbers such that \[ a(m \plus{} n) \leq 2 \cdot a(m) \plus{} 2 \cdot a(n) \text{ for all } m,n \geq 1, \] and $ a\left(2^k \right) \leq \frac {1}{(k \plus{} 1)^c} \text{ for all } k \geq 0.$ Prove that the sequence $ a(n)$ is bounded. [i]Author: Vjekoslav Kovač, Croatia[/i]

1984 Bundeswettbewerb Mathematik, 3

Tags: algebra , recurrence relation , sequence

The sequences $a_1, a_2, a_3,...$ and $b_1, b_2, b_3,... $suffices for all positive integers $n$ of the following recursion: $a_{n+1} = a_n - b_n$ and $b_{n+1} = 2b_n$, if $a_n \ge b_n$, $a_{n+1} = 2a_n$ and $b_{n+1} = b_n - a_n$, if $a_n < b_n$. For which pairs $(a_1, b_1)$ of positive real initial terms is there an index $k$ with $a_k = 0$?

2009 Postal Coaching, 1

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

Let $a_1, a_2, a_3, . . . , a_n, . . . $ be an infinite sequence of natural numbers in which $a_1$ is not divisible by $5$. Suppose $a_{n+1} = a_n + b_n$ where bn is the last digit of $a_n$, for every $n$. Prove that the sequence $\{a_n\}$ contains infinitely many powers of 2.

2015 Bulgaria National Olympiad, 3

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

The sequence $a_1, a_2,...$ is defined by the equalities $a_1 = 2, a_2 = 12$ and $a_{n+1} = 6a_n-a_{n-1}$ for every positive integer $n \ge 2$. Prove that no member of this sequence is equal to a perfect power (greater than one) of a positive integer.

1996 IMO Shortlist, 9

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

Let the sequence $ a(n), n \equal{} 1,2,3, \ldots$ be generated as follows with $ a(1) \equal{} 0,$ and for $ n > 1:$ \[ a(n) \equal{} a\left( \left \lfloor \frac{n}{2} \right \rfloor \right) \plus{} (\minus{}1)^{\frac{n(n\plus{}1)}{2}}.\] 1.) Determine the maximum and minimum value of $ a(n)$ over $ n \leq 1996$ and find all $ n \leq 1996$ for which these extreme values are attained. 2.) How many terms $ a(n), n \leq 1996,$ are equal to 0?

2020 China Second Round Olympiad, 3

Tags: number theory , recurrence relation , linear recurrence

Let $a_1=1,$ $a_2=2,$ $a_n=2a_{n-1}+a_{n-2},$ $n=3,4,\cdots.$ Prove that for any integer $n\geq5,$ $a_n$ has at least one prime factor $p,$ such that $p\equiv 1\pmod{4}.$

1992 IMO Shortlist, 2

Tags: quadratic , algebra , functional equation , recurrence relation

Let $ \mathbb{R}^\plus{}$ be the set of all non-negative real numbers. Given two positive real numbers $ a$ and $ b,$ suppose that a mapping $ f: \mathbb{R}^\plus{} \mapsto \mathbb{R}^\plus{}$ satisfies the functional equation: \[ f(f(x)) \plus{} af(x) \equal{} b(a \plus{} b)x.\] Prove that there exists a unique solution of this equation.

1985 IMO Shortlist, 17

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.$

Mathley 2014-15, 5

Tags: sequence , recurrence relation , algebra

Given the sequence $(u_n)_{n=1}^{\infty}$, where $u_1 = 1, u_2 = 2$, and $u_{n + 2} = u_{n + 1} +u_ n+ \frac{(-1)^n-1}{2}$ for any positive integers $n$. Prove that every positive integers can be expressed as the sum of some distinguished numbers of the sequence of numbers $(u_n)_{n=1}^{\infty}$ Nguyen Duy Thai Son, The University of Danang, Da Nang.

2020 Jozsef Wildt International Math Competition, W53

Tags: recurrence relation , algebra , sequence

Define the sequence $(w_n)_{n\ge0}$ by the recurrence relation $$w_{n+2}=2w_{n+1}+3w_n,\enspace\enspace w_0=1,w_1=i,\enspace n=0,1,\ldots$$ (1) Find the general formula for $w_n$ and compute the first $9$ terms. (2) Show that $|\Re w_n-\Im w_n|=1$ for all $n\ge1$. [i]Proposed by Ovidiu Bagdasar[/i]

1969 IMO Shortlist, 31

Tags: permutation , combinatorics , counting , recurrence relation

$(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.$

2001 IMO Shortlist, 3

Tags: modular arithmetic , number theory , integer sequence , recurrence relation

Let $ a_1 \equal{} 11^{11}, \, a_2 \equal{} 12^{12}, \, a_3 \equal{} 13^{13}$, and $ a_n \equal{} |a_{n \minus{} 1} \minus{} a_{n \minus{} 2}| \plus{} |a_{n \minus{} 2} \minus{} a_{n \minus{} 3}|, n \geq 4.$ Determine $ a_{14^{14}}$.

2023 ISI Entrance UGB, 6

Tags: inequalities , recurrence relation

Let $\{u_n\}_{n \ge 1}$ be a sequence of real numbers defined as $u_1 = 1$ and \[ u_{n+1} = u_n + \frac{1}{u_n} \text{ for all $n \ge 1$.}\] Prove that $u_n \le \frac{3\sqrt{n}}{2}$ for all $n$.

1984 IMO Longlists, 16

Tags: linear recurrence , combinatorics , recurrence relation , algebra

The harmonic table is a triangular array: $1$ $\frac 12 \qquad \frac 12$ $\frac 13 \qquad \frac 16 \qquad \frac 13$ $\frac 14 \qquad \frac 1{12} \qquad \frac 1{12} \qquad \frac 14$ Where $a_{n,1} = \frac 1n$ and $a_{n,k+1} = a_{n-1,k} - a_{n,k}$ for $1 \leq k \leq n-1.$ Find the harmonic mean of the $1985^{th}$ row.