Olympiad problems

2015 Israel National Olympiad, 7

The Fibonacci sequence $F_n$ is defined by $F_0=0,F_1=1$ and the recurrence relation $F_n=F_{n-1}+F_{n-2}$ for all integers $n\geq2$. Let $p\geq3$ be a prime number. [list=a] [*] Prove that $F_{p-1}+F_{p+1}-1$ is divisible by $p$. [*] Prove that $F_{p^{k+1}-1}+F_{p^{k+1}+1}-\left(F_{p^k-1}+F_{p^k+1}\right)$ is divisible by $p^{k+1}$ for any positive integer $k$. [/list]

1999 Croatia National Olympiad, Problem 3

Tags: sum , summation , fibonacci , fibonacci sequence , algebra

Let $(a_n)$ be defined by $a_1=a_2=1$ and $a_n=a_{n-1}+a_{n-2}$ for $n>2$. Compute the sum $\frac{a_1}2+\frac{a_2}{2^2}+\frac{a_3}{2^3}+\ldots$.

2017 Harvard-MIT Mathematics Tournament, 9

Tags: modular arithmetic , fibonacci sequence , number theory

The Fibonacci sequence is defined as follows: $F_0=0$, $F_1=1$, and $F_n=F_{n-1}+F_{n-2}$ for all integers $n\ge 2$. Find the smallest positive integer $m$ such that $F_m\equiv 0 \pmod {127}$ and $F_{m+1}\equiv 1\pmod {127}$.

2018 Mathematical Talent Reward Programme, SAQ: P 5

Tags: fibonacci sequence , periodic sequence , remainder , polynomial , algebra

[list=1] [*] Prove that, the sequence of remainders obtained when the Fibonacci numbers are divided by $n$ is periodic, where $n$ is a natural number. [*] There exists no such non-constant polynomial with integer coefficients such that for every Fibonacci number $n,$ $ P(n)$ is a prime. [/list]

2016 Taiwan TST Round 2, 2

Tags: fibonacci sequence , number theory

Let $\left< F_n\right>$ be the Fibonacci sequence, that is, $F_0=0$, $F_1=1$, and $F_{n+2}=F_{n+1}+F_{n}$ holds for all nonnegative integers $n$. Find all pairs $(a,b)$ of positive integers with $a < b$ such that $F_n-2na^n$ is divisible by $b$ for all positive integers $n$.

1992 IMO Longlists, 78

Tags: fibonacci , fibonacci sequence , sequence , limit , calculus

Let $F_n$ be the nth Fibonacci number, defined by $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n > 2$. Let $A_0, A_1, A_2,\cdots$ be a sequence of points on a circle of radius $1$ such that the minor arc from $A_{k-1}$ to $A_k$ runs clockwise and such that \[\mu(A_{k-1}A_k)=\frac{4F_{2k+1}}{F_{2k+1}^2+1}\] for $k \geq 1$, where $\mu(XY )$ denotes the radian measure of the arc $XY$ in the clockwise direction. What is the limit of the radian measure of arc $A_0A_n$ as $n$ approaches infinity?

1988 Spain Mathematical Olympiad, 4

Tags: fibonacci sequence , number theory

The Fibonacci sequence is given by $a_1 = 1, a_2 = 2$ and $a_{n+1} = a_n +a_{n-1}$ for $n > 1$. Express $a_{2n}$ in terms of only $a_{n-1},a_n,a_{n+1}$.

VMEO I 2004, 2

Tags: fibonacci number , fibonacci sequence , fibonacci , divisible , perfect power , number theory

The Fibonacci numbers $(F_n)_{n=1}^{\infty}$ are defined as follows: $$F_1 = F_2 = 1, F_n = F_{n-2} + F_{n-1}, n = 3, 4, ...$$ Assume $p$ is a prime greater than $3$. With $m$ being a natural number greater than $3$, find all $n$ numbers such that $F_n$ is divisible by $p^m$.

1983 IMO Longlists, 52

Tags: fibonacci , fibonacci sequence , sequence , algebra , polynomial

Let $(F_n)_{n\geq 1} $ be the Fibonacci sequence $F_1 = F_2 = 1, F_{n+2} = F_{n+1} + F_n (n \geq 1),$ and $P(x)$ the polynomial of degree $990$ satisfying \[ P(k) = F_k, \qquad \text{ for } k = 992, . . . , 1982.\] Prove that $P(1983) = F_{1983} - 1.$

1992 IMO Longlists, 18

Tags: fibonacci , fibonacci sequence , combinatorics of words , sequence , combinatorics

Fibonacci numbers are defined as follows: $F_0 = F_1 = 1, F_{n+2} = F_{n+1}+F_n, n \geq 0$. Let $a_n$ be the number of words that consist of $n$ letters $0$ or $1$ and contain no two letters $1$ at distance two from each other. Express $a_n$ in terms of Fibonacci numbers.

2018 Stanford Mathematics Tournament, 4

Tags: fibonacci , fibonacci sequence , fibonacci number , number theory

