Olympiad problems

2019 India PRMO, 3

Tags: recurrence , recursion

Let $x_{1}$ be a positive real number and for every integer $n \geq 1$ let $x_{n+1} = 1 + x_{1}x_{2}\ldots x_{n-1}x_{n}$. If $x_{5} = 43$, what is the sum of digits of the largest prime factors of $x_{6}$?

2006 Cuba MO, 7

Tags: algebra , recurrence relation , recurrence

The sequence $a_1, a_2, a_3, ...$ satisfies that $a_1 = 3$, $a_2 = -1$, $a_na_{n-2} +a_{n-1} = 2$ for all $n \ge 3$. Calculate $a_1 + a_2+ ... + a_{99}$.

2003 Czech And Slovak Olympiad III A, 3

Tags: recurrence relation , recurrence , combinatorics , algebra

A sequence $(x_n)_{n= 1}^{\infty}$ satisfies $x_1 = 1$ and for each $n > 1, x_n = \pm (n-1)x_{n-1} \pm (n-2)x_{n-2} \pm ... \pm 2x_2 \pm x_1$. Prove that the signs ” $\pm$” can be chosen so that $x_n \ne 12$ holds only for finitely many $n$.

2016 Puerto Rico Team Selection Test, 6

Tags: composition , function , algebra , recurrence

$N$ denotes the set of all natural numbers. Define a function $T: N \to N$ such that $T (2k) = k$ and $T (2k + 1) = 2k + 2$. We write $T^2 (n) = T (T (n))$ and in general $T^k (n) = T^{k-1} (T (n))$ for all $k> 1$. (a) Prove that for every $n \in N$, there exists $k$ such that $T^k (n) = 1$. (b) For $k \in N$, $c_k$ denotes the number of elements in the set $\{n: T^k (n) = 1\}$. Prove that $c_{k + 2} = c_{k + 1} + c_k$, for $1 \le k$.

2009 Math Prize For Girls Problems, 10

Tags: modular arithmetic , algebra , binomial theorem , recurrence

When the integer $ {\left(\sqrt{3} \plus{} 5\right)}^{103} \minus{} {\left(\sqrt{3} \minus{} 5\right)}^{103}$ is divided by 9, what is the remainder?

1981 IMO Shortlist, 9

Tags: algebra , sequence , recurrence , 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.$

2019 Saint Petersburg Mathematical Olympiad, 1

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

For a non-constant arithmetic progression $(a_n)$ there exists a natural $n$ such that $a_{n}+a_{n+1} = a_{1}+…+a_{3n-1}$ . Prove that there are no zero terms in this progression.

2013 AIME Problems, 9

Tags: modular arithmetic , recurrence , combinatorics

A $7 \times 1$ board is completely covered by $m \times 1$ tiles without overlap; each tile may cover any number of consecutive squares, and each tile lies completely on the board. Each tile is either red, blue, or green. Let $N$ be the number of tilings of the $7 \times 1$ board in which all three colors are used at least once. For example, a $1 \times 1$ red tile followed by a $2 \times 1$ green tile, a $1 \times 1$ green tile, a $2 \times 1$ blue tile, and a $1 \times 1$ green tile is a valid tiling. Note that if the $2 \times 1$ blue tile is replaced by two $1 \times 1$ blue tiles, this results in a different tiling. Find the remainder when $N$ is divided by $1000$.

2013 Iran MO (2nd Round), 3

Tags: function , inequalities , algebra , recurrence

Let $\{a_n\}_{n=1}^{\infty}$ be a sequence of positive integers for which \[ a_{n+2} = \left[\frac{2a_n}{a_{n+1}}\right]+\left[\frac{2a_{n+1}}{a_n}\right]. \] Prove that there exists a positive integer $m$ such that $a_m=4$ and $a_{m+1} \in\{3,4\}$. [b]Note.[/b] $[x]$ is the greatest integer not exceeding $x$.

V Soros Olympiad 1998 - 99 (Russia), 10.6

Tags: algebra , sequence , recurrence , recurrence relation

Find the formula for the general term of the sequence an, for which $a_1 = 1$, $a_2 = 3$, $a_{n+1} = 3a_n-2a_{n-1}$ (you need to express an in terms of $n$).

OIFMAT III 2013, 10

Tags: sequence , recurrence relation , recurrence , number theory

Prove that the sequence defined by: $$ y_ {n + 1} = \frac {1} {2} (3y_ {n} + \sqrt {5y_ {n} ^ {2} -4}) , \,\, \forall n \ge 0$$ with $ y_ {0} = 1$ consists only of integers.

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

2017 Ecuador NMO (OMEC), 5

Tags: perfect square , number theory , sequence , recurrence

Let the sequences $(x_n)$ and $(y_n)$ be defined by $x_0 = 0$, $x_1 = 1$, $x_{n + 2} = 3x_{n + 1}-2x_n$ for $n = 0, 1, ...$ and $y_n = x^2_n+2^{n + 2}$ for $n = 0, 1, ...,$ respectively. Show that for all n> 0, and n is the square of a odd integer.

