Olympiad problems

1996 Austrian-Polish Competition, 3

The polynomials $P_{n}(x)$ are defined by $P_{0}(x)=0,P_{1}(x)=x$ and \[P_{n}(x)=xP_{n-1}(x)+(1-x)P_{n-2}(x) \quad n\geq 2\] For every natural number $n\geq 1$, find all real numbers $x$ satisfying the equation $P_{n}(x)=0$.

2022 Saudi Arabia IMO TST, 1

Tags: number theory , divide , number theory with sequences , recurrence relation

Let $(a_n)$ be the integer sequence which is defined by $a_1= 1$ and $$ a_{n+1}=a_n^2 + n \cdot a_n \,\, , \,\, \forall n \ge 1.$$ Let $S$ be the set of all primes $p$ such that there exists an index $i$ such that $p|a_i$. Prove that the set $S$ is an infinite set and it is not equal to the set of all primes.

1973 Swedish Mathematical Competition, 2

Tags: fibonacci number , algebra , sequence , recurrence relation

The Fibonacci sequence $f_1,f_2,f_3,\dots$ is defined by $f_1=f_2=1$, $f_{n+2}=f_{n+1}+f_n$. Find all $n$ such that $f_n = n^2$.

2007 Germany Team Selection Test, 1

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

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]

2017 Irish Math Olympiad, 5

Tags: recurrence relation , algebra , number theory

The sequence $a = (a_0, a_1,a_2,...)$ is defined by $a_0 = 0, a_1 =2$ and $$a_{n+2} = 2a_{n+1} + 41a_n$$Prove that $a_{2016}$ is divisible by $2017.$

1979 Dutch Mathematical Olympiad, 3

Tags: recurrence relation , sequence , number theory , last digit

Define $a_1 = 1979$ and $a_{n+1} = 9^{a_n}$ for $n = 1,2,3,...$. Determine the last two digits of $a_{1979}$.

2011 Dutch IMO TST, 4

Tags: recurrence relation , sequence , prime number , number theory

Prove that there exists no innite sequence of prime numbers $p_0, p_1, p_2,...$ such that for all positive integers $k$: $p_k = 2p_{k-1} + 1$ or $p_k = 2p_{k-1} - 1$.

2018 Irish Math Olympiad, 9

Tags: perfect cube , sequence , recurrence relation , number theory

The sequence of positive integers $a_1, a_2, a_3, ...$ satisfies $a_{n+1} = a^2_{n} + 2018$ for $n \ge 1$. Prove that there exists at most one $n$ for which $a_n$ is the cube of an integer.

1992 IMO Longlists, 55

Tags: induction , algebra , recurrence relation , sequence

For any positive integer $ x$ define $ g(x)$ as greatest odd divisor of $ x,$ and \[ f(x) \equal{} \begin{cases} \frac {x}{2} \plus{} \frac {x}{g(x)} & \text{if \ $x$ is even}, \\ 2^{\frac {x \plus{} 1}{2}} & \text{if \ $x$ is odd}. \end{cases} \] Construct the sequence $ x_1 \equal{} 1, x_{n \plus{} 1} \equal{} f(x_n).$ Show that the number 1992 appears in this sequence, determine the least $ n$ such that $ x_n \equal{} 1992,$ and determine whether $ n$ is unique.

2004 Thailand Mathematical Olympiad, 7

Tags: algebra , sequence , recurrence relation

Let f be a function such that $f(0) = 0, f(1) = 1$, and $f(n) = 2f(n-1)- f(n- 2) + (-1)^n(2n - 4)$ for all integers $n \ge 2$. Find f(n) in terms of $n$.

OIFMAT III 2013, 10

Tags: number theory , sequence , recurrence relation , recurrence

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.

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

1971 IMO Shortlist, 9

Tags: algebra , sequence , recurrence relation , linear recurrence

Let $T_k = k - 1$ for $k = 1, 2, 3,4$ and \[T_{2k-1} = T_{2k-2} + 2^{k-2}, T_{2k} = T_{2k-5} + 2^k \qquad (k \geq 3).\] Show that for all $k$, \[1 + T_{2n-1} = \left[ \frac{12}{7}2^{n-1} \right] \quad \text{and} \quad 1 + T_{2n} = \left[ \frac{17}{7}2^{n-1} \right],\] where $[x]$ denotes the greatest integer not exceeding $x.$

2010 Saudi Arabia IMO TST, 3

Tags: recurrence relation , divide , number theory

Consider the sequence $a_1 = 3$ and $a_{n + 1} =\frac{3a_n^2+1}{2}-a_n$ for $n = 1 ,2 ,...$. Prove that if $n$ is a power of $3$ then $n$ divides $a_n$ .

1977 IMO Longlists, 28

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

Let $n$ be an integer greater than $1$. Define \[x_1 = n, y_1 = 1, x_{i+1} =\left[ \frac{x_i+y_i}{2}\right] , y_{i+1} = \left[ \frac{n}{x_{i+1}}\right], \qquad \text{for }i = 1, 2, \ldots\ ,\] where $[z]$ denotes the largest integer less than or equal to $z$. Prove that \[ \min \{x_1, x_2, \ldots, x_n \} =[ \sqrt n ]\]

