Olympiad problems

1979 Chisinau City MO, 170

The numbers $a_1,a_2,...,a_n$ ( $n\ge 3$) satisfy the relations $$a_1=a_n = 0, a_{k-1}+ a_{k+1}\le 2a_k \,\,\, (k = 2, 3,..., n-1)$$ Prove that the numbers $a_1,a_2,...,a_n$ are non-negative.

1988 Dutch Mathematical Olympiad, 2

Tags: limit , recurrence relation , algebra , sequence , trigonometry

Given is a number $a$ with 0 $\le \alpha \le \pi$. A sequence $c_0,c_1, c_2,...$ is defined as $$c_0=\cos \alpha$$ $$C_{n+1}=\sqrt{\frac{1+c_n}{2}} \,\, for \,\,\, n=0,1,2,...$$ Calculate $\lim_{n\to \infty}2^{2n+1}(1-c_n)$

2005 VTRMC, Problem 3

Tags: recurrence relation , counting , combinatorics

We wish to tile a strip of $n$ $1$-inch by $1$-inch squares. We can use dominos which are made up of two tiles that cover two adjacent squares, or $1$-inch square tiles which cover one square. We may cover each square with one or two tiles and a tile can be above or below a domino on a square, but no part of a domino can be placed on any part of a different domino. We do not distinguish whether a domino is above or below a tile on a given square. Let $t(n)$ denote the number of ways the strip can be tiled according to the above rules. Thus for example, $t(1)=2$ and $t(2)=8$. Find a recurrence relation for $t(n)$, and use it to compute $t(6)$.

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

2015 Thailand Mathematical Olympiad, 1

Tags: divide , recurrence relation , divisible , number theory

Let $p$ be a prime, and let $a_1, a_2, a_3, . . .$ be a sequence of positive integers so that $a_na_{n+2} = a^2_{n+1} + p$ for all positive integers $n$. Show that $a_{n+1}$ divides $a_n + a_{n+2}$ for all positive integers $n$.

2013 Korea Junior Math Olympiad, 3

Tags: algebra , sequence , recurrence relation , sum , positive integer , diophantine equation

$\{a_n\}$ is a positive integer sequence such that $a_{i+2} = a_{i+1} +a_i$ (for all $i \ge 1$). For positive integer $n$, define as $$b_n=\frac{1}{a_{2n+1}}\Sigma_{i=1}^{4n-2}a_i$$ Prove that $b_n$ is positive integer.

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.