Olympiad problems

1969 IMO Longlists, 41

$(MON 2)$ Given reals $x_0, x_1, \alpha, \beta$, find an expression for the solution of the system \[x_{n+2} -\alpha x_{n+1} -\beta x_n = 0, \qquad n= 0, 1, 2, \ldots\]

1988 IMO Longlists, 1

Tags: sequence , divisibility , linear recurrence , algebra , linear algebra , modular arithmetic

An integer sequence is defined by \[{ a_n = 2 a_{n-1} + a_{n-2}}, \quad (n > 1), \quad a_0 = 0, a_1 = 1.\] Prove that $2^k$ divides $a_n$ if and only if $2^k$ divides $n$.

1979 IMO Shortlist, 9

Tags: combinatorics , linear recurrence , counting , recurrence relation

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}. \]

2019 Pan-African Shortlist, A1

Tags: linear recurrence , recurrence relation , induction , algebra

Let $(a_n)_{n=0}^{\infty}$ be a sequence of real numbers defined as follows: [list] [*] $a_0 = 3$, $a_1 = 2$, and $a_2 = 12$; and [*] $2a_{n + 3} - a_{n + 2} - 8a_{n + 1} + 4a_n = 0$ for $n \geq 0$. [/list] Show that $a_n$ is always a strictly positive integer.

2020 China Second Round Olympiad, 3

Tags: recurrence relation , linear recurrence , number theory

Let $a_1=1,$ $a_2=2,$ $a_n=2a_{n-1}+a_{n-2},$ $n=3,4,\cdots.$ Prove that for any integer $n\geq5,$ $a_n$ has at least one prime factor $p,$ such that $p\equiv 1\pmod{4}.$

1979 IMO Longlists, 28

Tags: recurrence relation , counting , linear recurrence , combinatorics

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}. \]

1971 IMO Longlists, 34

Tags: recurrence relation , linear recurrence , sequence , algebra

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

1988 IMO Longlists, 74

Tags: linear recurrence , inequality system , inequality , sequence

Let $ \{a_k\}^{\infty}_1$ be a sequence of non-negative real numbers such that: \[ a_k \minus{} 2 a_{k \plus{} 1} \plus{} a_{k \plus{} 2} \geq 0 \] and $ \sum^k_{j \equal{} 1} a_j \leq 1$ for all $ k \equal{} 1,2, \ldots$. Prove that: \[ 0 \leq a_{k} \minus{} a_{k \plus{} 1} < \frac {2}{k^2} \] for all $ k \equal{} 1,2, \ldots$.

PEN L Problems, 7

Tags: linear recurrence

Let $m$ be a positive integer. Define the sequence $\{a_{n}\}_{n \ge 0}$ by \[a_{0}=0, \; a_{1}=m, \; a_{n+1}=m^{2}a_{n}-a_{n-1}.\] Prove that an ordered pair $(a, b)$ of non-negative integers, with $a \le b$, gives a solution to the equation \[\frac{a^{2}+b^{2}}{ab+1}= m^{2}\] if and only if $(a, b)$ is of the form $(a_{n}, a_{n+1})$ for some $n \ge 0$.

PEN L Problems, 4

Tags: linear recurrence , induction

The Fibonacci sequence $\{F_{n}\}$ is defined by \[F_{1}=1, \; F_{2}=1, \; F_{n+2}=F_{n+1}+F_{n}.\] Show that $F_{mn}-F_{n+1}^{m}+F_{n-1}^{m}$ is divisible by $F_{n}^{3}$ for all $m \ge 1$ and $n>1$.

PEN L Problems, 9

Tags: linear recurrence

Let $\{u_{n}\}_{n \ge 0}$ be a sequence of positive integers defined by \[u_{0}= 1, \;u_{n+1}= au_{n}+b,\] where $a, b \in \mathbb{N}$. Prove that for any choice of $a$ and $b$, the sequence $\{u_{n}\}_{n \ge 0}$ contains infinitely many composite numbers.

1971 IMO Shortlist, 9

Tags: recurrence relation , linear recurrence , sequence , algebra

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

1969 IMO Shortlist, 41

Tags: linear recurrence , recurrence relation , algebra , system of equations

$(MON 2)$ Given reals $x_0, x_1, \alpha, \beta$, find an expression for the solution of the system \[x_{n+2} -\alpha x_{n+1} -\beta x_n = 0, \qquad n= 0, 1, 2, \ldots\]

2019 Pan-African, 1

Tags: linear recurrence , induction , algebra , recurrence relation

Let $(a_n)_{n=0}^{\infty}$ be a sequence of real numbers defined as follows: [list] [*] $a_0 = 3$, $a_1 = 2$, and $a_2 = 12$; and [*] $2a_{n + 3} - a_{n + 2} - 8a_{n + 1} + 4a_n = 0$ for $n \geq 0$. [/list] Show that $a_n$ is always a strictly positive integer.

