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

learn more… | top users | synonyms

0
votes
3answers
91 views

Lucas numbers and fibonacci

This is a question straight from the Applied Combinatorics book. Suppose that chairs are arranged in a circle. Let $L_n$ count the number of subsets of $n$ chairs which don't contain consecutive ...
4
votes
0answers
98 views

Are there infinite Fibonacci primes if and only if there are infinite Fibonacci numbers that are Fibonacci pseudoprimes?

One of the open questions about the Fibonacci numbers is if there are infinite prime numbers inside the Fibonacci sequence. I wonder if a good approach would be trying to know first if there are ...
2
votes
2answers
40 views

Prove the sum of the even Fibonacci numbers

Let $f_n$ denote the $nth$ Fibonacci number. Prove that $f_2\:+\:f_4\:+...+f_{2n}=f_{2n+1}-1$ I am having trouble proving this. I thought to use induction as well as Binet's formula where, ...
2
votes
0answers
181 views

LCM of Fibonacci numbers

$\newcommand{\lcm}{\operatorname{lcm}}$There is a nice property of Fibonacci numbers which says that: $$\gcd(F_{a_1}, \ldots, F_{a_n}) = F_{\gcd(a_1, \ldots, a_n)}$$ I am curious is there anything ...
3
votes
1answer
53 views

Showing that $f_n$ is the number closest to $\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n$ [duplicate]

I want to prove that the the $n$th Fibonacci number $f_n$ is the integer closest to $\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n$. What would be a rigorous way to go about this? I assume I'll have to ...
1
vote
0answers
26 views

Hankel determinant involving Fibonacci numbers

Let $F_n$ denote the nth Fibonacci number, with $F_1 = F_2 = 1$. Denote by M(n) the nxn Hankel matrix with $i,j $ entry $F_{i+j-1}^{n-1}$, where i and j range from 1 through n. Finally, let d(n) = ...
5
votes
1answer
98 views

Connection between Euler's totient function and Fibonacci numbers

For a sequence $(a_n)$ of natural numbers define $\alpha(n):=\min\{m\in\mathbb{N}:n|a_m\}$ whenever it exists. Thus $\alpha(n)$ is the first index $m$ such that $n$ divides $a_m$. Now define the ...
0
votes
1answer
41 views

Convergence of fibonacci quotient $\frac{f_n}{f_{n+1}}$

I know that $\frac{f_{n+1}}{f_{n}}$ converges against $\phi = \frac{1+\sqrt{5}}{2}$. The question i want to to ask you is if the following conclusion is correct, I mean i know that if we have two ...
-1
votes
1answer
45 views

What is the probability that a given a positive number, will be found in the space of shifted fibonacci sequences?

We are given a space of shifted Fibonacci sequences, Fk, Fk+1, Fk+2, Fk+3, Fk+6, Fk+8, Fk+9, Fk+10, Fk+10, Fk+11….. Given a number,n, what is the probability of this number within this space? And ...
7
votes
0answers
182 views

when $F_n^2+F_m^2$ is a square for fibonacci numbers

This is a curiosity question I'm trying to solve a Diophantine equation and I need some results about fibonnacci numbers, I encountered this problem: For which couple of integers $(n,m)$ the ...
3
votes
3answers
218 views

How many times a positive number can be found in shifted Fibonacci Sequences?

Given a positive number, how many times can this number be found in shifted fibonacci sequences? ...For example...Number 11, can be present seven times in total, in Fn+3, Fn+6, Fn+8, Fn+9, Fn+10, ...
3
votes
2answers
74 views

How to find a Fibonacci number that is divisible by $x$?

I'm looking for an algorithm that is better than just checking every number in the Fib Sequence for divisibility. Example: Find the first Fib number that is divisible by $x=223321$, with no ...
0
votes
2answers
106 views

Find a formula for the nth Fibonacci Number [duplicate]

So I'm being asked to find a formula for the nth fibonacci number. I know the answer is $$x_{n}=\frac{(1+5^{1/2})^{n} -(1-5^{1/2})^n}{\sqrt{5}2^n}$$ However I don't really know how to get there. ...
1
vote
2answers
56 views

