80
votes
Accepted
Fibonacci series captures Euler $e=2.718\dots$
It follows from the identity
$$F_{n+k} = \sum_{j=0}^k {k \choose j} F_{n-j}$$
which is obtained by applying the standard recurrence $k$ times to the left side, each time splitting up each term ...
- 148k
41
votes
Accepted
Why doesn't the number of ones in the binary representation of Fibonacci numbers grow linearly?
You are hitting overflow with 32 bit "integers" at the point where things stop off in your calculations. In other words, your graph stops being accurate because you are using machine numeric ...
- 5,827
31
votes
Fibonacci series captures Euler $e=2.718\dots$
Mathematica tells me it's a consequence of the two series (distinguished by $\pm$):
$$\sum_{k=0}^\infty\frac{F_{n\pm k}}{k!}=\frac{e^{\sqrt{5}} \phi^n-(1-\phi)^n}{\sqrt{5}\, \exp(\phi^{\mp 1})},$$
...
- 188k
22
votes
Fibonacci series captures Euler $e=2.718\dots$
More generally,
$$\sum_{k=0}^\infty F_{n+k} \frac{x^k}{k!} = e^x\sum_{k=0}^\infty F_{n-k}\frac{x^k}{k!},\tag{1}$$
which is equivalent to Will Sawin's identity.
Similarly,
$$e^x\sum_{k=0}^\infty F_{n+k}...
- 17k
21
votes
Accepted
Limit involving the fractional part and the Fibonacci numbers
The statement is not correct. The correct statement is:
$$\lim_{n\rightarrow\infty}\frac{1}{2n}\sum_{k=1}^{2n}\left\{ \frac{F(2n)}{F(k)}\right\}=\frac{3\log 2}{4}.$$
That is, the limit is $\approx 0....
- 105k
16
votes
Accepted
Non-enumerative proof that, in average, less than 50% of tiles in domino tiling of 2-by-n rectangle are vertical?
Here is at least a heuristic argument for why we should expect fewer vertical dominoes than horizontal dominoes. As we increase the length of the strip (to the right, say), let us think about how the ...
- 82.6k
14
votes
On the finite sum of reciprocal Fibonacci sequences
Let me sketch a proof that this identity holds for big enough $n$. In fact, we can show that
$$\left(\sum_{k = n}^{2n} \frac{1}{F_{2k}}\right)^{-1} = F_{2n-1} + \frac{1}{\varphi \sqrt{5}} + o(1),$$
...
- 6,476
9
votes
Accepted
The Fibonacci sequence modulo $5^n$
I claim that for even $n\in \{0,2,4,\ldots, 4\cdot 5^n-2\}$ each remainder of $F_n$ modulo $5^n$ is realized at most twice (thus exactly twice), and the same for odd $n\in \{1,3,5,\ldots, 4\cdot 5^n-1\...
- 109k
9
votes
Accepted
Possible small mistake in Bilu-Hanrot-Voutier paper on primitive divisors of Lehmer sequences (?)
Yes, there are some omissions in the lists in the original BHV article. I think all of them were fixed by Mourad Abouzaid
Mourad Abouzaid, Les nombres de Lucas et Lehmer sans diviseur primitif, J. ...
- 1,294
9
votes
Accepted
On the finite sum of reciprocal Fibonacci sequences
We need to prove, equivalently
$$\frac1{F_{2n-1}+1}<\sum_{k=n}^{2n}\frac1{F_{2k}}\le \frac1{F_{2n-1}}, $$
that is, by the above expression for $F_{k}$, since $\beta=-\alpha^{-1}$, we need to check ...
- 60.5k
9
votes
Accepted
A rational function related to Fibonacci numbers
$\let\eps\varepsilon$ Here is an answer to the original question, for usual Fibonacci numbers. I apologise for changing the notation; the standard arguments for $f$ will be $f(n,k)$.
1. Recall that $...
- 23.7k
9
votes
Accepted
Lucas number multiples of Fibonacci pairs
The first identity can be derived as the follows. From the identity
$$\displaystyle F_{m+k} + (-1)^k F_{m-k} = L_k F_m,$$
with the choice $m = 2n+2, k = 2n+1$ we have
$$\displaystyle F_{4n+3} - F_1 = ...
- 26.9k
7
votes
Non-enumerative proof that, in average, less than 50% of tiles in domino tiling of 2-by-n rectangle are vertical?
Here is a proof without computing the fraction.
For each $n \in \mathbb{N}$, let $t_n$ be the number of tilings of the $2 \times n$ rectangle by dominos, and let $v_n$ and $h_n$ be the total number of ...
- 32.1k
6
votes
Accepted
Fibonacci with seeds, modulo $n$
We can completely classify modulo which $n$ there is a surjective sequence. Indeed, I claim that $\text{fib}_{n, x_0, x_1}$ is surjective for some seed values $x_0,x_1$ iff the usual Fibonacci ...
- 28.2k
6
votes
Fibonacci series captures Euler $e=2.718\dots$
The identity given is simpler than it seems. Suppose
that $z$ is any nonzero complex number. Then
$$ \sum_{k=0}^\infty \frac{z^{n+k}}{k!} =
z^n \sum_{k=0}^\infty \frac{z^k}{k!} = e^z z^n, \quad
\sum_{...
- 2,784
5
votes
Fibonacci series captures Euler $e=2.718\dots$
I set out intending to post this as a comment, but perhaps it sits better here. The method that follows suggests a general formula to produce such relationships from second order linear recurrences. ...
- 233
5
votes
Accepted
Number of coefficients equal to $k$ in certain "Fibonacci polynomials"
I will use the set up of my answer to a previous question about "Fibonacci polynomials".
The key observation is that the coefficient of $x^m$ in $P(x)$ equals the number of "unrollings&...
- 34.3k
5
votes
Non-enumerative proof that, in average, less than 50% of tiles in domino tiling of 2-by-n rectangle are vertical?
Essentially also a reformulation:
Tilings of $n\times 2$ with vertical and horizontal dominos are in bijection with Zeckendorf expansions of integers in $[0,F_{n+1}-1]$ (perhaps up to a small shift of ...
- 17.9k
4
votes
Accepted
Why do convoluted convolved Fibonacci numbers pop up from this triangle?
We have $$T(n,k) = [x^ny^{n-k}]\ \frac{2 - (1+y)x}{1-(1+y)x-x^2}=[y^{n-k}]\ L_n(1+y),$$
where $L_n$ is the $n$-th Lucas polynomial.
For $k<n$, we have an explicit formula:
\begin{split}
T(n,k) &...
- 34.3k
4
votes
Non-enumerative proof that, in average, less than 50% of tiles in domino tiling of 2-by-n rectangle are vertical?
Could some argument along these lines be made? (I admit that this argument is itself seriously lacking.)
Let $p$ be the probability that a random tile among all domino tilings of a $2\times n$ ...
- 2,339
4
votes
Number of coefficients equal to $k$ in certain "Fibonacci polynomials"
This is just a `formulas-free' version of the proof that the numbers $\nu_k(n)$ are indeed linear in $n$, for a fixed $k$ and large enough $n\geq n_0(k)$. The following lemma is the same as Max ...
- 23.7k
4
votes
On the finite sum of reciprocal Fibonacci sequences
For further discussion on such sums (the case of infinite series) and generalizations can be found in this paper starting on page 12 and references therein:
https://users.math.msu.edu/users/bsagan/...
- 43.2k
4
votes
Accepted
Fibonacci and product polynomials
Question 2 follows from Theorem 6.1 of arXiv:2101.02131. (In this reference, I consider $\prod_{i=1}^n(1+x^{F_{i+1}})$ rather than $\prod_{i=1}^n(1+x^{F_i})$, but the proof still works.) The result ...
- 50.8k
4
votes
A generalization of Vajda's identity
Slight correction to Random's substitutions (community wiki since it's not my contribution):
define:
$${n_0}=n+x+y-k,\;\;{i_0}=i+k-y-z,\;\;{j_0}=j+k-x+z$$
substitute in Vajda's identity
$$F_{n_0+i_0}...
4
votes
The Fibonacci sequence modulo $5^n$
Fedor Petrov gave a satisfactory answer, but here is another one, based on a linear algebraic reasoning.
The following is a general fact, which proof is left as an exercise.
Lemma: Let $C$ be a $\...
- 11.6k
4
votes
Is 8 the largest cube in the Fibonacci sequence?
In Siegel's article Zum Beweise des Starkschen Satzes. Inventiones mathematicae (1968), Siegel reduces the class number one problem for imaginary quadratic fields to the determination of Fibonacci ...
- 2,375
4
votes
Accepted
Negated Fibonacci and the floor function
We have
$$F_{-n}=\frac{(-a_-)^n-(-a_+)^n}{\sqrt5} \tag{1}\label{1}$$
with
$$a_\pm:=\frac{1\pm\sqrt5}2.$$
We also have the easy formula for $\sum_{j=j_1}^{j_2}(p+qj)x^j$, which yields
$$\sum_{i=1}^{n-1}...
- 128k
3
votes
Nontrivial question about Fibonacci numbers?
Parametrization of the equation $x^2-xy-y^2=\pm1$. Next step is a 2-dmensional isolation theorem, see Cassels, J. W. S. An introduction to the geometry of numbers, sec. II. 4. Indefinite quadratic ...
3
votes
Complexity of a Fibonacci numbers discrete log variation
The Binet formula for Fibonacci numbers is
$$F_n = \frac{\phi^n - (-\phi)^{-n}}{\phi - (-\phi)^{-1}},\qquad\text{where}\ \phi:=\frac{1+\sqrt{5}}2.$$
Then the congruence $F_n\equiv k\pmod{m}$ reduces ...
- 34.3k
Only top scored, non community-wiki answers of a minimum length are eligible