PEN L Problems, 12

Tags: linear recurrence

The sequence $\{a_{n}\}_{n \ge 1}$ is defined by \[a_{1}=1, \; a_{2}=12, \; a_{3}=20, \; a_{n+3}= 2a_{n+2}+2a_{n+1}-a_{n}.\] Prove that $1+4a_{n}a_{n+1}$ is a square for all $n \in \mathbb{N}$.

PEN L Problems, 8

Tags: induction , linear recurrence

Let $\{x_{n}\}_{n\ge0}$ and $\{y_{n}\}_{n\ge0}$ be two sequences defined recursively as follows \[x_{0}=1, \; x_{1}=4, \; x_{n+2}=3 x_{n+1}-x_{n},\] \[y_{0}=1, \; y_{1}=2, \; y_{n+2}=3 y_{n+1}-y_{n}.\] [list=a][*] Prove that ${x_{n}}^{2}-5{y_{n}}^{2}+4=0$ for all non-negative integers. [*] Suppose that $a$, $b$ are two positive integers such that $a^{2}-5b^{2}+4=0$. Prove that there exists a non-negative integer $k$ such that $a=x_{k}$ and $b=y_{k}$.[/list]

PEN L Problems, 2

Tags: number theory , linear recurrence , greatest common divisor

The Fibonacci sequence $\{F_{n}\}$ is defined by \[F_{1}=1, \; F_{2}=1, \; F_{n+2}=F_{n+1}+F_{n}.\] Show that $\gcd (F_{m}, F_{n})=F_{\gcd (m, n)}$ for all $m, n \in \mathbb{N}$.

2007 Bulgarian Autumn Math Competition, Problem 12.4

Tags: prime number , linear recurrence , number theory

Let $p$ and $q$ be prime numbers and $\{a_{n}\}_{n=1}^{\infty}$ be a sequence of integers defined by: \[a_{0}=0, a_{1}=1, a_{n+2}=pa_{n+1}-qa_{n}\quad\forall n\geq 0\] Find $p$ and $q$ if there exists an integer $k$ such that $a_{3k}=-3$.

1979 IMO, 3

Tags: counting , recurrence relation , linear recurrence , combinatorics

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}. \]

PEN L Problems, 5

Tags: linear recurrence

The Fibonacci sequence $\{F_{n}\}$ is defined by \[F_{1}=1, \; F_{2}=1, \; F_{n+2}=F_{n+1}+F_{n}.\] Show that $F_{2n-1}^{2}+F_{2n+1}^{2}+1=3F_{2n-1}F_{2n+1}$ for all $n \ge 1$.

PEN L Problems, 10

Tags: linear recurrence

The sequence $\{y_{n}\}_{n \ge 1}$ is defined by \[y_{1}=y_{2}=1,\;\; y_{n+2}= (4k-5)y_{n+1}-y_{n}+4-2k.\] Determine all integers $k$ such that each term of this sequence is a perfect square.

PEN L Problems, 3

Tags: induction , linear recurrence

The Fibonacci sequence $\{F_{n}\}$ is defined by \[F_{1}=1, \; F_{2}=1, \; F_{n+2}=F_{n+1}+F_{n}.\] Show that $F_{mn-1}-F_{n-1}^{m}$ is divisible by $F_{n}^{2}$ for all $m \ge 1$ and $n>1$.

1984 IMO Shortlist, 19

Tags: algebra , combinatorics , recurrence relation , linear recurrence

The harmonic table is a triangular array: $1$ $\frac 12 \qquad \frac 12$ $\frac 13 \qquad \frac 16 \qquad \frac 13$ $\frac 14 \qquad \frac 1{12} \qquad \frac 1{12} \qquad \frac 14$ Where $a_{n,1} = \frac 1n$ and $a_{n,k+1} = a_{n-1,k} - a_{n,k}$ for $1 \leq k \leq n-1.$ Find the harmonic mean of the $1985^{th}$ row.

1984 IMO Longlists, 14

Tags: recurrence relation , linear recurrence , sequence , algebra

Let $c$ be a positive integer. The sequence $\{f_n\}$ is defined as follows: \[f_1 = 1, f_2 = c, f_{n+1} = 2f_n - f_{n-1} + 2 \quad (n \geq 2).\] Show that for each $k \in \mathbb N$ there exists $r \in \mathbb N$ such that $f_kf_{k+1}= f_r.$

PEN L Problems, 6

Tags: linear recurrence

Prove that no Fibonacci number can be factored into a product of two smaller Fibonacci numbers, each greater than 1.