Seeking combinatorial proof for $F_{n+1} -1=\sum\limits_{k=0}^{n-1} F_k$

In order to give a combinatorial proof for this equation, we need to find what these two count for. But I don't know what they count for and how I can pivot the RHS to show that it actually counts ...
5
votes
2answers
93 views

Prove function is Fibonacci sequence

Stuck on how to finish a question I'm working on. Have to find the number of bitstrings of length n with no odd length maximal runs of ones. For example, when n=3 there are three such bitsrings: 011, ...
1
vote
1answer
51 views

Lucas Number Sequence

Can anyone help me in this question: Define $ (b_n)$ as $b_1= 1,b_n=a_{n+1} - a_n $ for $ n\ge 2$, where $ a_n $ is the Fibonnaci series. This sequence is known as the sequence of Lucas numbers. ...
7
votes
3answers
178 views

Show that there are infinitely many integers such that $ \binom{m}{n-1} = \binom{m-1}{n} $

This question comes from the 1st Brazilian's IMO TST of 2004. I have found no solutions of it online, though I have developed one. After getting to $ mn = (m-n)(m-n+1) $, my solution relies on the ...
1
vote
1answer
37 views

Fibonacci Numbers, show $F_n$ $>=$ $2^{n/2}$ for n $>=$ 6.

I want to show that for the fibonacci numbers, $F_n$ $>=$ $2^{n/2}$ for n $>=$ 6. My thought was to prove this via induction. I showed the base case is true for $F_n$, n=6 and 7. I assumed ...
8
votes
2answers
316 views

If $ab-1$, $bc-1$, $ca-1$, $ab-a-b+c$, $bc-b-c+a$, $ca-c-a+b$ are perfect squares, then are $ab+a+b-c$, $bc+b+c-a$, $ca+c+a-b$ also perfect squares?

About a month ago, a friend of mine taught me that there exist many sets of three positive integers $(a,b,c)$ where $a\not=b,b\not=c$ and $c\not=a$ such that each of $$ab-1,\ bc-1,\ ca-1,\ ab-a-b+c,\ ...
1
vote
1answer
51 views

Proving the Fibonacci identity $\sum_{i=1}^n f_i^2=f_nf_{n+1}$ by induction [duplicate]

I am having troubles with a proof question. Prove that for any $n\ge1$, $\sum_{i=1}^n f_i^2=f_nf_{n+1}$, where $f_n$ is the $n$'th Fibonacci number. I have the base case and the induction ...
4
votes
2answers
91 views

Of fibonomials, pellonomials, and tribonomials, etc

I. Linear recurrence with order 2 Given the Fibonacci numbers $F_n$, we have $$\begin{aligned} &F_n+F_{n+1}-F_{n+2}=0\\[1mm] &F_n^2-2F_{n+1}^2-2F_{n+2}^2+F_{n+3}^2=0\\[1mm] ...
2
votes
0answers
57 views

Generalizing the Fibonacci identity $F_{2n}=-F_{n-1}^2+F_{n+1}^2$

Using an integer relations algorithm, we get, $$F_{2n}=-F_{n-1}^2+F_{n+1}^2$$ $$6F_{4n}= -F_{n-2}^4-3F_{n-1}^4+3F_{n+1}^4+F_{n+2}^4$$ The pattern of the subscripts is clear. Expressing the ...
1
vote
2answers
88 views

formula for logarithmic spiral on a linear level

I am trying to plot the contents of a circle, which include geometric elements and spirals, on a linear graph. For example, take a circle, take the beginning and the end and make it straight. What ...
3
votes
2answers
54 views

Fibonacci recursive algorithm yields interesting result

After writing a program in Java to generate Fibonacci numbers using a recursive algorithm, I noticed the time increase in each iteration is approximately $\Phi$ times greater than the previous. ...
1
vote
2answers
121 views

Need help understanding Fibonacci Fast Doubling Proof

From this website, http://www.nayuki.io/page/fast-fibonacci-algorithms (fast doubling proof close to the bottom of the page). I have understood the proof for the most part but I am struggling to see ...
2
votes
0answers
71 views

