Olympiad problems

1999 Vietnam National Olympiad, 3

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, 6

Tags: Linear Recurrences

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

PEN L Problems, 7

Tags: Linear Recurrences , pen

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, 5

Tags: Linear Recurrences

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, 1

Tags: induction , algebra , binomial theorem , Linear Recurrences , pen

An integer sequence $\{a_{n}\}_{n \ge 1}$ is defined by \[a_{0}=0, \; a_{1}=1, \; a_{n+2}=2a_{n+1}+a_{n}\] Show that $2^{k}$ divides $a_{n}$ if and only if $2^{k}$ divides $n$.

1984 IMO Longlists, 14

Tags: algebra , Sequence , recurrence relation , Linear Recurrences , IMO Shortlist

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

1988 IMO Longlists, 74

Tags: inequality system , Inequality , Sequence , Linear Recurrences , IMO Shortlist

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

1984 IMO Shortlist, 6

Tags: algebra , Sequence , recurrence relation , Linear Recurrences , IMO Shortlist

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, 2

Tags: number theory , greatest common divisor , Linear Recurrences

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

1988 IMO Shortlist, 24

Tags: inequality system , Inequality , Sequence , Linear Recurrences , IMO Shortlist

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, 10

Tags: Linear Recurrences

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.

1979 IMO, 3

Tags: combinatorics , recurrence relation , Linear Recurrences , counting , IMO , IMO 1979

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

1984 IMO Shortlist, 19

Tags: algebra , combinatorics , recurrence relation , Linear Recurrences , IMO Shortlist

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.

PEN L Problems, 11

Tags: Linear Recurrences

Let the sequence $\{K_{n}\}_{n \ge 1}$ be defined by \[K_{1}=2, K_{2}=8, K_{n+2}=3K_{n+1}-K_{n}+5(-1)^{n}.\] Prove that if $K_{n}$ is prime, then $n$ must be a power of $3$.

2019 Pan-African, 1

Tags: recurrence relation , Linear Recurrences , algebra , induction , PAMO

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, 4

Tags: induction , Linear Recurrences

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, 3

Tags: induction , Linear Recurrences

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 Longlists, 16

Tags: algebra , combinatorics , recurrence relation , Linear Recurrences , IMO Shortlist

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.

1971 IMO Shortlist, 9

Tags: algebra , Sequence , recurrence relation , Linear Recurrences , IMO Shortlist

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

1971 IMO Longlists, 34

Tags: algebra , Sequence , recurrence relation , Linear Recurrences , IMO Shortlist

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, 1

Tags: modular arithmetic , linear algebra , algebra , Sequence , Divisibility , Linear Recurrences , IMO Shortlist

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

PEN L Problems, 13

Tags: induction , algebra , polynomial , quadratics , difference of squares , special factorizations , Linear Recurrences

The sequence $\{x_{n}\}_{n \ge 1}$ is defined by \[x_{1}=x_{2}=1, \; x_{n+2}= 14x_{n+1}-x_{n}-4.\] Prove that $x_{n}$ is always a perfect square.

1979 IMO Longlists, 28

Tags: combinatorics , recurrence relation , Linear Recurrences , counting , IMO , IMO 1979

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

1979 IMO Shortlist, 9

Tags: combinatorics , recurrence relation , Linear Recurrences , counting , IMO , IMO 1979

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

1969 IMO Longlists, 41

Tags: algebra , recurrence relation , system of equations , Linear Recurrences , IMO Shortlist , IMO Longlist

$(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\]