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,083
questions
-5
votes
0
answers
35
views
Fibonacci propertie formula proof [closed]
I wanted to proof this Fibonacci formula
$f^2_{n+1}= 4f_nf_{n−1}+ f^2_{n−2}$
without using combinatorial interpretation or induction on n, but I still stuck with nothing much.
Can anyone, please, ...
7
votes
1
answer
147
views
Is every Nth Fibonacci number where N is a power of 5 or 12 divisible by N?
I was playing around with Fibonacci numbers divisible by their indexes (i.e. the $12$th Fibonacci number, $144$, is divisible by $12$) and found that this works when the index is a power of $5$ or $12$...
- 73
1
vote
1
answer
72
views
Similarity of Lifting the Exponent Lemma in Pell numbers
Pell number is a term of the sequence $\{P_n\}$ determined by a recurrence relation
$$P_{n+2}=2P_{n+1}+P_n, P_0=0, P_1=1.$$
Let $v_p(x)$ be the $p$-adic valuation of an integer $x$ (the number of ...
- 145
1
vote
1
answer
121
views
Finding the formula for the Fibonacci numbers using Generating Functions
I am trying to derive the formula for the Fibonacci sequence. Here is my work, I am making a mistake somewhere, but I can't seem to find where it is. My answer is almost correct but the the final ...
- 89
1
vote
0
answers
25
views
For which lowest value of $a$ and $b$ does their fibonacci series include a given number $n$? [closed]
Note: I am trying to get any useful insight into this type of questions, a general gist or mindset which would be helpful in dealing with question regarding fibonacci sequence. I am not currently ...
- 39
0
votes
0
answers
31
views
Bounding the "General Version" of the Fibonacci Sequence
I am working on the following problem:
Define $\{a_n\}$ where $a_0=0$, $a_1=1$, and $a_n=A\cdot a_{n-1}+B\cdot a_{n-2}$ for all $n\geq 2$ where $A,B\in\mathbb{R}$. Find a constant $M$ such that $a_n\...
- 89
1
vote
1
answer
76
views
how to prove that Fibonacci sequence is divergent [duplicate]
Fibonacci sequence is defined as follows $\{F_{n}\}_{n=0}^{\infty}$, where $F_{n+2}=F_{n+1}+F_{n}$. How to prove that this sequence is divergent?
I started with definition of limit goes to infinity, i....
- 11
3
votes
1
answer
78
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$ ...
- 75
2
votes
0
answers
54
views
Divisibility of Lucas+Fibonacci [duplicate]
I was playing around with the Fibonacci sequence and the Lucas sequence, and I noticed something.
It seems that for most $n\in\mathbb{N}$ where $n|(F_n+L_n)$, $n$ is prime and is congruent to 3 or 7 ...
- 121
0
votes
0
answers
68
views
What is the exact value of $\sum\limits_{n=1}^\infty \frac{1}{F_n}$? [duplicate]
What is the exact value of $\sum\limits_{n=1}^\infty \frac{1}{F_n}$? $F_n$ denotes the $n^{th}$ Fibonacci number.
Wolframalpha gave me this answer: $$\sum_{n=1}^{\infty}\frac{1}{F_n}\ =\frac{1}{4}\...
- 139
-2
votes
1
answer
69
views
A connection between Fibonacci numbers and the golden ratio
I'm very interested in studying number theory and I post an other conjecture between the golden ratio and Fibonacci numbers.
N.B: it is well known that is a link between the golden ratio and Fibonacci ...
- 77
3
votes
2
answers
46
views
Sets with out letters that are consecutive
If we have a set that is the alphabet, $\{a,b,..y, z\}$ then how many subsets exist that do not contain consecutive letters?
I figured out that a subset of size $1$ has $2$ elements, size $2$ has $3$ ...
- 105
0
votes
2
answers
84
views
I need help with a proof regarding Fibonacci sequence.
I have constructed a formula for the terms of the Fibonacci sequence for positive integer $n$. It is:
$$
\frac{a^{n}}{1+b^2}+\frac{b^n}{1+a^2}
$$
where $a=\frac{1+\sqrt{5}}{2}$, and $b=\frac{1-\sqrt{...
- 73
1
vote
1
answer
66
views
Why is $\phi^x=\underset{n\to\infty}{\lim} \frac{F_n}{F_{n-x}}$? [closed]
The function $F_n$ denotes the nth Fibonacci number and $\phi$ is the golden ratio $\frac{1+\sqrt{5}}{2}$. I found this while trying to create a fun math puzzle. Is there a name for this? Also, how do ...
- 139
2
votes
0
answers
83
views
Can $a^n+F_n$ be prime for every integer $a>1$?
I have the following conjecture :
Let $a>1$ be an integer. Then, there is a positive integer $n$ such that $a^n+F_n$ is prime , where $F_n$ denotes the $n$-th fibonacci number.
For $a\le 10^4$ , ...
- 80.6k
0
votes
1
answer
46
views
Fibonacci numbers in closed form using generating functions
I feel like I made a simple mistake along the way, hopefully I'm not approaching this in the wrong way in general.
Let $f_n=f_{n-1}+f_{n-2}$ for all $n\ge 2$ be our recursive definition of the ...
2
votes
2
answers
155
views
At most one representation as a sum of two fibonacci-numbers?
I wanted to start a project to find primes of the form $F_m+F_n$ with integers $m,n$ satisfying $1<m<n$ , where $F_n$ denotes the $n$ th fibonacci-number.
I wondered whether duplicate numbers ...
- 80.6k
0
votes
0
answers
33
views
Generalised algorithm to find generating function for any linear recurrance relation.
Problem:
Formally speaking lets say we have,
$ F_n = a_{k}F_{n-1} + a_{k-1}F_{n-2} + a_{k-2}F_{n-3} + \cdots + a_1F_{n-k} $
Base case being,
$F_0 = b_0\\F_1 = b_1\\
\cdots\\F_{k-1} = b_{k-1}$
We are ...
- 470
2
votes
2
answers
32
views
Order ideals of a fence
Let $F_n$ be the $n$-element fence, that is, $F_n=\{a_1, \ldots, a_n\}$ with
$$a_1>a_2<a_3>\cdots a_n$$
and no other elements related.
Here is the Wikipedia article about fences : https://en....
- 95
0
votes
1
answer
23
views
Prove $S(n) = S(f_{k}) + S(n-f_{k}) + n-f_{k}$
Problem:
Lets $Z(n)$ be the number of numbers of in Zeckendorf Representation of $n$
and Let
$ S(n) = \sum_{1}^n Z(i) $ and $f_{k}= k_{th}$ fibonacci number not greater than $n$
Prove $S(n) = S(f_{k})...
- 470
0
votes
0
answers
34
views
Prove : $S_n = S_{n - f_k} - S_{f_{k+1} - n - 3} + 2^{k-1}$
Problem:
Given a power series
$\prod (1+x^{f_i})$ where $f_i$ is the $i_{th}$ fibonacci number,
Prove that
$S_n = S_{n - f_k} - S_{f_{k+1} - n - 3} + 2^{k-1}$
$S_n =\sum_{i=0}^nc_i$ where $c_ix^i$ is $...
- 470
15
votes
1
answer
491
views
Conjecture about difference of Fibonacci numbers and primes
I'm curious to see if this conjecture is true: if $ m > 4 $ is a positive integer not divisible by $ 2 $ or $ 3 $, it's possible to find a positive integer $ n $ such that the difference of the $ 2 ...
- 409
4
votes
3
answers
121
views
Solve for all $x$ such that $x^3 = 2x + 1, x^4 = 3x + 2, x^5 = 5x + 3, x^6 = 8x +5 \cdots$
Question:
Solve for all $x$ such that $\begin{cases}&{x}^{3}=2x+1\\&{x}^{4}=3x+2\\&{x}^{5}=5x+3\\&{x}^{6}=8x+5\\&\vdots\end{cases}$.
My attempt:
I sum up everything.
$$\begin{...
- 1,158
1
vote
1
answer
53
views
What is the general continuous form of discrete generalization of Fibonacci golden ratios?
What is the general continuous form?
The general form for discrete numbers is:
$$
a_n = a_{n-1} + a_{n-2}
$$
$$
A = \lim_{n \to \infty} \biggl( \frac{a_n}{a_{n-1}} \biggr)
$$
$$a_0 = 1$$
$$a_1 = 1$$
...
- 73
0
votes
0
answers
72
views
3D logarithmic spiral using Fibonacci sequence
I would like to get an equation of a 3D logarithmic spiral using the Fibonacci sequence so I can use it in GeoGebra. I'm an artist, not a mathematician. This is beyond my understanding. Thank you.
1
vote
2
answers
95
views
Determining the even Fibonacci numbers.
There is another question regarding this topic in MSE (here) but this question (in my point of view) isn't answered fully correct. I will explain why.
The problem in question is to determine which ...
- 1,171
1
vote
0
answers
37
views
Deducing a Fibonacci number property. [duplicate]
Exercise. Show that, for all $n \in \mathbb N$, the following property holds:
$$ \sum_{k=0}^n \binom{n}{k}F_k = F_{2n}.$$
My solution. To show this, I procedeed by induction over $n$. For $n=1$, we ...
- 1,171
4
votes
1
answer
92
views
Primitive divisors of Fibonacci numbers
The well known Fibonacci sequence $F_{0} = 0, F_{1} = 1$ and, by recurrence law, $F_{n+1}:=F_{n} +F_{n-1}$ for all $n\geq 1$, has the following property (proved by Carmichael in 1913):
With the ...
- 215
0
votes
1
answer
45
views
Prefix code with word lengths equal to consecutive Fibonacci numbers
Is it possible to find a prefix code with word lengths equal to consecutive Fibonacci numbers?
The sequence of Fibonacci numbers is:
$$F_1=1,F_2=1,F_3=2,F_4=3,F_5=5,...$$
I think, I can use Kraft–...
- 50
5
votes
0
answers
111
views
Bijection Between $\mathbb{R}$ and $\mathbb{R}\setminus\{1\}$
I was looking for a way to establish the equinumerosity of $\mathbb{R}$ and $\mathbb{R}\setminus\{1\}.$ This is what I came up with:
Consider $f:\mathbb{R}\rightarrow\mathbb{R}\setminus\{1\}$ such ...
- 844
3
votes
1
answer
125
views
Time complexity of computing Fibonacci numbers using naive recursion
I'm trying to rigorously solve the Time Complexity $T(n)$ of the naive (no memoization) recursive algorithm that computes the Fibonacci numbers.
In other words I'm looking for $f(n):T(n)\in\Theta(f(n))...
- 238
1
vote
1
answer
74
views
Generating function of ordered odd partitions of $n$.
Let the number of ordered partitions of $n$ with odd parts be $f(n)$. Find the generating function $f(n)$ .
My try : For $n=1$ we have $f(1)=1$, for $n=2$, $f(2)=1$, for $n=3$, $f(3)=2$, for $n=4$, $...
user1137804
1
vote
1
answer
93
views
The least number of numbers the differences among which include Fibonacci numbers $F_2, F_3,\cdots, F_n$
The Fibonacci numbers $F_0,F_1,F_2,\ldots$ are defined inductively by $F_0=0$, $F_1=1$, and $F_{n+1} = F_n + F_{n−1}$ for $n\ge1$. Given an integer $n\ge2$, determine the smallest size of a set $S$ of ...
- 336
4
votes
2
answers
237
views
Inverse Fibonacci sequence
I was having fun with Fibonacci numbers, and I had the idea to consider the sequence
$
F_n=F_{n-1}^{-1}+F_{n-2}^{-1}
$
instead.
I wrote a simple program to compute the first terms and the sequence ...
- 620
0
votes
1
answer
22
views
calculate the Population after n-days based on a fixed growth rate
My question is similar to This but it is a bit more complicated.
Assuming I have a population of a creature that can reproduce by themselves (like bacteria).
Each one is about to give birth in a ...
- 1
4
votes
1
answer
238
views
How are there two generating functions for the Fibonacci sequence?
I've come across two generating functions for the Fibonacci sequence,
$$
F(z) = \frac{1}{1-z-z^2}
\quad\text{and}\quad
F(z) = \frac{z}{1-z-z^2} \,.
$$
I've seen both of their proofs and both of ...
- 55
1
vote
0
answers
71
views
Are the roots of $x^{h+k}-m(x^{k-1}+x^{k-2}+\cdots +x+1)$, either real or complex, distinct, where $m,h,k$ are positive integers with $m,h>1$?
The recursive relationship $F_n=F_{n-1}+mF_{n-h-1}-mF_{n-h-k-1}$ or equivalently $F_n=m(F_{n-h-1}+\cdots +F_{n-h-k})$ comes from looking at Fibonacci's rabbit problem but assuming each litter has $m\...
- 19
2
votes
1
answer
32
views
Analytic continuation of the sum of the reciprocals of the $n$-bonacci sequences.
In a previous question, I asked for an approximation of the sum of the reciprocals of the Tribonacci numbers. So I was wondering if there is a function for the sum of the reciprocals of the $n$-...
- 3,574
0
votes
1
answer
38
views
Relations involving Fibonacci and Lucas numbers $F_{mn}, F_n, L_n$
If we take $\alpha = \frac {1 + \sqrt 5} 2$ and $\beta = \frac {1 - \sqrt 5} 2$ and $F_n$ be the $n$-th Fibonacci number and $L_n$ be the companion Lucas number then,
$$
F_n = \frac {\alpha^n - \beta^...
- 2,182
3
votes
2
answers
92
views
Approximation of $\sum_{k=1}^\infty \frac{1}{T_k}$ where $T_k$ are the tribonacci numbers
So I have heard about the reciprocal Fibonacci constant, which is the sum of the reciprocals of the Fibonacci numbers. A natural question is to ask what we get when we add the reciprocals of the ...
- 3,574
1
vote
1
answer
69
views
How to find a closed form expression for the following recurrence?
Recently, I was dealing with the following recurrence, where $F_n$ is the $n$-th Fibonacci number:
$$
\displaylines{\begin{align}a(0) &= 0 \\\ a(1) &= 1 \\\ a(n) &= a(n-1) + a(n-2) + F_n + ...
- 195
2
votes
0
answers
68
views
Prove that $\gcd(F_n,F_{n+3})= 1$ or $2$. [duplicate]
Prove that $\gcd(F_n,F_{n+3})=1$ or $2$ for $n\geq 2$.
The excercise has a slightly confusing hint. It says "Let $d|\gcd(F_n,F_{n+3})$" and also asks to show $d|2$ which I understand.
I don'...
- 69
1
vote
1
answer
64
views
Fibonacci 19^n is multiple of 19 a mathematical property or a unique event? [duplicate]
Considering the 0 as the first index of Fibonacci numbers,
I observed that Fibonacci(19^n) is multiple of 19. (Practically I could try till n=7).
Is this a mathematical property of prime numbers or a ...
- 107
0
votes
0
answers
82
views
How can I prove by induction that $3 ∣ f _{4n}$ is true?
This is related to the fibonaci numbers. I understand the way a proof by induction works, and these are 2 statements that are given:
$f_1=1$
$f_2=1$
$f_n = f_{n-1} + f_{n-2}$,
as long as $f\ge3$ (...
- 11
0
votes
1
answer
54
views
Prove the properties of Fibonacci sequence $F_p$ $F_{p-1}$ $F_{p+1}$ mod p for prime p
p is a prime and Let $F_{n}$ denotes the Fibonacci sequence.
I want to show the following properties of $F_p$:
$F_p\equiv\left (\frac{p}{5} \right ) (mod ~p)\tag{0}$
And for $F_{p+1}$:
$F_{p+1}\...
- 369
-2
votes
1
answer
94
views
Prove $T(n)=2F(n+1)-1$ by induction. Please read body for full question. [closed]
Given : $F(n)=F(n-1)+F(n-2)$ with $F(0)=0$ and $F(1)=1$. $T(n)$ is the total number of calls needed to calculate $F(n)$ using top-down approach.
By writing top-down approach program, I have calculated ...
0
votes
1
answer
33
views
How do you get the characteristic polynomial of a recursion?
For example, the characteristic polynomial of the Fibonacci sequence is $x^2 -x -1$. What are the steps involved in this?
- 1
2
votes
2
answers
44
views
What is $x$ of the $m$-Fibonacci complexity $O(x^n)$ as $m \rightarrow \infty$?
I was helping a colleague (we're both tertiary students) with a computer science question. The question requires analysing the time complexity of various Fibonacci algorithms. One is the slow ...
- 309
0
votes
1
answer
117
views
Prove that for all $n > 2$, we have $F_j < F_n $ for every $j$ in $\{1, \dotsc ,n-1\}$ (Fibonacci Sequence)
I'm trying to show the following, where $F_n$ are the Fibonacci numbers.
Prove that for all natural numbers $n > 2$, we have $F_j < F_n $ for every $j$ in $\{1, \dotsc ,n-1\}$.
I am not sure ...
- 51
1
vote
1
answer
150
views
Prove that the total binary sequences of length n with no consecutive 1s is Fib(n+1) .
I have seen multiple posts on how to prove this, but I don't understand why we need only Fib(n-1) and Fib(n-2) from the Fib ...
- 11