2024 Bulgarian Winter Tournament, 9.4

Tags: combinatorics , combinatorial geometry , recurrence

There are $11$ points equally spaced on a circle. Some of the segments having endpoints among these vertices are drawn and colored in two colors, so that each segment meets at an internal for it point at most one other segment from the same color. What is the greatest number of segments that could be drawn?

V Soros Olympiad 1998 - 99 (Russia), 11.9

Tags: recurrence , recurrence relation , sequence , algebra

The sequence of $a_n$ is determined by the relation $$a_{n+1}=\frac{k+a_n}{1-a_n}$$ where $k > 0$. It is known that $a_{13} = a_1$. What values can $k$ take?

1978 Putnam, B3

Tags: polynomial , recurrence , sequence

The sequence $(Q_{n}(x))$ of polynomials is defined by $$Q_{1}(x)=1+x ,\; Q_{2}(x)=1+2x,$$ and for $m \geq 1 $ by $$Q_{2m+1}(x)= Q_{2m}(x) +(m+1)x Q_{2m-1}(x),$$ $$Q_{2m+2}(x)= Q_{2m+1}(x) +(m+1)x Q_{2m}(x).$$ Let $x_n$ be the largest real root of $Q_{n}(x).$ Prove that $(x_n )$ is an increasing sequence and that $\lim_{n\to \infty} x_n =0.$

2025 VJIMC, 1

Tags: limit , recurrence , characteristic polynomial , sequence

Let $x_0=a, x_1= b, x_2 = c$ be given real numbers and let $x_{n+2} = \frac{x_n + x_{n-1}}{2}$ for all $n\geq 1$. Show that the sequence $(x_n)_{n\geq 0}$ converges and find its limit.

2015 Korea - Final Round, 5

Tags: number theory , recurrence

For a fixed positive integer $k$, there are two sequences $A_n$ and $B_n$. They are defined inductively, by the following recurrences. $A_1 = k$, $A_2 = k$, $A_{n+2} = A_{n}A_{n+1}$ $B_1 = 1$, $B_2 = k$, $B_{n+2} = \frac{B^3_{n+1}+1}{B_{n}}$ Prove that for all positive integers $n$, $A_{2n}B_{n+3}$ is an integer.

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

1973 Spain Mathematical Olympiad, 3

Tags: complex analysis , recurrence relation , recurrence , sequence , analysis

The sequence $(a_n)$ of complex numbers is considered in the complex plane, in which is: $$a_0 = 1, \,\,\, a_n = a_{n-1} +\frac{1}{n}(\cos 45^o + i \sin 45^o )^n.$$ Prove that the sequence of the real parts of the terms of $(a_n)$ is convergent and its limit is a number between $0.85$ and $1.15$.

2025 NEPALTST, 1

Tags: algebra , recurrence , inequality

Let the sequence $\{a_n\}_{n \geq 1}$ be defined by \[ a_1 = 1, \quad a_{n+1} = a_n + \frac{1}{\sqrt[2024]{a_n}} \quad \text{for } n \geq 1, \, n \in \mathbb{N} \] Prove that \[ a_n^{2025} >n^{2024} \] for all positive integers $n \geq 2$. $\textbf{Proposed by Prajit Adhikari, Nepal.}$

2018 Hanoi Open Mathematics Competitions, 7

Tags: algebra , recurrence , sequence

Let $\{u_n\}_ {n\ge 1}$ be given sequence satisfying the conditions: $u_1 = 0$, $u_2 = 1$, $u_{n+1} = u_{n-1} + 2n - 1$ for $n \ge 2$. 1) Calculate $u_5$. 2) Calculate $u_{100} + u_{101}$.

2015 ELMO Problems, 1

Tags: number theory , algebra , recurrence , divisibility

Define the sequence $a_1 = 2$ and $a_n = 2^{a_{n-1}} + 2$ for all integers $n \ge 2$. Prove that $a_{n-1}$ divides $a_n$ for all integers $n \ge 2$. [i]Proposed by Sam Korsky[/i]

2006 QEDMO 3rd, 10

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

Define a sequence $\left( a_{n}\right) _{n\in\mathbb{N}}$ by $a_{1}=a_{2}=a_{3}=1$ and $a_{n+1}=\dfrac{a_{n}^{2}+a_{n-1}^{2}}{a_{n-2}}$ for every integer $n\geq3$. Show that all elements $a_{i}$ of this sequence are integers. (L. J. Mordell and apparently Dana Scott, see also http://oeis.org/A064098)

2015 Postal Coaching, 4

Tags: sequence , induction , recurrence , number theory

The sequence $<a_n>$ is defined as follows, $a_1=a_2=1$, $a_3=2$, $$a_{n+3}=\frac{a_{n+2}a_{n+1}+n!}{a_n},$$ $n \ge 1$. Prove that all the terms in the sequence are integers.