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]

1982 All Soviet Union Mathematical Olympiad, 328

Tags: fibonacci , sequence , algebra

Every member, starting from the third one, of two sequences $\{a_n\}$ and $\{b_n\}$ equals to the sum of two preceding ones. First members are: $a_1 = 1, a_2 = 2, b_1 = 2, b_2 = 1$. How many natural numbers are encountered in both sequences (may be on the different places)?

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

2021 Saudi Arabia IMO TST, 8

Tags: fibonacci , additive representation , combinatorics

The Fibonacci numbers $F_0, F_1, F_2, . . .$ are defined inductively by $F_0=0, F_1=1$, and $F_{n+1}=F_n+F_{n-1}$ for $n \ge 1$. Given an integer $n \ge 2$, determine the smallest size of a set $S$ of integers such that for every $k=2, 3, . . . , n$ there exist some $x, y \in S$ such that $x-y=F_k$. [i]Proposed by Croatia[/i]

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?

2020 Brazil National Olympiad, 2

Tags: fibonacci , analytic number theory , number theory

For a positive integer $a$, define $F_1 ^{(a)}=1$, $F_2 ^{(a)}=a$ and for $n>2$, $F_n ^{(a)}=F_{n-1} ^{(a)}+F_{n-2} ^{(a)}$. A positive integer is [i]fibonatic[/i] when it is equal to $F_n ^{(a)}$ for a positive integer $a$ and $n>3$. Prove that there are infintely many not [i]fibonatic[/i] integers.

2020 IMO Shortlist, C4

Tags: fibonacci , additive representation , combinatorics

The Fibonacci numbers $F_0, F_1, F_2, . . .$ are defined inductively by $F_0=0, F_1=1$, and $F_{n+1}=F_n+F_{n-1}$ for $n \ge 1$. Given an integer $n \ge 2$, determine the smallest size of a set $S$ of integers such that for every $k=2, 3, . . . , n$ there exist some $x, y \in S$ such that $x-y=F_k$. [i]Proposed by Croatia[/i]

1996 Akdeniz University MO, 2

Tags: fibonacci , sequence , number theory

Let $u_1=1,u_2=1$ and for all $k \geq 1$'s $$u_{k+2}=u_{k+1}+u_{k}$$ Prove that for all $m \geq 1$'s $5$ divides $u_{5m}$

2017 USA TSTST, 6

Tags: number theory , fibonacci , algebra

A sequence of positive integers $(a_n)_{n \ge 1}$ is of [i]Fibonacci type[/i] if it satisfies the recursive relation $a_{n + 2} = a_{n + 1} + a_n$ for all $n \ge 1$. Is it possible to partition the set of positive integers into an infinite number of Fibonacci type sequences? [i]Proposed by Ivan Borsenco[/i]

2021 Taiwan TST Round 2, C

Tags: fibonacci , additive representation , combinatorics

The Fibonacci numbers $F_0, F_1, F_2, . . .$ are defined inductively by $F_0=0, F_1=1$, and $F_{n+1}=F_n+F_{n-1}$ for $n \ge 1$. Given an integer $n \ge 2$, determine the smallest size of a set $S$ of integers such that for every $k=2, 3, . . . , n$ there exist some $x, y \in S$ such that $x-y=F_k$. [i]Proposed by Croatia[/i]

2023 SG Originals, Q3

Tags: combinatorics , fibonacci

Bugs Bunny plays a game in the Euclidean plane. At the $n$-th minute $(n \geq 1)$, Bugs Bunny hops a distance of $F_n$ in the North, South, East, or West direction, where $F_n$ is the $n$-th Fibonacci number (defined by $F_1 = F_2 =1$ and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 3$). If the first two hops were perpendicular, prove that Bugs Bunny can never return to where he started. [i]Proposed by Dylan Toh[/i]

2023 Philippine MO, 7

Tags: fibonacci , number theory

A set of positive integers is said to be [i]pilak[/i] if it can be partitioned into 2 disjoint subsets $F$ and $T$, each with at least $2$ elements, such that the elements of $F$ are consecutive Fibonacci numbers, and the elements of $T$ are consecutive triangular numbers. Find all positive integers $n$ such that the set containing all the positive divisors of $n$ except $n$ itself is pilak.

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

