Olympiad problems

OIFMAT III 2013, 10

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.

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)

V Soros Olympiad 1998 - 99 (Russia), 10.6

Tags: algebra , Sequence , Recurrence , recurrence relations

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

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}$?

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.

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

1981 IMO Shortlist, 9

Tags: algebra , Sequence , Recurrence , recurrence relation , IMO Shortlist

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

2003 IMO Shortlist, 7

Tags: modular arithmetic , polynomial , Recurrence , Sequence , Divisibility , prime , IMO Shortlist

The sequence $a_0$, $a_1$, $a_2,$ $\ldots$ is defined as follows: \[a_0=2, \qquad a_{k+1}=2a_k^2-1 \quad\text{for }k \geq 0.\] Prove that if an odd prime $p$ divides $a_n$, then $2^{n+3}$ divides $p^2-1$. [hide="comment"] Hi guys , Here is a nice problem: Let be given a sequence $a_n$ such that $a_0=2$ and $a_{n+1}=2a_n^2-1$ . Show that if $p$ is an odd prime such that $p|a_n$ then we have $p^2\equiv 1\pmod{2^{n+3}}$ Here are some futher question proposed by me :Prove or disprove that : 1) $gcd(n,a_n)=1$ 2) for every odd prime number $p$ we have $a_m\equiv \pm 1\pmod{p}$ where $m=\frac{p^2-1}{2^k}$ where $k=1$ or $2$ Thanks kiu si u [i]Edited by Orl.[/i] [/hide]

2022 Saudi Arabia BMO + EGMO TST, 2.1

Tags: recurrence relation , Recurrence , number theory

Define $a_0 = 2$ and $a_{n+1} = a^2_n + a_n -1$ for $n \ge 0$. Prove that $a_n$ is coprime to $2n + 1$ for all $n \in N$.

2019 Saint Petersburg Mathematical Olympiad, 1

Tags: arithmetic sequence , algebra , Arithmetic Progression , Recurrence , recurrence relation

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.

1999 IMO Shortlist, 3

Tags: combinatorics , IMO Shortlist , Recurrence , Sequences , counting

A biologist watches a chameleon. The chameleon catches flies and rests after each catch. The biologist notices that: [list=1][*]the first fly is caught after a resting period of one minute; [*]the resting period before catching the $2m^\text{th}$ fly is the same as the resting period before catching the $m^\text{th}$ fly and one minute shorter than the resting period before catching the $(2m+1)^\text{th}$ fly; [*]when the chameleon stops resting, he catches a fly instantly.[/list] [list=a][*]How many flies were caught by the chameleon before his first resting period of $9$ minutes in a row? [*]After how many minutes will the chameleon catch his $98^\text{th}$ fly? [*]How many flies were caught by the chameleon after 1999 minutes have passed?[/list]

2021 Malaysia IMONST 2, 3

Tags: Recurrence

Given a sequence of positive integers $$a_1, a_2, a_3, a_4, a_5, \dots$$ such that $a_2 > a_1$ and $a_{n+2} = 3a_{n+1} - 2a_n$ for all $n \geq 1$. Prove that $a_{2021} > 2^{2019}$.

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?

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.

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

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?

2015 ELMO Problems, 1

Tags: Elmo , 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]

2015 Romania Team Selection Tests, 2

Tags: bounded , Sequences , Recurrence , algebra , Romanian TST

Let $(a_n)_{n \geq 0}$ and $(b_n)_{n \geq 0}$ be sequences of real numbers such that $ a_0>\frac{1}{2}$ , $a_{n+1} \geq a_n$ and $b_{n+1}=a_n(b_n+b_{n+2})$ for all non-negative integers $n$ . Show that the sequence $(b_n)_{n \geq 0}$ is bounded .

2003 Miklós Schweitzer, 6

Tags: college contests , Miklos Schweitzer , Sequences , Recurrence

Show that the recursion $n=x_n(x_{n-1}+x_n+x_{n+1})$, $n=1,2,\ldots$, $x_0=0$ has exaclty one nonnegative solution. (translated by L. Erdős)

2019 Federal Competition For Advanced Students, P1, 1

Tags: Sequence , recurrence relation , Recurrence , algebra , Austria

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

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

2017 Ecuador NMO (OMEC), 5

Tags: number theory , Perfect Squares , 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.

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?

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