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
80 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 ...
2
votes
4answers
866 views

Strong inductive proof for this inequality using the Fibonacci sequence.

Problem I need to determine for what natural numbers is $2n < F_n$, where $F_n$ is the $n^{th}$ Fibonacci number determined by $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n-1}+F_{n-2}$. I then need to ...
8
votes
2answers
288 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,\ ...
3
votes
2answers
133 views

Fibonacci combinatorial identity

Can someone explain how to prove the following identity involving Fibonacci sequence $F_n$ $F_{2n} = {n \choose 0} F_0 + {n\choose 1} F_1 + ... {n\choose n} F_n$ ?
8
votes
2answers
807 views

Proof by induction on Fibonacci numbers: show that $f_n\mid f_{2n}$

I was studying Mathematical Induction when I came across the following problem: The Fibonacci numbers are the sequence of numbers defined by the linear recurrence equation- $f_n = f_{n-1} + ...
2
votes
2answers
32 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
143 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
2answers
133 views

Prove the $n$th Fibonacci number is the integer closest to $\frac{1}{\sqrt{5}}\left( \frac{1 + \sqrt{5}}{2} \right)^n$

Prove that the $n$th Fibonacci number $f_n$ is the integer that is closest to the number $$\frac{1}{\sqrt{5}}\left( \frac{1 + \sqrt{5}}{2} \right)^n.$$ Hi everyone, I don't really understand the ...
3
votes
1answer
49 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
20 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
65 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 ...
4
votes
0answers
139 views

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

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 number $F_n^2+F_m^2$ is a square ...
1
vote
2answers
52 views

Fibonacci divisibility

Prove that the following holds: $3|F_n$ if and only if $4|n$ Base case for $n=1$: $F_1$=1, so $F_1$ is not divisible by 3 and 1 is not divisble by 4. So the proposition holds for $k=1$ Continue ...
0
votes
1answer
32 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
43 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 ...
3
votes
3answers
206 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
66 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 ...
2
votes
1answer
51 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 ...
1
vote
2answers
48 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 ...
0
votes
2answers
87 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. ...
5
votes
2answers
91 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, ...
16
votes
2answers
1k views

Find all integer solutions for the equation $|5x^2 - y^2| = 4$

In a paper that I wrote as an undergraduate student, I conjectured that the only integer solutions to the equation $$|5x^2 - y^2| = 4$$ occur when $x$ is a Fibonacci number and $y$ is a Lucas number. ...
7
votes
3answers
165 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 ...
0
votes
1answer
34 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 $is known as the sequence of lucas numbers. where $ a_n $ is the fibonnaci series. Prove: ...
6
votes
3answers
213 views

Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$

Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$; I was stuck with this question for a while... Help me please!!! Thanks!!!
1
vote
1answer
35 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 ...
4
votes
2answers
80 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] ...
1
vote
1answer
48 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 ...
1
vote
2answers
49 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 ...
2
votes
0answers
45 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 ...
3
votes
2answers
49 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. ...
7
votes
4answers
735 views

Fibonacci numbers and golden ratio: $\Phi = \lim \sqrt[n]{F_n}$

Let $\Phi$ be the golden ratio and $F_n$ be the usual Fibonacci numbers. How can I derive the following formula? $$ \Phi = \lim_{n\rightarrow \infty} \sqrt[n]{F_n} $$ I know the usual relation $$ ...
9
votes
2answers
167 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,\ \ ...
10
votes
4answers
3k views

Interesting properties of Fibonacci-like sequences?

Everyone is familiar with the Fibonacci Sequence, [0] 1 1 2 3 5 8 ... and many of it's interesting properties. For example, as the sequence continues, the ratio of ...
2
votes
0answers
59 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 ...
2
votes
2answers
1k views

Solve the recurrence of $T(n)= 3T(n-1)+1$ with$ T(0)=2$ by iteration of the recurrence

Solve the recurrence of $T(n)= 3T(n-1)+1$ with $T(0)=2$ by iteration of the recurrence. (I was told that there is no need to prove it by induction) I googled "iteration of the recurrence." I did not ...
1
vote
2answers
72 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 ...
35
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 ...
2
votes
1answer
26 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 ...
0
votes
0answers
68 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^*}$: ...
1
vote
1answer
58 views

Calculating the hitting probability using the strong markov property

** This problem is from Markov Chains by Norris, exercise 1.5.4.** A random sequence of non-negative integers $(F)n)_{n\ge0}$ is obtained by setting $F_0=0$ and $F_1=1$ and, once $F_0,\ldots,F_n$ are ...
1
vote
0answers
47 views

Proving an equation dealing with Fibonacci numbers

Prove that: $f(2 \cdot k) = f(k) \cdot  f(k + 1) + f(k - 1)  \cdot f(k) $ Where $f(k)$ is the kth Fibonacci number. Also prove that: $f(2 \cdot  k + 1) = f(k) \cdot f(k) + f(k + 1) \cdot f(k + 1) ...
3
votes
4answers
130 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 + ...
2
votes
4answers
115 views

Fibonacci proof question: $f_{n+1}f_{n-1}-f_n^2=(-1)^n$ [closed]

Show that $$f_{n+1}f_{n-1}-f_n^2=(-1)^n$$ when $n$ is a positive integer and $f_n$ is the $n$th Fibonacci number.
1
vote
0answers
116 views

using induction to prove that the formula for finding the n-th term of the Fibonacci sequence is: [duplicate]

May someone help me? I am trying to use induction to prove that the formula for finding the $n^{th}$ term of the Fibonacci sequence is: ...
2
votes
2answers
217 views

Inductive proof of a formula for Fibonacci numbers

May someone help me? I am trying to use induction to prove that the formula for finding the $n$-th term of the Fibonacci sequence is: ...
2
votes
3answers
199 views

Statement on the Fibonacci sequence

Question: Let $n,m,\in\mathbb{N^*}$ with $n>1$ and let $u_n$ denote the $n$-th term of the Fibonacci sequence, then $$u_{n+m}=u_{n-1}u_m+u_nu_{m+1}$$ I know these theorems: Two consecutive ...
0
votes
1answer
102 views

Two issues of Number Theory

Knowing in Fibonacci sequence$$u_n\mid u_m\Longleftrightarrow n\mid m$$ Question 1: In Fibonacci sequence, show that $$5\mid u_m\Longleftrightarrow 5\mid m$$ Show: $\Longrightarrow$ In ...
0
votes
2answers
97 views

How to prove that the Fibonacci sequence $7\mid U_m\Longrightarrow 8\mid m$ and $4\mid U_m\Longrightarrow 6\mid m$

How to prove that the Fibonacci sequence $$7\mid U_m\Longrightarrow 8\mid m$$ and $$4\mid U_m\Longrightarrow 6\mid m$$I was confused because there $\{ 4,7 \}$ in Fibonacci sequece
4
votes
1answer
54 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 ...