Olympiad problems

2012 Singapore Senior Math Olympiad, 4

Let $a_1, a_2, ..., a_n, a_{n+1}$ be a finite sequence of real numbers satisfying $a_0 = a_{n+1} = 0$ and $|a_{k-1} - 2a_{k} + a_{k+1}| \leq 1$ for $k = 1, 2, ..., n$ Prove that for $k=0, 1, ..., n+1,$ $|a_k| \leq \frac{k(n+1-k)}{2}$

2022 Switzerland - Final Round, 5

Tags: number theory , recurrence relation , divisor

For an integer $a \ge 2$, denote by $\delta_(a) $ the second largest divisor of $a$. Let $(a_n)_{n\ge 1}$ be a sequence of integers such that $a_1 \ge 2$ and $$a_{n+1} = a_n + \delta_(a_n)$$ for all $n \ge 1$. Prove that there exists a positive integer $k$ such that $a_k$ is divisible by $3^{2022}$.

1979 IMO, 3

Tags: combinatorics , recurrence relation , counting , linear recurrence

Let $A$ and $E$ be opposite vertices of an octagon. A frog starts at vertex $A.$ From any vertex except $E$ it jumps to one of the two adjacent vertices. When it reaches $E$ it stops. Let $a_n$ be the number of distinct paths of exactly $n$ jumps ending at $E$. Prove that: \[ a_{2n-1}=0, \quad a_{2n}={(2+\sqrt2)^{n-1} - (2-\sqrt2)^{n-1} \over\sqrt2}. \]

1967 IMO, 6

Tags: combinatorics , recurrence relation , system of equations

In a sports meeting a total of $m$ medals were awarded over $n$ days. On the first day one medal and $\frac{1}{7}$ of the remaining medals were awarded. On the second day two medals and $\frac{1}{7}$ of the remaining medals were awarded, and so on. On the last day, the remaining $n$ medals were awarded. How many medals did the meeting last, and what was the total number of medals ?

1966 Dutch Mathematical Olympiad, 2

Tags: number theory , greatest common divisor , gcd , recurrence relation

For all $n$, $t_{n+1} = 2(t_n)^2 - 1$. Prove that gcd $(t_n,t_m) = 1$ if $n \ne m$.

1969 IMO Longlists, 28

Tags: polynomial , number theory , sequence , divisibility , recurrence relation

$(GBR 5)$ Let us define $u_0 = 0, u_1 = 1$ and for $n\ge 0, u_{n+2} = au_{n+1}+bu_n, a$ and $b$ being positive integers. Express $u_n$ as a polynomial in $a$ and $b.$ Prove the result. Given that $b$ is prime, prove that $b$ divides $a(u_b -1).$

1989 IMO Shortlist, 16

Tags: algebra , sequence , recurrence relation , inequality

The set $ \{a_0, a_1, \ldots, a_n\}$ of real numbers satisfies the following conditions: [b](i)[/b] $ a_0 \equal{} a_n \equal{} 0,$ [b](ii)[/b] for $ 1 \leq k \leq n \minus{} 1,$ \[ a_k \equal{} c \plus{} \sum^{n\minus{}1}_{i\equal{}k} a_{i\minus{}k} \cdot \left(a_i \plus{} a_{i\plus{}1} \right)\] Prove that $ c \leq \frac{1}{4n}.$

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.

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]

1989 IMO Longlists, 55

Tags: algebra , sequence , recurrence relation , inequality

The set $ \{a_0, a_1, \ldots, a_n\}$ of real numbers satisfies the following conditions: [b](i)[/b] $ a_0 \equal{} a_n \equal{} 0,$ [b](ii)[/b] for $ 1 \leq k \leq n \minus{} 1,$ \[ a_k \equal{} c \plus{} \sum^{n\minus{}1}_{i\equal{}k} a_{i\minus{}k} \cdot \left(a_i \plus{} a_{i\plus{}1} \right)\] Prove that $ c \leq \frac{1}{4n}.$

1989 Poland - Second Round, 5

Tags: algebra , recurrence relation , floor function , number theory

Given a sequence $ (c_n) $ of natural numbers defined recursively: $ c_1 = 2 $, $ c_{n+1} = \left[ \frac{3}{2}c_n\right] $. Prove that there are infinitely many even numbers and infinitely many odd numbers among the terms of this sequence.

2016 India IMO Training Camp, 1

Tags: number theory , recurrence relation , power of 2 , geometry , bir tinga qimmat ekan boru

Let $n$ be a natural number. We define sequences $\langle a_i\rangle$ and $\langle b_i\rangle$ of integers as follows. We let $a_0=1$ and $b_0=n$. For $i>0$, we let $$\left( a_i,b_i\right)=\begin{cases} \left(2a_{i-1}+1,b_{i-1}-a_{i-1}-1\right) & \text{if } a_{i-1}<b_{i-1},\\ \left( a_{i-1}-b_{i-1}-1,2b_{i-1}+1\right) & \text{if } a_{i-1}>b_{i-1},\\ \left(a_{i-1},b_{i-1}\right) & \text{if } a_{i-1}=b_{i-1}.\end{cases}$$ Given that $a_k=b_k$ for some natural number $k$, prove that $n+3$ is a power of two.