Let $F_k$ denote the series of Fibonacci numbers shifted back by one index, so that $F_0 = 1$, $F_1 = 1,$ and $F_{k+1} = F_k +F_{k-1}$. It is known that for any fixed $n \ge 1$ there exist real constants $b_n$, $c_n$ such that the following recurrence holds for all $k \ge 1$: $$F_{n\cdot (k+1)} = b_n \cdot F_{n \cdot k} + c_n \cdot F_{n\cdot (k-1)}.$$ Prove that $|c_n| = 1$ for all $n \ge 1$.

2015 Singapore MO Open, 4

Tags: fibonacci sequence , number theory

Let $f_0, f_1,...$ be the Fibonacci sequence: $f_0 = f_1 = 1, f_n = f_{n-1} + f_{n-2}$ if $n \geq 2$. Determine all possible positive integers $n$ so that there is a positive integer $a$ such that $f_n \leq a \leq f_{n+1}$ and that $a( \frac{1}{f_1}+\frac{1}{f_1f_2}+\cdots+\frac{1}{f_1f_2...f_n} )$ is an integer.

2012 IFYM, Sozopol, 7

Tags: fibonacci sequence , combinatorics

Let $M=\{1,2,...,n\}$. Prove that the number of pairs $(A,a)$, where $A\subset M$ and $a$ is a permutation of $M$, for which $a(A)\cap A=\emptyset $, is equal to $n!.F_{n+1}$, where $F_{n+1}$ is the $n+1$ member of the Fibonacci sequence.

2017 Mathematical Talent Reward Programme, MCQ: P 4

Tags: algebra , fibonacci sequence

Let $F_1=F_2=1$. We define inductively $F_{n+1}=F_n+F_{n-1}$ for all $n\geq 2$. Then the sum $$F_1+F_2+\cdots+F_{2017}$$ is [list=1] [*] Even but not divisible by 3 [*] Odd but divisible by 3 [*] Odd and leaves remainder 1 when divisible by 3 [*] None of these [/list]

2007 IMAC Arhimede, 1

Tags: algebra , fibonacci , fibonacci sequence , inequalities , number theory

Let $(f_n) _{n\ge 0}$ be the sequence defined by$ f_0 = 0, f_1 = 1, f_{n + 2 }= f_{n + 1} + f_n$ for $n> 0$ (Fibonacci string) and let $t_n =$ ${n+1}\choose{2}$ for $n \ge 1$ . Prove that: a) $f_1^2+f_2^2+...+f_n^2 = f_n \cdot f_{n+1}$ for $n \ge 1$ b) $\frac{1}{n^2} \cdot \Sigma_{k=1}^{n}\left( \frac{t_k}{f_k}\right)^2 \ge \frac{t_{n+1}^2}{9 f_n \cdot f_{n+1}}$

2019 Jozsef Wildt International Math Competition, W. 19

Tags: number theory , fibonacci sequence , lucas sequence

Let $\{F_n\}_{n\in\mathbb{Z}}$ and $\{L_n\}_{n\in\mathbb{Z}}$ denote the Fibonacci and Lucas numbers, respectively, given by $$F_{n+1} = F_n + F_{n-1}\ \text{and}\ L_{n+1} = L_n + L_{n-1}\ \text{for all}\ n \geq 1$$with $F_0 = 0$, $F_1 = 1$, $L_0 = 2$, and $L_1 = 1$. Prove that for integers $n \geq 1$ and $j \geq 0$ [list=1] [*]$\sum \limits_{k=1}^n F_{k\pm j}L_{k\mp j}=F_{2n+1}-1+\begin{cases} 0, & \text{if}\ n\ \text{is even}\\ \left(-1\right)^{\pm j}F_{\pm 2j}, & \text{if}\ n\ \text{is odd} \end{cases}$ [*] $\sum \limits_{k=1}^nF_{k+j}F_{k-j}L_{k+j}L_{k-j}=\frac{F_{4n+2}-1-nL_{4j}}{5}$ [/list]

1992 IMO Shortlist, 18

Tags: sequence , fibonacci , fibonacci sequence , inequality , floor function , algebra

Let $ \lfloor x \rfloor$ denote the greatest integer less than or equal to $ x.$ Pick any $ x_1$ in $ [0, 1)$ and define the sequence $ x_1, x_2, x_3, \ldots$ by $ x_{n\plus{}1} \equal{} 0$ if $ x_n \equal{} 0$ and $ x_{n\plus{}1} \equal{} \frac{1}{x_n} \minus{} \left \lfloor \frac{1}{x_n} \right \rfloor$ otherwise. Prove that \[ x_1 \plus{} x_2 \plus{} \ldots \plus{} x_n < \frac{F_1}{F_2} \plus{} \frac{F_2}{F_3} \plus{} \ldots \plus{} \frac{F_n}{F_{n\plus{}1}},\] where $ F_1 \equal{} F_2 \equal{} 1$ and $ F_{n\plus{}2} \equal{} F_{n\plus{}1} \plus{} F_n$ for $ n \geq 1.$

1997 Slovenia National Olympiad, Problem 2

