Questions tagged [fibonacci-numbers]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
56 votes
28 answers
11k views

Nontrivial question about Fibonacci numbers?

I'm looking for a nontrivial, but not super difficult question concerning Fibonacci numbers. It should be at a level suitable for an undergraduate course. Here is a (not so good) example of the sort ...
45 votes
5 answers
3k views

Fibonacci series captures Euler $e=2.718\dots$

The Fibonacci recurrence $F_n=F_{n-1}+F_{n-2}$ allows values for all indices $n\in\mathbb{Z}$. There is an almost endless list of properties of these numbers in all sorts of ways. The below question ...
T. Amdeberhan's user avatar
28 votes
4 answers
9k views

Is 8 the largest cube in the Fibonacci sequence?

Can you prove that 8 is the largest cube in the Fibonacci sequence?
Pratik Poddar's user avatar
20 votes
3 answers
4k views

Reciprocals of Fibonacci numbers

Is the sum of the reciprocals of Fibonacci numbers a transcendental?
vamsi krishna's user avatar
20 votes
4 answers
2k views

Non-enumerative proof that, in average, less than 50% of tiles in domino tiling of 2-by-n rectangle are vertical?

Is there a non-enumerative proof that, in average, less than 50% of tiles in domino tiling of 2-by-n rectangle are vertical? It is a nice exercise with rational generating functions (or equivalently, ...
Sam Hopkins's user avatar
  • 22.7k
19 votes
2 answers
700 views

A rational function related to Fibonacci numbers

Let $F_n$ denote a Fibonacci number ($F_1=F_2=1$, $F_{n+1}=F_n+F_{n-1}$ for $n\geq 2$). Define $$\prod_{k=1}^n (1+x^{F_{k+1}}) = \sum_j f(n,j)x^j. $$ For a positive integer $r$ let $$ v_r(n) = \sum_j ...
Richard Stanley's user avatar
17 votes
1 answer
552 views

Complexity of a Fibonacci numbers discrete log variation

In my work I encountered the following FIBMOD PROBLEM: Given $k,m$ in binary, decide if there exists $n$ such that $\, F_n = k \,$ (mod $m$). Here $F_n$ is a Fibonacci number. This is a variation ...
Igor Pak's user avatar
  • 16.3k
16 votes
2 answers
546 views

Number of coefficients equal to $k$ in certain "Fibonacci polynomials"

Let $F_i$ denote the $i$th Fibonacci number (with $F_1=F_2=1$). Define $$ P_n(x) = \prod_{i=1}^n (1+x^{F_{i+1}}). $$ Let $\nu_k(n)$ denote the number of coefficients of the polynomial $P_n(x)$ that ...
Richard Stanley's user avatar
14 votes
3 answers
1k views

On the finite sum of reciprocal Fibonacci sequences

I want to check if $$\left\lfloor \left( \sum_{k=n}^{2n}{\frac{1}{F_{2k}}} \right)^{-1} \right\rfloor =F_{2n-1}~~(n\ge 3) \tag{$*$}$$ where $\lfloor x \rfloor$ is th floor function. The Fibonacci ...
fusheng's user avatar
  • 65
11 votes
2 answers
897 views

The Fibonacci sequence modulo $5^n$

Let $(F_k)_{k=0}^\infty$ be the classical Fibonacci sequence, defined by the recursive formula $F_{k+1}=F_k+F_{k-1}$ where $F_0=0$ and $F_1=1$. For every $n\in\mathbb N$ let $\pi(n)$ be the smallest ...
Taras Banakh's user avatar
  • 40.8k
8 votes
1 answer
308 views

Possible small mistake in Bilu-Hanrot-Voutier paper on primitive divisors of Lehmer sequences (?)

I think that I might have spotted I small mistake (a missing $5$-defective Lehmer pair) in the classification of terms of Lehmer sequences without primitive divisors given in: 1 Bilu, Hanrot, and ...
Seee's user avatar
  • 65
6 votes
0 answers
108 views

Equivalence of primes based on the partition of their Pisano periods

The period of Fibonacci numbers modulo $m$ is called Pisano period and its length is denoted as $\pi(m)$. Define the Pisano partition of $m$ as the set partition of the indices $\{0,1,\dotsc,\pi(m)-1\}...
Max Alekseyev's user avatar
4 votes
1 answer
210 views

Why do convoluted convolved Fibonacci numbers pop up from this triangle?

Start with this triangle (OEIS A118981). This triangle is simple to generate with the following recurrence relation (though $T(0,0)$ ends up different from the OEIS version): $$ T(0,0) = 2;T(1,0) = 1;...
Mitch's user avatar
  • 195
4 votes
0 answers
136 views

The smallest sequence without differences among Fibonacci numbers

Given a subset $\mathcal S\subset \mathbb N\setminus\{0\}$ of (strictly) positive integers, we can consider subsets $A$ of $\mathbb N$ (or $\mathbb Z$) with no differences in $\mathcal S$. Examples: ...
Roland Bacher's user avatar
4 votes
0 answers
162 views

Binary iterations, Fibonacci numbers and permutation of natural numbers

Let $\operatorname{wt}(n)$ be A000120, i.e. the number of $1$'s in binary expansion of $n$ (or the binary weight of $n$). Also let's consider $$\ell(n)=\left\lfloor\log_{2} n\right\rfloor$$ and $$T(n,...
Notamathematician's user avatar
3 votes
1 answer
1k views

Why doesn't the number of ones in the binary representation of Fibonacci numbers grow linearly? [closed]

I am a third-year computer science student. I am interested, why doesn't the number of ones in the binary representation of Fibonacci numbers grow linearly? I would expect it to grow linearly all the ...
FlatAssembler's user avatar
3 votes
1 answer
183 views

Proof of an unknown source Fibonacci identity with double modulo

Many years ago, I saw the following Fibonacci identity from somewhere online, without proof: Let usual $F(n)$ be Fibonacci numbers with $F(0) = 0, F(1) = 1$, then we have $$F(n) = \left(p ^ {n + 1} \...
Voile's user avatar
  • 131
3 votes
1 answer
135 views

Golden ratio base

Let $\phi$ be the golden ratio and look at real numbers as expansions in digits from base $\phi + 1$. Has this base been considered or studied anywhere? Note that integers in this base are palindromes ...
Maarten Havinga's user avatar
3 votes
0 answers
120 views

Reference for formula expressing products of two Fibonacci numbers in Zeckendorf-basis

It is well-known folklore that every natural integer has a unique Zeckendorf expansion as a sum over a finite set of Fibonacci numbers containing no pair of consecutive Fibonacci numbers. It is easy ...
Roland Bacher's user avatar
3 votes
0 answers
229 views

Is there a closed form of $ \displaystyle \sum_{k=0}^{\infty}{\frac{\phi^{xk}}{k!_F}}$

where $\phi = \frac{1+\sqrt{5}}{2}$ and $k!_F$ is the fibonorial of $k$, or the product of the first $k$ Fibonacci numbers? My hunch is that, this can be represented as a function in terms of the ...
Michael Smith's user avatar
2 votes
1 answer
186 views

Is this case of a generalised partition equivalent to Fibonacci numbers?

Let $k=m+\sum^{m+1}_{j=1} a_j$ such that $a,m,k\in\mathbb{N}$ and $a_1$ or $a_{m+1}\geq 0$ with all other $a\geq1$. Note that we assume natural numbers start from $0$ and we have the restriction that $...
UNOwen's user avatar
  • 79
2 votes
0 answers
81 views

Splitting natural numbers into subsets with sums equal to A066258

Let $F(n)$ be A000045 i.e. Fibonacci numbers. Here $$ F(n) = F(n-1) + F(n-2), \\ F(0) = 0, F(1) = 1 $$ Let $a(n)$ be A066258 i.e. $$ a(n) = F(n)^2F(n+1) $$ Let $b(n)$ be A345253 i.e. maximal ...
Notamathematician's user avatar
2 votes
0 answers
261 views

Conjecture about primes and Fibonacci numbers

I posted this conjecture on math.stackexchange, but I received no answer proving or disproving it: if $ m > 4 $ is a positive integer not divisible by $ 2 $ or $ 3 $, it's ever possible to find a ...
user967210's user avatar
2 votes
0 answers
192 views

My Fibonacci Formula (with combinatorics) [closed]

I'm a high school student, and was playing around with pascals triangle. and ended up taking (weird) diagonals. And I saw Fibonacci numbers, from the sum of the diagonals. Pascall's triangle is just ...
Josh's user avatar
  • 21
2 votes
0 answers
111 views

Can all (inverse) trigonometric functions with periodic iterates be characterized?

I wonder whether all (composites of) trigonometric and inverse trigonometric functions with periodic functional iterations can be found. In order to specify what I mean by that, let's introduce some ...
Max Muller's user avatar
  • 4,485
1 vote
1 answer
151 views

Fibonacci with seeds, modulo $n$

Let $n\in\mathbb{N}$ be an integer with $n>1$. For $x_0, x_1 \in \mathbb{Z}/n\mathbb{Z}$ we define the map $\text{fib}_{n, x_0, x_1}: \mathbb{N} \to \mathbb{Z}/n\mathbb{Z}$ by $0 \mapsto x_0, 1 \...
Dominic van der Zypen's user avatar
1 vote
1 answer
155 views

Explicit formula for Fibonacci numbers; compositions of $n$

A Fibonacci-type sequence is a sequence with two seed-values, $F_1$ and $F_2$, and which, for all $n>2$, abides by the recurrence relation $F_n = F_{n-1} + F_{n-2}$. If $F_1 = F_2 = s$, then the $n$...
user1113719's user avatar
1 vote
1 answer
196 views

Tiling a square with similar non-congruent rectangles. What is the aspect ratio of the rectangles as n grows large?

I recently saw a question here on mathoverflow: «For what n and t can a square be partitioned into n similar rectangles in t congruence classes?», where Joseph Gordon gave a proof that, indeed, a ...
Arne Erikson's user avatar
1 vote
0 answers
115 views

On a Fibonacci and binary

Let F(n) be A000045 i.e. Fibonacci numbers. Here $$ F(n) = F(n-1) + F(n-2), \\ F(0) = 0, F(1) = 1 $$ Let $$ \ell(n) = \left\lfloor\log_2 n\right\rfloor $$ Let $$ T(n, k) = \left\lfloor\frac{n}{2^k}\...
Notamathematician's user avatar
1 vote
0 answers
71 views

Slightly modified program for the A345253 such that specific partial sums equal A066258

Let $F(n)$ be A000045 i.e. Fibonacci numbers. Here $$ F(n) = F(n-1) + F(n-2), \\ F(0) = 0, F(1) = 1 $$ Let $a(n)$ be A345253 i.e. maximal Fibonacci tree: arrangement of the positive integers as ...
Notamathematician's user avatar
1 vote
0 answers
68 views

Recurrences (based on Fibonacci numbers) for the first differences of numbers filtred by equality of binary functions

First we need to set some binary functions: Let $$\ell(n)=\left\lfloor\log_2 n\right\rfloor$$ Let $\operatorname{wt}(n)$ be A000120, i.e., $1$'s-counting sequence: number of $1$'s in binary expansion ...
Notamathematician's user avatar
0 votes
1 answer
195 views

Density of "Fibonacci friends"

Let $F$ be the set of all integers $n>1$ such that in the Fibonacci sequence modulo $n$, the value $0$ occurs infinitely often. What is the value of $\lim\sup_{n\to\infty}\frac{|F\cap\{0,\ldots,n\}|...
Dominic van der Zypen's user avatar
0 votes
1 answer
186 views

Fibonacci and product polynomials

The motivation for my current question arises from this MO post by R. Stanley. Caveat. There's a slight alteration. With the convention $F_1=F_2=1$ for the Fibonacci numbers, define the polynomials $...
T. Amdeberhan's user avatar
0 votes
0 answers
53 views

Stolarsky representation from Zeckendorf representation with some pairs of bits inverted

Let $a(n)$ be A200714 i.e. Stolarsky representation interpreted as binary to decimal integers. Let $b(n)$ be A003714 i.e. Fibbinary numbers (Zeckendorf representation interpreted as binary to decimal ...
Notamathematician's user avatar
0 votes
0 answers
77 views

Constructing a pair of complementary sequences with the perfect differences

Let $F_n$ be A000045, i.e. Fibonacci numbers. Here $$ F_n = F_{n-1} + F_{n-2}, \\ F_0 = 0, F_1 = 1 $$ Let $g(n,m)$ be A257961. Here $$ g(n, m) = mF_{n-1} \operatorname{mod} F_n $$ Let $$ \varphi=\...
Notamathematician's user avatar
0 votes
0 answers
133 views

Chains in tilings with the aperiodic monotile

This is starting with any given infinite tiling of the plane by the aperiodic "hat" monotile, where chains of similarly oriented tiles are colored as in Figure 2.2 on p. 10 in the original ...
Wolfgang's user avatar
  • 13.2k
0 votes
0 answers
87 views

Avoiding the Fibonacci numbers

For given positive integers $a$ and $b$, let $(a,b)$ be "special" if $an+b$ is not a Fibonacci number for every positive integer $n$. For instance, $(8,4)$ and $(8,6)$ are special. There are ...
Ilhee Kim's user avatar
  • 248
0 votes
0 answers
196 views

What are the hidden assumptions behind Harvey Friedman's claim, CSR?

I'm doing some archeology and trying to understand a claim. As summed up by David Roberts, on the FOM list in 2011: Let the statement "every infinite sequence of rationals in [0,1] has an ...
Corbin's user avatar
  • 424
0 votes
0 answers
98 views

Requesting proof of closed form of sum involving Fibonacci and Lucas numbers

$$ \sum_{n=0}^{k+1}\frac{3F_{n+1}-L_{n+1}}{2n!}\frac{(k+1)!}{(k-n+1)!}x^{k-n+1}=(\varphi+x)^k\left(\frac{\sqrt{5}}{5}-\frac{\sqrt{5}-5}{10}x\right)+(\psi+x)^k\left(\frac{\sqrt{5}+5}{10}x-\frac{\sqrt{5}...
Michael Smith's user avatar
-1 votes
1 answer
189 views

A generalization of Vajda's identity [closed]

I discovered the identity below which generalizes Vajda's identity concerning Fibonacci Numbers. The identity states that: if $F_r$ is the rth Fibonacci number, then $$F_{n+i+x-z}F_{n+j+y+z}-F_{n+x+y-...
Shuaib Lateef's user avatar