2021 Dutch IMO TST, 1

Tags: number theory , sequence , recurrence relation

The sequence of positive integers $a_0, a_1, a_2, . . .$ is defined by $a_0 = 3$ and $$a_{n+1} - a_n = n(a_n - 1)$$ for all $n \ge 0$. Determine all integers $m \ge 2$ for which $gcd (m, a_n) = 1$ for all $n \ge 0$.

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

2020 Paraguay Mathematical Olympiad, 2

Tags: algebra , recurrence relation

Laura is putting together the following list: $a_0, a_1, a_2, a_3, a_4, ..., a_n$, where $a_0 = 3$ and $a_1 = 4$. She knows that the following equality holds for any value of $n$ integer greater than or equal to $1$: $$a_n^2-2a_{n-1}a_{n+1} =(-2)^n.$$Laura calculates the value of $a_4$. What value does it get?

1988 Austrian-Polish Competition, 5

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

Two sequences $(a_k)_{k\ge 0}$ and $(b_k)_{k\ge 0}$ of integers are given by $b_k = a_k + 9$ and $a_{k+1} = 8b_k + 8$ for $k\ge 0$. Suppose that the number $1988$ occurs in one of these sequences. Show that the sequence $(a_k)$ does not contain any nonzero perfect square.

2004 VTRMC, Problem 2

Tags: recurrence relation , function , algebra , sequence

A sequence of integers $\{f(n)\}$ for $n=0,1,2,\ldots$ is defined as follows: $f(0)=0$ and for $n>0$, $$\begin{matrix}f(n)=&f(n-1)+3,&\text{if }n=0\text{ or }1\pmod6,\\&f(n-1)+1,&\text{if }n=2\text{ or }5\pmod6,\\&f(n-1)+2,&\text{if }n=3\text{ or }4\pmod6.\end{matrix}$$Derive an explicit formula for $f(n)$ when $n\equiv0\pmod6$, showing all necessary details in your derivation.

2017 Irish Math Olympiad, 5

Tags: number theory , recurrence relation , algebra

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

2016 Switzerland - Final Round, 6

Tags: number theory , sequence , recurrence relation

Let $a_n$ be a sequence of natural numbers defined by $a_1 = m$ and for $n > 1$. We call apair$ (a_k, a_{\ell })$ [i]interesting [/i] if (i) $0 < \ell - k < 2016$, (ii) $a_k$ divides $a_{\ell }$. Show that there exists a $m$ such that the sequence $a_n$ contains no interesting pair.

2012 Switzerland - Final Round, 4

Tags: number theory , recurrence relation , prime

Show that there is no infinite sequence of primes $p_1, p_2, p_3, . . .$ there any for each $ k$: $p_{k+1} = 2p_k - 1$ or $p_{k+1} = 2p_k + 1$ is fulfilled. Note that not the same formula for every $k$.

2024 IMC, 8

Tags: recurrence relation , limit , sequence

Define the sequence $x_1,x_2,\dots$ by the initial terms $x_1=2, x_2=4$, and the recurrence relation \[x_{n+2}=3x_{n+1}-2x_n+\frac{2^n}{x_n} \quad \text{for} \quad n \ge 1.\] Prove that $\lim_{n \to \infty} \frac{x_n}{2^n}$ exists and satisfies \[\frac{1+\sqrt{3}}{2} \le \lim_{n \to \infty} \frac{x_n}{2^n} \le \frac{3}{2}.\]

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 Saudi Arabia Pre-TST + Training Tests, 3.3

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

Define sequence of positive integers $(a_n)$ as $a_1 = a$ and $a_{n+1} = a^2_n + 1$ for $n \ge 1$. Prove that there is no index $n$ for which $$\prod_{k=1}^{n} \left(a^2_k + a_k + 1\right)$$ is a perfect square.

1990 IMO Longlists, 62

Tags: function , algebra , recurrence relation , recursion

Let $ a, b \in \mathbb{N}$ with $ 1 \leq a \leq b,$ and $ M \equal{} \left[\frac {a \plus{} b}{2} \right].$ Define a function $ f: \mathbb{Z} \mapsto \mathbb{Z}$ by \[ f(n) \equal{} \begin{cases} n \plus{} a, & \text{if } n \leq M, \\ n \minus{} b, & \text{if } n >M. \end{cases} \] Let $ f^1(n) \equal{} f(n),$ $ f_{i \plus{} 1}(n) \equal{} f(f^i(n)),$ $ i \equal{} 1, 2, \ldots$ Find the smallest natural number $ k$ such that $ f^k(0) \equal{} 0.$

1987 Greece National Olympiad, 3

Tags: algebra , sequence , recurrence relation

There is no sequence $x_n$ strictly increasing with terms natural numbers such that : $$ x_n+x_{k}=x_{nk}, \ \ for \, any \,\,\, n, k \in \mathbb{N}^*$$