Tags: fibonacci sequence , fibonacci

The Fibonacci sequence $f_n$ is defined by $f_1=f_2=1$ and $f_{n+2}=f_{n+1}+f_n$ for $n\in\mathbb N$. (a) Show that $f_{1005}$ is divisible by $10$. (b) Show that $f_{1005}$ is not divisible by $100$.

2019 Jozsef Wildt International Math Competition, W. 17

Tags: fibonacci sequence , number theory

Let $f_n=\left(1+\frac{1}{n}\right)^n\left((2n-1)!F_n\right)^{\frac{1}{n}}$. Find $\lim \limits_{n \to \infty}(f_{n+1} - f_n)$ where $F_n$ denotes the $n$th Fibonacci number (given by $F_0 = 0$, $F_1 = 1$, and by $F_{n+1} = F_n + F_{n-1}$ for all $n \geq 1$

2016 Israel National Olympiad, 5

Tags: algebra , number theory , fibonacci , fibonacci sequence , degree , polynomial

The Fibonacci sequence $F_n$ is defined by $F_1=F_2=1$ and the recurrence relation $F_n=F_{n-1}+F_{n-2}$ for all integers $n\geq3$. Let $m,n\geq1$ be integers. Find the minimal degree $d$ for which there exists a polynomial $f(x)=a_dx^d+a_{d-1}x^{d-1}+\dots+a_1x+a_0$, which satisfies $f(k)=F_{m+k}$ for all $k=0,1,...,n$.

2019 Jozsef Wildt International Math Competition, W. 40

Tags: fibonacci sequence , number theory

Let $f_n$ be $n$th Fibonacci number defined by recurrence $f_{n+1} - f_n - f_{n-1} = 0$, $n \in \mathbb{N}$ and initial conditions $f_0 = 0$, $f_1 = 1$. Prove that for any $n \in \mathbb{N}$ $$(n - 1) (n + 1) (2nf_{n+1} - (n + 6) f_n)$$is divisible by 150 for any $n \in \mathbb{N}$.

1981 IMO Shortlist, 4

Tags: fibonacci , fibonacci sequence , sequence , number theory , algebra

Let $\{fn\}$ be the Fibonacci sequence $\{1, 1, 2, 3, 5, \dots.\}. $ (a) Find all pairs $(a, b)$ of real numbers such that for each $n$, $af_n +bf_{n+1}$ is a member of the sequence. (b) Find all pairs $(u, v)$ of positive real numbers such that for each $n$, $uf_n^2 +vf_{n+1}^2$ is a member of the sequence.

1992 IMO Longlists, 79

Tags: algebra , floor function , sequence , fibonacci , fibonacci sequence , inequality

Let $ \lfloor x \rfloor$ denote the greatest integer less than or equal to $ x.$ Pick any $ x_1$ in $ [0, 1)$ and define the sequence $ x_1, x_2, x_3, \ldots$ by $ x_{n\plus{}1} \equal{} 0$ if $ x_n \equal{} 0$ and $ x_{n\plus{}1} \equal{} \frac{1}{x_n} \minus{} \left \lfloor \frac{1}{x_n} \right \rfloor$ otherwise. Prove that \[ x_1 \plus{} x_2 \plus{} \ldots \plus{} x_n < \frac{F_1}{F_2} \plus{} \frac{F_2}{F_3} \plus{} \ldots \plus{} \frac{F_n}{F_{n\plus{}1}},\] where $ F_1 \equal{} F_2 \equal{} 1$ and $ F_{n\plus{}2} \equal{} F_{n\plus{}1} \plus{} F_n$ for $ n \geq 1.$

2022 Baltic Way, 7

Tags: combinatorics , fibonacci , fibonacci sequence , fibonacci number

The writer Arthur has $n \ge1$ co-authors who write books with him. Each book has a list of authors including Arthur himself. No two books have the same set of authors. At a party with all his co-author, each co-author writes on a note how many books they remember having written with Arthur. Inspecting the numbers on the notes, they discover that the numbers written down are the first $n$ Fibonacci numbers (defined by $F_1 = F_2 = 1$ and $F_{k+2}= F_{k+1} + F_k$). For which $n$ is it possible that none of the co-authors had a lapse of memory?

2019 Dutch Mathematical Olympiad, 4

Tags: inequalities , fibonacci sequence , fibonacci , sum , algebra

The sequence of Fibonacci numbers $F_0, F_1, F_2, . . .$ is defined by $F_0 = F_1 = 1 $ and $F_{n+2} = F_n+F_{n+1}$ for all $n > 0$. For example, we have $F_2 = F_0 + F_1 = 2, F_3 = F_1 + F_2 = 3, F_4 = F_2 + F_3 = 5$, and $F_5 = F_3 + F_4 = 8$. The sequence $a_0, a_1, a_2, ...$ is defined by $a_n =\frac{1}{F_nF_{n+2}}$ for all $n \ge 0$. Prove that for all $m \ge 0$ we have: $a_0 + a_1 + a_2 + ... + a_m < 1$.