Questions tagged [fibonacci-numbers]
Questions on the Fibonacci numbers, a special sequence of integers that satisfy the recurrence $F_n=F_{n-1}+F_{n-2}$ with the initial conditions $F_0=0$ and $F_1=1$.
2,194
questions
3
votes
2
answers
604
views
Prove that if $F_n$ is highly abundant, then so is $n$.
Define $F_n$ to be the $n$th Fibonacci number, define $\sigma(n)$ to be the sum of the divisors of $n$, and call $n$ highly abundant if and only if $\sigma(n)>\sigma(m) \hspace{3mm} \forall m<n$....
- 810
3
votes
1
answer
129
views
A Generalized Fibonacci sequence
I have the following recurrence $$u_{n+1}=u_{n}+a^{N-n}u_{n-1}\quad n\ge 1$$ where $$N\ge 1,\quad u_1=u_0=1,\quad 0< a\le 1$$ I want to find out $u_N$.
My Try: For $a=1$ this is just the Fibonacci ...
- 16.3k
3
votes
1
answer
487
views
Another Bijective proof for Fibonacci Identities
I'm going through a past exam, and this question popped up:
Prove:
$3P_n = P_{n-2} + P_{n+2},\,n>2$
Where $\tilde{P}_j = \{\textrm{monomer-dimer pavings on a } 1\times j \textrm{ board}\}$ and $|...
- 405
3
votes
2
answers
144
views
How many ways to reach $1$ from $n$ by doing $/13$ or $-7$?
How many ways to reach $1$ from $n$ by doing $/13$ or $-7$ ?
(i.e., where $n$ is the starting value (positive integer) and $/13$ means division by $13$ and $-7$ means subtracting 7)?
Let the number ...
- 16k
3
votes
1
answer
4k
views
Understanding the base step in inductive proof that Lucas number are the sum of consecutive Fibonacci numbers.
Define the Lucas numbers to be
$$l_n = l_{n-1} + l_{n-2} $$
if $n \ge 2$ with initial conditions $l_0 = 2$ and $l_1= 1$.
I "proved" by induction that $l_n = f_{n-1} + f_{n+1}$ for $n \ge 1$ (by $...
- 31
3
votes
1
answer
178
views
On the Finite Sum of Reciprocal Fibonacci Sequences
I want to check if $$\left \lfloor \left( \sum_{k=n}^{2n}{\dfrac{1}{F_{2k}}} \right) ^{-1} \right\rfloor =F_{2n-1}~~(n\ge 3)\qquad(*)$$ where $\lfloor x \rfloor$ is a floor function.
Fibonacci ...
- 1,135
3
votes
1
answer
124
views
prove a fibonomial identity
For all $n\ge 1$, why do there exist integers $a_{i,n}$, $0\le i\le n+1$, not all zero, so that $$a_{0,n} (F_k)^n + a_{1,n} (F_{k-1})^n +\cdots + a_{n,n} (F_{k-n})^n+a_{n+1,n}(F_{k-n-1})^n = 0$$ for ...
- 1,809
3
votes
1
answer
144
views
Combinatorially proving $F_{n} = \sum_{i=0}^{\left\lfloor n/2 \right\rfloor}\binom{n-i}{i}$, where $F_n$ is the $n$-th Fibonacci number [duplicate]
Prove the following combinatorially:
$$F_{n} = \sum_{i=0}^{\left\lfloor n/2 \right\rfloor}\binom{n-i}{i}$$
So, I know that the Fibonacci number counts the number of ways to cover a $1 \times n$ ...
user1154312
3
votes
1
answer
217
views
Question on calculating a Fibonacci Number using Matrix Exponentiation
We know that $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^k = \begin{pmatrix}F_{k + 1} & F_k \\ F_k & F_{k - 1}\end{pmatrix},$ of which there is a simple proof by induction. However, ...
- 1,122
3
votes
1
answer
337
views
Evaluating the sum $\sum_{n=1}^{\infty}\frac{1}{F_n}$
Let $F_n$ be the $n^\text{th}$ Fibonacci number. I wanted to calculate
$$\sum_{n\ge1}\frac{1}{F_n}$$
I simplified it to
$$\sqrt{5}\sum_{n\ge1}\frac{1}{\varphi^n-\phi^n}$$
But this didn't seem to help....
user840532
3
votes
1
answer
674
views
Two elements in the set differ by 3 or more
Call a set of integers sparse if any two elements in the set differ by at least 3. Find the number of sparse subsets of $\{1, 2, 3, \dots, 12\}.$ (Both $\emptyset$ and one-element sets are sparse, to ...
- 1,851
3
votes
2
answers
176
views
proof : even nth Fibonacci number using Mathematical Induction
I know that the sequence $f$ of even Fibonacci numbers has the recurrence relation
$$f(n) = 4f(n-1) + f(n-2) \quad \text{for n } \ge 2$$
How to prove that this formula is true using Induction ?
3
votes
1
answer
108
views
Identity about Fibonacci numbers
If I note $(F_N)_N = \{0,1,1,2,3,5,...\}$ the Fibonacci sequence, I have proved the identity
$$ \forall N \geqslant 0,\,F_{N}^2 = F_{N} + 2\,\sum_{k=0}^{N-3} F_{k+1}\,F_{k+2}\,F_{N-k-2}. $$
This ...
- 117
3
votes
1
answer
2k
views
Closed form of the Fibonacci sequence: solving using the characteristic root method
Here is the official theorem I'll use:
Since the Fibonacci sequence is defined as $F_n=F_{n-1}+F_{n-2}$, we solve the equation $x^2-x-1=0$ to find that $r_1 = \frac{1+\sqrt 5}{2}$ and $r_2 = \frac{1-...
- 2,331
3
votes
1
answer
72
views
Prove for all $n\in \mathbb{N}$ that $\sum_{i=0}^{n} i\cdot F_{2i} = (n+1)F_{2n + 1} - F_{2n + 2}$.
$F_n$ denotes the Fibonacci sequence where $n$ is the term of the Fibonacci number in the sequence. ($F_0=0$, $F_1=1$, $F_2=1$, $F_3=2$, $F_4=3$, ... $F_n=F_{n-1} + F_{n-2}$)
I want to prove this ...
- 155
3
votes
4
answers
104
views
If $2 \mid F_n$, then $4 \mid F_{n+1}^2-F_{n-1}^2$, where $F_n$ is $n$-th Fibonacci number
I want to show that
If $2 \mid F_n$, then $4 \mid F_{n+1}^2-F_{n-1}^2$
If $3 \mid F_n$, then $9 \mid F_{n+1}^3-F_{n-1}^3$
where $F_n$ is the $n$-th Fibonacci number.
I have tried ...
- 1,460
3
votes
1
answer
277
views
Fibonacci ratio - inequality proof: $\frac{f_{2k}}{f_{2k-1}} < \frac{f_{2k+1}}{f_{2k}}$
For all $n \in \mathbb{N_{>0}}$, let $$\phi_{n} = \frac{f_{n+1}}{f_{n}}$$
the ratio between two successive Fibonacci numbers.
I've already shown using Cassini's Identity
that $$ \phi_{n} = \phi_{n-...
- 160
3
votes
1
answer
109
views
Showing the equivalence: $\frac{\varphi^{n}(1+\frac{1}{\varphi})-\psi^{n}(1+\frac{1}{\psi})}{\sqrt{5}}=\frac{\varphi^{n+1}-\psi^{n+1}}{\sqrt{5}}$
For a school project, I want to explain the proof, that the Moivre/Binet formula for calculating the $n$-th number of the Fibonacci-Sequence works. I got an inductive proof from the German Wikipedia ...
- 31
3
votes
1
answer
407
views
Probability of combinations of beads on cut necklaces (mass spectrometry physics problem)
I have a math problem related to peptide mass spectrometry which I am unable to solve myself. Hopefully some of you guys will find it to be an interesting challenge. I have expressed it below in terms ...
3
votes
1
answer
366
views
Second order non linear recurrence relation
$$ G_n= G_{n-1}+ (\frac{3}{4})^n G_{n-2}, \quad with \quad G_0=1,G_1=1 $$
I am trying to find the limit $ \lim\limits_{n \rightarrow +\infty} G_n$ which converges to $ 5.457177946$.
Or to find an ...
- 45
3
votes
1
answer
107
views
Find $n \in \mathbb N$ such that $F_{n-1} \cdot x^2 - F_n \cdot y ^ 2 = (- 1) ^ n$ has a solution in positive integers $x, y$?
Let $\{F_n\} -$ Fibonacci sequence: $F_1=F_2=1, F_{n+1}=F_n+F_{n-1}, n\ge2$. Find $n \in \mathbb N$ such that
$$F_{n-1} \cdot x^2 - F_n \cdot y ^ 2 = (- 1) ^ n$$ has a solution in positive ...
- 17.9k
3
votes
1
answer
166
views
A generalization of a divisibility relation for Fibonacci numbers
Given $a,b\in\mathbb Z^+$, and let $F_{a,b}:\mathbb N\to\mathbb N$ be a function such that $F_{a,b}(0)=0$, $F_{a,b}(1)=1$ and $F_{a,b}(n+1)=a\cdot F_{a,b}(n)+b\cdot F_{a,b}(n-1)$. $F_{1,1}$ correspond ...
- 13.8k
3
votes
1
answer
835
views
How can I solve this Fibonacci sequence exercise?
Define $\ a_n=\frac{F_{n+1}}{F_n},n>1$ where $F_n$ is a member of a Fibonacci sequence.
a) Write the first 10 terms of $a_n$
b) Show that $a_n= \frac1{a_n-1}$
I was able to solve the a) ...
- 33
3
votes
1
answer
147
views
Show that $\sum_{k=1}^{\infty}\frac{F_{2^{k-1}}}{L_{2^k}-2}=\frac{15-\sqrt{5}}{10}$
Show that$$\sum_{k=1}^{\infty}\frac{F_{2^{k-1}}}{L_{2^k}-2}=\frac{15-\sqrt{5}}{10},$$
where $F_n$ is a Fibonacci number and $L_n$ is a Lucas number.$^1$
Motivation: For example, when calculating ...
- 8,786
3
votes
1
answer
2k
views
Find the sum of Fibonacci Series
I have given a Set A i have to find the sum of Fibonacci Sum of All the Subset of A
...
- 51
3
votes
1
answer
212
views
Fibonacci and Lucas numbers congruence relation?
The wikipedia page for Lucas Numbers seems to suggest that if $F_n ≥ 5$ is a Fibonacci number then no Lucas number is divisible by $F_n$. Here is the link.
However, the page does not give any ...
- 332
3
votes
1
answer
146
views
Prove equality of Fibonacci sequence
Let $u(n)$ — the Fibonacci sequence. Prove that
$$u(1)^3+...+u(n)^3=\frac{ 1 }{ 10 } \left[ u(3n+2)+(-1)^{n+1}6u(n-1)+5 \right].$$
I suppose we need prove that equality by iduction in $n$. It's ...
- 955
3
votes
2
answers
2k
views
Proving that for Fibonacci numbers $a_n \lt (\frac {1 + \sqrt 5} 2)^n$ for $n \ge 1$
I'd like to prove that for Fibonacci numbers $a_n \lt \left(\frac {1 + \sqrt 5} 2\right)^n$ for $n \ge 1$. I suppose it needs induction so, after verifying the trivial case $n=1$, the inductive step ...
- 135
3
votes
1
answer
304
views
Sum of Power of Two Fibonacci reciprocals [duplicate]
Evaluate $$\sum_{k=0}^{\infty} \frac{1}{F_{2^n}} \;.$$
I'm thinking of using a relation from a term to another.
user198454
3
votes
1
answer
186
views
Hankel determinant involving Fibonacci numbers
Let $F_n$ denote the $n$-th Fibonacci number, with $F_1 = F_2 = 1$.
Denote by $M\left(n\right)$ the $n \times n$ Hankel matrix with $\left(i,j\right)$-th entry $F_{i+j-1}^{n-1}$,
where $i$ and $j$ ...
- 2,437
3
votes
3
answers
101
views
Uniform Convergence for a sequence of functions defined by recurrence
The following is a problem that I can't solve, and I need some tips:
Problem:
For $x>-1$, define $f_1(x) = x,\ f_{n+1}=\dfrac{1}{1+f_n(x)}$. Find the limit function $f(x)$ and all the subsets of $...
- 2,238
3
votes
1
answer
679
views
Are the Fibonacci numbers' prevalence in nature due to confirmation bias?
The Fibonacci numbers are frequently found in nature, such as in the petals of flowers or the shape of pinecones.
But are the numbers actually any more prevalent than other numbers? Could it all be ...
- 283
3
votes
1
answer
625
views
Fibonacci Numbers in Nature
Supposedly the Fibonacci sequence appears naturally in nature, and my question is how, where and I guess why?
I read that one way this is so is that it models the population of honey bees under ideal ...
- 2,901
3
votes
1
answer
510
views
Monotonicity of the sequence $ ( F_n^{\frac{1}{n}} ) $, where $ ( F_n ) $ is the Fibonacci sequence
Let $ F_n = F_{n-1} + F_{n-2} $ with $ F_0 = 1 $, $ F_1 = 1 $ (the Fibonacci sequence). I would like to know whether $ F_n^{\frac{1}{n}} $ is monotonically increasing in $ n $. It is not difficult to ...
- 31
3
votes
1
answer
100
views
Prove that $F_{x^{n+1}} \sim 5^{\frac{x-1}{2}}F_{x^n}^x \forall x,n \geq 1$, holding either variable constant while the other goes to infinity
I noticed from looking at the prime factorizations of some Fibonacci numbers that all those with an index equal to a power of 5 divided that power of five, a property not guaranteed by the strong ...
- 810
3
votes
1
answer
340
views
Solve a recursion using generating functions: $F_n+F_{n-1}+⋯+F_0=3^n , n\geq0$?
Given the recursive equation :
$$F_n+F_{n-1}+⋯+F_0=3^n , n\geq0$$
A fast solution that I can think of is placing $n-1$ instead of $n$ , and then we'll get :
$$F_{n-1}+F_{n-2}+⋯+F_0=3^{n-1} $$
...
- 2,379
3
votes
1
answer
297
views
Have I correctly derived an inverse to the Binet formula?
I was interested by another user's question on finding such an inverse and in particular noted Will Orrick's comment in the best answer that one can square both sides to obtain a quartic.I thought I'd ...
- 1,682
3
votes
2
answers
153
views
Non-isomorphic combinatorial classes with growth rate equal to the golden ratio?
In a couple of weeks, I'm giving a talk about the growth rates of some combinatorial classes.
In the introduction, I thought I'd present the class of tilings of a $n\!\times\!2$ strip with dominos, ...
- 5,862
3
votes
1
answer
70
views
Induction Proof for the Sum of the First n Fibonacci Numbers
I'm trying to prove that there exists a formula for the sum of the first n Fibonacci numbers, using induction.
$$\sum_{i=1}^{n} F_i$$
For my class, we have denoted the recursive definition of the ...
- 123
3
votes
0
answers
69
views
Linear clustering when plotting Pisano periods
Recently I saw a video on YouTube where the Fibonacci numbers were studied and around minute 4:20 appears a graph showing the period against the modulus. Something that caught my attention is that ...
- 31
3
votes
0
answers
89
views
On primes that are a sum of two Fibonacci numbers
This question is about primes that are sums of two Fibonacci numbers.
$$
\begin{align}
2 &= 1 + 1 \\
3 &= 1 + 2 \\
5 &= 2 + 3 \\
7 &= 2 + 5 \\
11 &= 3 + 8 \\
13 &= 5 + 8 \\
&...
- 3,311
3
votes
0
answers
86
views
Subset sum problem with $F_m^2 F_n^2$ (Fibonacci square) weights
Suppose $$N = \sum_{i=1}^{k} \sum_{j=1}^{k} x_i \cdot y_j\cdot F_{c_i}^2 \cdot F_{c_j}^2 ; (x_i, y_j, c_i, c_j \in \mathbb{Z}, c_i, c_j \ge 1) \tag{1}$$ and $F_k$ is the $k$-th Fibonacci number. The ...
- 3,311
3
votes
0
answers
138
views
How can the Fibonacci numbers be extended to a Fibonacci number triangle?
A way to study a sequence is to apply a transformation to the
sequence. The transformations we want to consider are transformations
from 1-dim sequences to 2-dim sequences. We assume 1-dim sequences
...
- 885
3
votes
0
answers
105
views
A PigeonHole principle (combinatorics)problem using Fibonacci numbers [duplicate]
Define the sequence of Fibonacci numbers as: $F_1$ = $F_2$ = 1 and $F_n$ = $F_{n−1}$ + $F_{n−2}$ for every
n > 2. Prove that, for any positive integer $k$, there is a Fibonacci number ending with $...
- 178
3
votes
0
answers
57
views
Does the infinite double sum $ \sum_{m=1}^{\infty} \sum_{n=1}^{\infty} \dfrac{Fib(mn)}{Fib(m+2)^{2n}} $ converge, and if yes, to what?
Based on this video by Prof. Michael Penn, I was recently playing around with "geometric" summations involving the Fibonacci sequence, as in $$ \displaystyle \sum_{n=0}^{\infty} \frac{Fib(mn)...
- 257
3
votes
0
answers
65
views
How to solve this sum of a recurrence relation?
I've been given the recurrence relation $a_n = na_{n-1}+n^2a_{n-2}$ where $a_0 = 1$ and $a_1 = 1$.
I need to find $a_{1000}$.
My understanding is that this is very similar to the Fibonacci sequence. ...
3
votes
0
answers
136
views
Prove identity for the Fibonacci numbers by bijection
I was given the following to prove by using bijection:
$F_{n+2} + \sum^n_{k=2} 2^{n-k}F_{k-1} = 2^n$
I know that $F_{n+2}$ is the number of subsets of $[n]$ containing no $2$ consecutive elements, ...
- 115
3
votes
1
answer
119
views
A Fibonacci Number problem(please help me that 1 answer is mine)
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_{...
user665856
3
votes
1
answer
209
views
fibonacci and lucas numbers induction
I'm having trouble proving by induction that this following Fibonacci-Lucas equation
$$F_{2n+k} = F_n L_{n+k} + (-1)^n F_k \tag{*}$$
is true, given that
$$F_{2n} = F_nL_n$$
and
$$F_{2n+1} = ...
- 155
3
votes
0
answers
71
views
Question about periodicity in Fibonacci numbers
This is related to Pisano periods, that is, the periods of the Fibonacci numbers modulo $k=2, 3, \cdots$. I am studying the sequence $x(n+1)=\{b x(n)\}$ (here the brackets represent the fractional ...
- 3,605