Olympiad problems

2021 Macedonian Mathematical Olympiad, Problem 1

Tags: sequence , inequality , am-gm , recursive , factorial , inequalities

Let $(a_n)^{+\infty}_{n=1}$ be a sequence defined recursively as follows: $a_1=1$ and $$a_{n+1}=1 + \sum\limits_{k=1}^{n}ka_k$$ For every $n > 1$, prove that $\sqrt[n]{a_n} < \frac {n+1}{2}$.

2012 Miklós Schweitzer, 1

Tags: recursive , computable analysis , discrete mathematics , real analysis

Is there any real number $\alpha$ for which there exist two functions $f,g: \mathbb{N} \to \mathbb{N}$ such that $$\alpha=\lim_{n \to \infty} \frac{f(n)}{g(n)},$$ but the function which associates to $n$ the $n$-th decimal digit of $\alpha$ is not recursive?

2020 Australian Maths Olympiad, 4

Tags: recurrence relation , australia , sequence , recursive , algebra

Define the sequence $A_1, A_2, A_3, \dots$ by $A_1 = 1$ and for $n=1,2,3,\dots$ $$A_{n+1}=\frac{A_n+2}{A_n +1}.$$ Define the sequences $B_1, B_2, B_3,\dots$ by $B_1=1$ and for $n=1,2,3,\dots$ $$B_{n+1}=\frac{B_n^2 +2}{2B_n}.$$ Prove that $B_{n+1}=A_{2^n}$ for all non-negative integers $n$.

1993 Mexico National Olympiad, 4

Tags: number theory , recursive , function

$f(n,k)$ is defined by (1) $f(n,0) = f(n,n) = 1$ and (2) $f(n,k) = f(n-1,k-1) + f(n-1,k)$ for $0 < k < n$. How many times do we need to use (2) to find $f(3991,1993)$?

2012 German National Olympiad, 1

Tags: number theory , sequence , recursive , composite

Define a sequence $(a_n)$ by $a_0 =-4 , a_1 =-7$ and $a_{n+2}= 5a_{n+1} -6a_n$ for $n\geq 0.$ Prove that there are infinitely many positive integers $n$ such that $a_n$ is composite.

2019 Taiwan APMO Preliminary Test, P4

Tags: algebra , floor function , sequence , recursive

We define a sequence ${a_n}$: $$a_1=1,a_{n+1}=\sqrt{a_n+n^2},n=1,2,...$$ (1)Find $\lfloor a_{2019}\rfloor$ (2)Find $\lfloor a_{1}^2\rfloor+\lfloor a_{2}^2\rfloor+...+\lfloor a_{20}^2\rfloor$

1994 All-Russian Olympiad, 5

Tags: number theory , recursive , sequence , power of 2

Let $a_1$ be a natural number not divisible by $5$. The sequence $a_1,a_2,a_3, . . .$ is defined by $a_{n+1} =a_n+b_n$, where $b_n$ is the last digit of $a_n$. Prove that the sequence contains infinitely many powers of two. (N. Agakhanov)

2002 German National Olympiad, 4

Tags: algebra , inequalities , convergence , sequence , recursive

Given a positive real number $a_1$, we recursively define $a_{n+1} = 1+a_1 a_2 \cdots \cdot a_n.$ Furthermore, let $$b_n = \frac{1}{a_1 } + \frac{1}{a_2 } +\cdots + \frac{1}{a_n }.$$ Prove that $b_n < \frac{2}{a_1}$ for all positive integers $n$ and that this is the smallest possible bound.

2022 Iran MO (3rd Round), 4

Tags: recursive , integer sequence , periodic sequence , number theory

$a_1,a_2,\ldots$ is a sequence of [u]nonzero integer[/u] numbers that for all $n\in\mathbb{N}$, if $a_n=2^\alpha k$ such that $k$ is an odd integer and $\alpha$ is a nonnegative integer then: $a_{n+1}=2^\alpha-k$. Prove that if this sequence is periodic, then for all $n\in\mathbb{N}$ we have: $a_{n+2}=a_n$. (The sequence $a_1,a_2,\ldots$ is periodic iff there exists natural number $d$ that for all $n\in\mathbb{N}$ we have: $a_{n+d}=a_n$)

2005 Mexico National Olympiad, 4

Tags: number theory , recursive , arithmetic progression

A list of numbers $a_1,a_2,\ldots,a_m$ contains an arithmetic trio $a_i, a_j, a_k$ if $i < j < k$ and $2a_j = a_i + a_k$. Let $n$ be a positive integer. Show that the numbers $1, 2, 3, \ldots, n$ can be reordered in a list that does not contain arithmetic trios.