2018 Romanian Master of Mathematics Shortlist, N2

Tags: fibonacci , number theory

Prove that for each positive integer $k$ there exists a number base $b$ along with $k$ triples of Fibonacci numbers $(F_u,F_v,F_w)$ such that when they are written in base $b$, their concatenation is also a Fibonacci number written in base $b$. (Fibonacci numbers are defined by $F_1 = F_2 = 1$ and $F_{n+2} = F_{n+1} + F_n$ for all positive integers $n$.) [i]Proposed by Serbia[/i]

2014 BAMO, 4

Tags: fibonacci , sequence , divisibility , number theory

Let $F_1, F_2, F_3 \cdots$ be the Fibonacci sequence, the sequence of positive integers satisfying $$F_1 =F_2=1$$ and $$F_{n+2} = F_{n+1} + F_n$$ for all $n \ge 1$. Does there exist an $n \ge 1$ such that $F_n$ is divisible by $2014$? Prove your answer.

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

2019 USA TSTST, 6

Tags: integer polynomial , fibonacci , algebra

Suppose $P$ is a polynomial with integer coefficients such that for every positive integer $n$, the sum of the decimal digits of $|P(n)|$ is not a Fibonacci number. Must $P$ be constant? (A [i]Fibonacci number[/i] is an element of the sequence $F_0, F_1, \dots$ defined recursively by $F_0=0, F_1=1,$ and $F_{k+2} = F_{k+1}+F_k$ for $k\ge 0$.) [i]Nikolai Beluhov[/i]

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

2021 Thailand TST, 2

Tags: fibonacci , additive representation , combinatorics

The Fibonacci numbers $F_0, F_1, F_2, . . .$ are defined inductively by $F_0=0, F_1=1$, and $F_{n+1}=F_n+F_{n-1}$ for $n \ge 1$. Given an integer $n \ge 2$, determine the smallest size of a set $S$ of integers such that for every $k=2, 3, . . . , n$ there exist some $x, y \in S$ such that $x-y=F_k$. [i]Proposed by Croatia[/i]

2020 Jozsef Wildt International Math Competition, W55

Tags: fibonacci number , diophantine equation , fibonacci , number theory

Prove that the equation $$1320x^3=(y_1+y_2+y_3+y_4)(z_1+z_2+z_3+z_4)(t_1+t_2+t_3+t_4+t_5)$$ has infinitely many solutions in the set of Fibonacci numbers. [i]Proposed by Mihály Bencze[/i]

2009 BAMO, 2

Tags: fibonacci , sum

The Fibonacci sequence is the list of numbers that begins $1, 2, 3, 5, 8, 13$ and continues with each subsequent number being the sum of the previous two. Prove that for every positive integer $n$ when the first $n$ elements of the Fibonacci sequence are alternately added and subtracted, the result is an element of the sequence or the negative of an element of the sequence. For example, when $n = 4$ we have $1-2+3-5 = -3$ and $3$ is an element of the Fibonacci sequence.

ICMC 6, 3

Tags: combinatorics , fibonacci

Bugs Bunny plays a game in the Euclidean plane. At the $n$-th minute $(n \geq 1)$, Bugs Bunny hops a distance of $F_n$ in the North, South, East, or West direction, where $F_n$ is the $n$-th Fibonacci number (defined by $F_1 = F_2 =1$ and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 3$). If the first two hops were perpendicular, prove that Bugs Bunny can never return to where he started. [i]Proposed by Dylan Toh[/i]

2018 Mathematical Talent Reward Programme, MCQ: P 3

Tags: fibonacci , algebra

$F_{n}$ denotes the Fibonacci Sequence where $F_{1}=0, F_{2}=1, F_{n}=F_{n-1}+F_{n-2},\ \forall \ n \geq 3$ Find$$\sum\limits_{n=3}^{\infty}\frac{18+999F_n}{F_{n-1}\times F_{n+1}}$$ [list=1] [*] 2016 [*] 2017 [*] 2018 [*] None of these [/list]