1964 Putnam, A4

Tags: recurrence relation , periodic

Let $p_n$ be a bounded sequence of integers which satisfies the recursion $$p_n =\frac{p_{n-1} +p_{n-2} + p_{n-3}p _{n-4}}{p_{n-1} p_{n-2}+ p_{n-3} +p_{n-4}}.$$ Show that the sequence eventually becomes periodic.

2005 VJIMC, Problem 4

Tags: recurrence relation , algebra , sequence , limit

Let $(x_n)_{n\ge2}$ be a sequence of real numbers such that $x_2>0$ and $x_{n+1}=-1+\sqrt[n]{1+nx_n}$ for $n\ge2$. Find (a) $\lim_{n\to\infty}x_n$, (b) $\lim_{n\to\infty}nx_n$.

2021 Francophone Mathematical Olympiad, 1

Tags: sequence , number theory , divide , recurrence relation

Let $a_1,a_2,a_3,\ldots$ and $b_1,b_2,b_3,\ldots$ be positive integers such that $a_{n+2} = a_n + a_{n+1}$ and $b_{n+2} = b_n + b_{n+1}$ for all $n \ge 1$. Assume that $a_n$ divides $b_n$ for infinitely many values of $n$. Prove that there exists an integer $c$ such that $b_n = c a_n$ for all $n \ge 1$.

2004 Federal Competition For Advanced Students, P2, 4

Tags: perfect square , sequence , recurrence relation , number theory

Show that there is an infinite sequence $a_1,a_2,...$ of natural numbers such that $a^2_1+a^2_2+ ...+a^2_N$ is a perfect square for all $N$. Give a recurrent formula for one such sequence.

1996 IMO Shortlist, 3

Tags: integer sequence , extremal combinatorics , recurrence relation , perfect square , number theory

A finite sequence of integers $ a_0, a_1, \ldots, a_n$ is called quadratic if for each $ i$ in the set $ \{1,2 \ldots, n\}$ we have the equality $ |a_i \minus{} a_{i\minus{}1}| \equal{} i^2.$ a.) Prove that any two integers $ b$ and $ c,$ there exists a natural number $ n$ and a quadratic sequence with $ a_0 \equal{} b$ and $ a_n \equal{} c.$ b.) Find the smallest natural number $ n$ for which there exists a quadratic sequence with $ a_0 \equal{} 0$ and $ a_n \equal{} 1996.$

2011 Dutch IMO TST, 4

Tags: recurrence relation , sequence , prime number , number theory

Prove that there exists no innite sequence of prime numbers $p_0, p_1, p_2,...$ such that for all positive integers $k$: $p_k = 2p_{k-1} + 1$ or $p_k = 2p_{k-1} - 1$.

1981 Austrian-Polish Competition, 2

Tags: sequence , recurrence relation , algebra , rational

The sequence $a_0, a_1, a_2, ...$ is defined by $a_{n+1} = a^2_n + (a_n - 1)^2$ for $n \ge 0$. Find all rational numbers $a_0$ for which there exist four distinct indices $k, m, p, q$ such that $a_q - a_p = a_m - a_k$.

2014 Regional Competition For Advanced Students, 3

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

The sequence $(a_n)$ is defined with the recursion $a_{n + 1} = 5a^6_n + 3a^3_{n-1} + a^2_{n-2}$ for $n\ge 2$ and the set of initial values $\{a_0, a_1, a_2\} = \{2013, 2014, 2015\}$. (That is, the initial values are these three numbers in any order.) Show that the sequence contains no sixth power of a natural number.

2011 Indonesia TST, 4

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

Let $a, b$, and $c$ be positive integers such that $gcd(a, b) = 1$. Sequence $\{u_k\}$, is given such that $u_0 = 0$, $u_1 = 1$, and u$_{k+2} = au_{k+1} + bu_k$ for all $k \ge 0$. Let $m$ be the least positive integer such that $c | u_m$ and $n$ be an arbitrary positive integer such that $c | u_n$. Show that $m | n$. [hide=PS.] There was a typo in the last line, as it didn't define what n does. Wording comes from [b]tst-2011-1.pdf[/b] from [url=https://sites.google.com/site/imoidn/idntst/2011tst]here[/url]. Correction was made according to #2[/hide]

2022 Assara - South Russian Girl's MO, 6

Tags: algebra , sequence , recurrence relation

There are $2022$ numbers arranged in a circle $a_1, a_2, . . ,a_{2022}$. It turned out that for any three consecutive $a_i$, $a_{i+1}$, $a_{i+2}$ the equality $a_i =\sqrt2 a_{i+2} - \sqrt3 a_{i+1}$. Prove that $\sum^{2022}_{i=1} a_ia_{i+2} = 0$, if we know that $a_{2023} = a_1$, $a_{2024} = a_2$.