Olympiad problems

1980 IMO Shortlist, 2

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

2010 Saudi Arabia BMO TST, 3

Tags: sequence , recurrence relation , algebra

Let $(a_n )_{n \ge o}$ and $(b_n )_{n \ge o}$ be sequences defined by $a_{n+2} = a_{n+1}+ a_n$ , $n = 0 , 1 , . .. $, $a_0 = 1$, $a_1 = 2$, and $b_{n+2} = b_{n+1} + b_n$ , $n = 0 , 1 , . . .$, $b_0 = 2$, $b_1 = 1$. How many integers do the sequences have in common?

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

2005 VTRMC, Problem 3

Tags: recurrence relation , counting , 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)$.

2020 Jozsef Wildt International Math Competition, W26

Tags: recurrence relation , algebra , sequence

Let $P_n$ denote the $n$-th Pell number defined by $P_{n+1}=2P_n+P_{n-1}$, $P_0=0$, $P_1=1$. Furthermore, let $T_n$ denote the $n$-th triangular number, that is $T_n=\binom{n+1}2$. Show that $$\sum_{n=0}^\infty4T_n\cdot\frac{P_n}{3^{n+2}}=P_3+P_4$$ [i]Proposed by Ángel Plaza[/i]

1972 IMO, 3

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

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

1984 IMO Shortlist, 6

Tags: algebra , sequence , recurrence relation , linear recurrence

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

1988 Dutch Mathematical Olympiad, 2

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

Given is a number $a$ with 0 $\le \alpha \le \pi$. A sequence $c_0,c_1, c_2,...$ is defined as $$c_0=\cos \alpha$$ $$C_{n+1}=\sqrt{\frac{1+c_n}{2}} \,\, for \,\,\, n=0,1,2,...$$ Calculate $\lim_{n\to \infty}2^{2n+1}(1-c_n)$

1965 Swedish Mathematical Competition, 4

Tags: algebra , function , recurrence relation , sequence

Find constants $A > B$ such that $\frac{f\left( \frac{1}{1+2x}\right) }{f(x)}$ is independent of $x$, where $f(x) = \frac{1 + Ax}{1 + Bx}$ for all real $x \ne - \frac{1}{B}$. Put $a_0 = 1$, $a_{n+1} = \frac{1}{1 + 2a_n}$. Find an expression for an by considering $f(a_0), f(a_1), ...$.

2006 IMO Shortlist, 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]

1976 IMO, 2

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

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.

2012 Indonesia TST, 1

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

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

2019 Federal Competition For Advanced Students, P1, 1

Tags: sequence , recurrence relation , recurrence , algebra

We consider the two sequences $(a_n)_{n\ge 0}$ and $(b_n) _{n\ge 0}$ of integers, which are given by $a_0 = b_0 = 2$ and $a_1= b_1 = 14$ and for $n\ge 2$ they are defined as $a_n = 14a_{n-1} + a_{n-2}$ , $b_n = 6b_{n-1}-b_{n-2}$. Determine whether there are infinite numbers that occur in both sequences

2022 Brazil EGMO TST, 5

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

VMEO IV 2015, 10.1

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

Where $n$ is a positive integer, the sequence $a_n$ is determined by the formula $$a_{n+1}=\frac{1}{a_1 + a_2 +... + a_n} -\sqrt2, \,a_1 = 1.$$ Find the limit of the sequence $S_n$ defined by $S_n=a_1 + a_2 +... + a_n$.

2013 Korea Junior Math Olympiad, 3

Tags: algebra , sequence , recurrence relation , sum , positive integer , diophantine equation

$\{a_n\}$ is a positive integer sequence such that $a_{i+2} = a_{i+1} +a_i$ (for all $i \ge 1$). For positive integer $n$, define as $$b_n=\frac{1}{a_{2n+1}}\Sigma_{i=1}^{4n-2}a_i$$ Prove that $b_n$ is positive integer.

2020 New Zealand MO, 8

Tags: algebra , sequence , recurrence relation , number theory

For a positive integer $x$, define a sequence $a_0, a_1, a_2, . . .$ according to the following rules: $a_0 = 1$, $a_1 = x + 1$ and $$a_{n+2} = xa_{n+1} - a_n$$ for all $n \ge 0$. Prove that there exist infinitely many positive integers x such that this sequence does not contain a prime number.

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.

2005 Korea Junior Math Olympiad, 3

Tags: algebra , sequence , recurrence relation , minimum

For a positive integer $K$, define a sequence, $\{a_n\}$, as following: $a_1 = K$ and $a_{n+1} =a_n -1$ if $a_n$ is even $a_{n+1} =\frac{a_n - 1}{2}$ if $a_n$ is odd , for all $n \ge 1$. Find the smallest value of $K$, which makes $a_{2005}$ the first term equal to $0$.

2023 Brazil Undergrad MO, 5

Tags: modular arithmetic , generating functions , recurrence relation , algebra

A drunken horse moves on an infinite board whose squares are numbered in pairs $(a, b) \in \mathbb{Z}^2$. In each movement, the 8 possibilities $$(a, b) \rightarrow (a \pm 1, b \pm 2),$$ $$(a, b) \rightarrow (a \pm 2, b \pm 1)$$ are equally likely. Knowing that the knight starts at $(0, 0)$, calculate the probability that, after $2023$ moves, it is in a square $(a, b)$ with $a \equiv 4 \pmod 8$ and $b \equiv 5 \pmod 8$.

2010 Bundeswettbewerb Mathematik, 2

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

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.

1996 Greece National Olympiad, 1

Tags: recurrence relation , algebra , geometric progression , sequence , geometric sequence

Let $a_n$ be a sequence of positive numbers such that: i) $\dfrac{a_{n+2}}{a_n}=\dfrac{1}{4}$, for every $n\in\mathbb{N}^{\star}$ ii) $\dfrac{a_{k+1}}{a_k}+\dfrac{a_{n+1}}{a_n}=1$, for every $ k,n\in\mathbb{N}^{\star}$ with $|k-n|\neq 1$. (a) Prove that $(a_n)$ is a geometric progression. (n) Prove that exists $t>0$, such that $\sqrt{a_{n+1}}\leq \dfrac{1}{2}a_n+t$