Transforming the cubic Pell-type equation for the tribonacci numbers

The Lucas and Fibonacci numbers solve the Pell equation, $$L_n^2-5F_n^2=4(-1)^n\tag1$$ The tribonacci numbers $z = T_n$ are positive integer solutions to the cubic Pell-type equation, $$27 x^3 - 36 ...
9
votes
2answers
197 views

A number $N$ is a $k$-nacci number if and only if …

For $k\ge 2\in\mathbb N$, one can define the $n$-th $k$-nacci number $f_k(n)\ (n=0,1,\cdots)$ as $$f_k(0)=f_k(1)=\cdots=f_{k}(k-2)=0,\ \ ...
2
votes
1answer
33 views

How to show that $(L_n,F_n) < 3$ (Lucas numbers and Fibonacci numbers)

While following the proof that no Fibonacci number is a perfect square larger than 144 (https://math.la.asu.edu/~checkman/SquareFibonacci.html) I stumbled in proving two of the elementary facts about ...
2
votes
1answer
74 views

Are there 3D geometric proofs of Fibonacci identities?

There is a significant number of identities involving Fibonacci numbers that can be proven in a sort of geometric way, as it is shown in the following picture: However, I couldn't find any such ...
0
votes
0answers
70 views

An identity for the Fibonacci number $F_{n^2}$

I was manipulating Fibonacci numbers defined by : $F_0=0$ and $F_1=1$ $ \forall n\in \mathbb{N}$ $F_{n+2}=F_{n+1}+F_n$ Until I obtain this equation (which I proved) $\forall n\in \mathbb{N^*}$: ...
4
votes
1answer
59 views

Closed form as sum and combinatorial of Fibonacci numbers

How can I prove that the Fibonacci numbers that are defined as $F_n=F_{n-1}+F_{n-2}, \; n \geq 2$ and $F_0=0,\ F_1=1,\ F_2=1$ have the form: $$F_n=\sum_{k=0}^{n-1} \binom{n-1-k}{k}, \; n\ge 2 $$ I ...
3
votes
0answers
150 views

What is a better comparision series for $\sum \frac {1}{F_n}$ than $\sum_0^\infty2^{-k}$?

What is a better comparision series for $\sum \frac {1}{F_n}$ than $\sum_0^\infty2^{-k}$? By better comparison series than $\sum_0^\infty2^{-k}$ we mean a series $\sum c_k$ s.t. ...
1
vote
1answer
71 views

What is wrong with the following argument involving Fibonacci and Lucas numbers?

The Lucas numbers $L_n$ are defined by the equations $L_1 = 1$, and $L_n = F_{n+1} + F_{n-1}$ for each $n \geq 2$. What is wrong with the following argument? Assuming $L_n = F_n$ for $n = ...
3
votes
4answers
199 views

A calculus proof for the general term of the Fibonacci sequence [duplicate]

Let $a_0=1$,$a_1=1$ and $a_n=a_{n-1} + a_{n-2}$ for $n \geq 2$, I would like to prove: $$a_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n + 1}- \left(\frac{1-\sqrt{5}}{2}\right)^{n + ...
3
votes
4answers
46 views

Prove $F^2_{n+1} - F_nF_{n+2} = (-1)^n$

This is a question about Fibonacci sequences, a sequence in which the previous terms build up upon the current term (e.g. $F_1 + F_2 = F_3$ where $F_1 = F_2 = 1$). How would I go about proving ...
0
votes
1answer
84 views

are there infinitely many primes in Fibonacci sequence

There is one proof about infinitude of prime with following method, http://www.ams.org/mathscinet-getitem?mr=2271540 Also it is well know that any two consecutive Fibonacci numbers are mutually ...
2
votes
4answers
132 views

Prove that $p$ divides $F_{p-1}+F_{p+1}-1$ [duplicate]

Given the Fibonacci sequence $(F_n)$, defined by $F_0=0,F_1=1, F_{n+2}=F_{n+1}+F_n$, and $p$ an odd prime number, how to prove that $p$ divides $F_{p-1}+F_{p+1}-1$? Is induction a good idea here? ...
3
votes
2answers
85 views

Sum of squares of Fibonacci Numbers

$$ \sum_{i=0}^{n} (F_{2i+1})^2 = \;?$$ I know that sum of squares of first $n$ Fibonacci numbers is $F_{n} \times F_{n+1}$.
0
votes
2answers
72 views

Proving a slight variation of the fibonacci formula using complete induction

I learned this formula for the Fibonacci series, and its respective proof in one of my Computer Science classes. F(0) = 0; F(1) = 1; F(2) = 1 However, I am taking an abstract mathematics class and ...
1
vote
1answer
40 views

Counting the sequences of coin flips that end HH after $n$ flips (a more efficient method?)

I figured out that for any given $n$ the number of sequences of heads and tails that satisfy the condition that HH wasn't flipped consecutively until flips $n-1$ and $n$ is equal to the $(n-1)$th ...
1
vote
4answers
58 views

Fibonacci sequences and related series

Let $\{a_n\}$ be a sequence such that $a_1=a_2=1$ and $a_{n+1}=a_n+a_{n-1}$ for $n\geq 2$. Prove that $\displaystyle \sum_{n=1}^\infty \frac{1}{a_n}$ converges. My work: Let $b_n=\frac{1}{a_n}$. ...
10
votes
4answers
294 views

Linear Combinations of Fibonacci Numbers (integer coefficients)

While working on problem #2 on Project Euler, I came across the need to express $F_n$ as a linear combination of $F_{n-3}$ and $F_{n-6}$. This is relatively simple to do: $$\begin{align} F_n &= ...
32
votes
6answers
5k views

Proof the Fibonacci numbers are not a polynomial.

I was asked a while ago to prove there is no polynomial $P$ in $\mathbb R$ such that $P(i)=f_i$ for all $i\geq0$. I tried to get a proof as slick as possible and here's what I got. Let ...
1
vote
2answers
109 views

Modulus of sum of sequence of Fibonacci numbers

What is the most efficient way to find the modulus of sum of sequence of fibinacci numbers. For example (F(N) + F(N + 1) + ... + F(M)) mod 1000000007.
15
votes
5answers
3k views

Is it true that the Fibonacci sequence has the remainders when divided by 3 repeating?

About this Fibonacci sequence, is it true that the remainders when divided by three repeat along with the sequence like this: Fibonacci sequence: $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...
36
votes
1answer
1k views

Why does this test for Fibonacci work?

In order to test if a number $A$ is Fibonacci, all we need to do is compute $5A^2 + 4$ and $5A^2 -4$. If either of them is a perfect square, the number is Fibonacci, otherwise not. Why does this test ...
50
votes
3answers
580 views

Closed form solution for $\sum_{n=1}^\infty\frac{1}{1+\frac{n^2}{1+\frac{1}{\stackrel{\ddots}{1+\frac{1}{1+n^2}}}}}$.

Using a symbolic computation software (Mathematica), I got the following interesting results: $$ \begin{align} \sum_{n=1}^\infty\frac{1}{1+\frac{n^2}{1+\frac{1}{1+\frac{1}{1+n^2}}}} &= ...
0
votes
1answer
98 views

Hyper sum of Fibonacci numbers

Let $F(n)$ be the $n$-th Fibonacci number. That is, $F(n)$ satisfies $F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2) (if n≥2).$ Let $f_k(n)$ be the function such that $f_0(n) = F(n)$, $f_k(n) = ...
1
vote
2answers
88 views

Divisibility of $987x^n − F_nx^{16} + F_{n−16}$

If $F_n$ is $n^{th}$ Fibonacci number, and polynomials $P_n(x)$ are defined as $987x^n − F_nx^{16} + F_{n−16}$, prove that for all $n ≥ 1$, $P_n(x)$ is divisible by $x^2−x−1$. This is from a ...
20
votes
6answers
510 views

Why does every “fibonacci like” series converge to $\phi$?

It's is well known that the ratio of side-by-side fibonacci numbers converge to $\phi$. But it seems by my calculations, that if one starts with any pair of numbers one will also get a ratio that ...