Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

5
votes
1answer
67 views

Maximum and minimum of $\frac{1}{n} \cot(n \pi \phi)$, $\phi$ Golden ratio

Studying aspects of the problem https://math.stackexchange.com/a/3186019/198592 I stumbled on this question. Designating the golden ration by $\phi=\frac{1+\sqrt{5}}{2} \simeq 1.61803$ and letting $...
2
votes
1answer
49 views

Combinatorial proof of fibonacci

I need to proof this expression combinatorially $f_{2n+1}= \sum_{i \geq 0} \sum_{j\geq 0} \binom{n-i}{j} \binom{n-j}{i}$ for all $n \geq 0$. As $f_1 = 1, f_2=2$ I dont know how to start combinatorial ...
3
votes
1answer
35 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} = ...
1
vote
2answers
52 views

Problem relating to Fibonacci numbers

Simplify $$F(n-2)\cdot F(n+2)-F(n)^2$$ where $F(n)$ is the $n^{th}$ Fibonacci number. I tried solving it by induction but it couldn't obtain the answer.
2
votes
1answer
45 views

Least period of the Fibonacci sequence in a field

Actually, I'm solving some exercises from the book "Finite Field" by Rudolf Lidl et al. There is an exercise for which the idea is missing to solve it: Let $r$ be the least period of the Fibonacci ...
0
votes
1answer
22 views

Fibonacci matrix for different constant values in recurrence relation

For Fibonacci series we have a recurrence relation $F_n=F_{n-1}+F_{n-2}$.So the initial matrix can be written as $$A=\begin{bmatrix} 1 &1\\ 1 &0 \\ \end{bmatrix}$$ where $a_{11}=F_{n+1}, a_{21}...
-1
votes
1answer
17 views

How can I describe the union between this specific set and the Fibonacci sequence set?

I have two sets, $M_1$ and $M_2$: $$ M_1 = \{x\mid x \text{ is a Fibonacci number}\}\\ M_2 = \{x \mid −10 \leq x \leq 10\} $$ How can I describe the union between these sets? $$M_1 \cup M_2$$ ...
0
votes
1answer
54 views

Fibonacci Challenge Proof

We call a pair of codes x and y to be a losing pair if the Fibonacci ex- pansion for one of them ends in an even number of zeros and Fibonacci expansion for the other is obtained by adding a zero to ...
2
votes
1answer
61 views

Is there some way of proving that this simple pattern tiles the plane? Is a formal proof even necessary?

I’m thinking about the well known pattern generated by constructing a series of squares with side lengths following the Fibonacci sequence. Each time we add in a new square, we choose a side of the ...
1
vote
1answer
57 views

How can I find the sum of squares of binomial coefficient and fibonacci numbers $ \sum_{k=0}^{n} \left[ \binom{n}{k}F_k \right]^2 $

In this topic (Binomial coefficient and fibonacci numbers), it can be easily seen the sum of binomial coefficient and fibonacci numbers is $$ \sum_{k=0}^{n} \binom{n}{k}F_k = F_{2n}. $$ I have also ...
0
votes
0answers
26 views

Non-Fibonacci numbers, appear from Fibonacci Sums …?

(Please consider that i am not the best on explaining things when it comes to mathematics, so i will try my best.) Lately this month i had an idea, to test if the Sum of Fibonacci Numbers always ...
4
votes
1answer
39 views

How to improve this bound?

As everyone reading this should very well know, $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n - 2} + F_{n - 1}$ for all integers $n > 1$. The choice of uppercase F for the Fibonacci numbers seems to be ...
4
votes
1answer
46 views

How can I make sure the recurrence relation is correct?

If $A_n$ represents the number of ways to write $n$ as an ordered sum of positive odd integers, then $A_n = A_{n-1} + A_{n-2}$. For example, $A_2 = 1$ $(1+1)$, $A_3 = 2$ $(1+1+1)$, $(3)$, and $A_4 ...
2
votes
1answer
52 views

Time complexity for finding the nth Fibonacci number using matrices

I have a question about the time complexity of finding the nth Fibonacci number using matrices. I know that you can find $F_n$ from: $ \begin{pmatrix} 1 & 1\\ 1 & 0\\ \end{pmatrix}^n = \...
0
votes
0answers
20 views

Question on Fibonacci relationship and consecutive

I know it is the Fibonacci recurrence relation and I looked at these two posts. How many $N$ digits binary numbers can be formed where $0$ is not repeated How many length n binary numbers have no ...
0
votes
0answers
37 views

Fibonacci Workings

The Fibonacci number sequence is given by $$F_n = F_{n−1} + F_{n−2},\ n \ge 2,\\F_0 = F_1 = 1$$ Suppose we write two consecutive Fibonacci numbers in the form of a $2 \times 1$ matrix $f$, where $$ ...
0
votes
2answers
29 views

Fibonacci Proof by induction 8 [duplicate]

Fibonacci numbers have lots of uses in computer science – heaps and trees, for example. Prove by induction that $$F_n = 1 + \sum_{i=0}^{n−2} F_i,\quad n \geq 2 \text{ and }F_0 = 0, F_1 = 1$$
2
votes
1answer
27 views

Finding Annihilators for Recurrence Relations

Recently I've taken an interest in solving recurrence relations using annihilators but I'm still unclear as to how to find such annihilators. My professor provides the following linear recurrence in ...
2
votes
1answer
48 views

Prove Fibonacci Numbers $F_n$ and $F_{n+1}$ are relatively prime (induction with proof by contradiction?)

(We are proving the claim for $n \geq 1$, and we have $F_1 = 1, F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$.) The proof proceeds by induction on $n$. Base Case: We have that $F_1 =1$ and $F_2 = 1$, and ...
0
votes
1answer
32 views

Show that $f_{n+1}\cdot f_{n-1}-f^2_n=(-1)^n$ if $f_n $ is the $n$th Fibonacci number

I've reviewed this answer: https://math.stackexchange.com/a/606286/584468 and I'm getting lost on how he did $f_{k+2}f_k−f^2_{k+1}=(f_k−f_{k+1})f_k−f^2_{k+1}$ When I thought that $f_{k+2}=f_{k+1}+f_k$...
2
votes
0answers
49 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 ...
0
votes
2answers
46 views

Showing that the tribonacci sequence has relatively prime terms

Let $f_k$ denote the Fibonacci numbers. It turns out that $gcd(f_k,f_{k+1})=1$ for all $k\ge 1$ and I understand this proof. If one defines the tribonacci numbers by $t_1=t_2=t_3=1$ and $t_{k+3}=t_{...
9
votes
1answer
140 views

Congruence about Fibonacci numbers

Let $$ F_{n} = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2}\right)^{n} - \left( \frac{1-\sqrt{5}}{2} \right)^{n} \right] $$ be a Fibonacci number. If $p\neq 2, 5$ is a prime, then I want ...
0
votes
0answers
12 views

Is it possible to calculate prefix sums for sequnce defined as sum of two previous values

Let's say we have sequence $S$ defined as: $S_1 = A, S_2 = B, S_i = S_{i-1} + S_{i-2}, i > 2$. We want to find the sum of the first $N$ elements of this sequence. Is there any easy and quick way ...
0
votes
1answer
33 views

Decomposing Fibonacci Numbers

This link demonstrates certain decompositions of Fibonacci numbers into products and sums of smaller Fibonacci numbers, such as $F_{m+n} = F_{m-1}F_n+F_mF_{n+1}$. I am wondering if anyone knows of ...
0
votes
0answers
30 views

show this Fibonacci sequence this $F_{p-\left(\dfrac{p}{5}\right)}\equiv 0\pmod p$

Let $\{F_{n}\}$ be Fibonacci sequence which defined by $F_{1}=1,F_{2}=1$,and $$F_{n+1}=F_{n}+F_{n-1}$$ show that: for any prime $p$,we have $$F_{p-\left(\dfrac{p}{5}\right)}\equiv 0\pmod p$$ This is ...
0
votes
1answer
26 views

Which relation symbol goes between $F_m$ and $\phi^m$?

I have already asked a similar question where the tilde notation was used (and context can be taken from there). Now I think that tilde is not the correct symbol to go between these two functions ...
1
vote
1answer
49 views

How to represent first several Fibonacci numbers as a set?

We know that first five fibonacci numbers are $\,0,1,1,2,3\,$. Now I want to include them in a set. But according to Set theory a set cannot have duplicate elements. So, how can I write the set? ...
0
votes
0answers
29 views

Sum of Fibonacci Numbers Proof [duplicate]

Let $(f_j)_{j=1}^{\infty}$ be the sequence of Fibonacci numbers. Prove that $$ \sum_{j =1}^k f_j^2 = f_{k}f_{k+1}$$ for all $k \in \mathbb{N}$ If anybody could lend a hand in how to go about ...
3
votes
1answer
25 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 ...
0
votes
3answers
67 views

Relation between $m$th Fibonacci number and Golden Ratio

Can anyone tell me how to interpret the following expression $F_m\sim\phi^m$? EDIT: The following answer was where I have seen this notation.
4
votes
1answer
117 views

Fibonacci elegance sought for $F_{f (n)} + F_{f(n)-1}$

Updated on Friday 15th March 2019 at 5 pm in the light of comments received over the last 24 hours. The original question was; given the well known variation of Binet's Formula: $$F_n = \frac{\phi^n ...
1
vote
1answer
80 views

$I_1=\int_0^1 \frac 1 {1+\frac 1 {\sqrt x}} dx$

If we let $I_2= \int_0^1 \frac 1 {1+\frac 1 {1+\sqrt x}} dx$ and so on, we’re tasked with solving $I_n$. We can show that $I_2 = \int \frac {1+\sqrt x} {1-\sqrt x + 1} = \int \frac {1+\sqrt x} {2+\...
3
votes
1answer
76 views

generating function for $F_{5n}/(5F_n)$

Let $F_n$ be the $n$-th Fibonacci number with $F_0=0$, $F_1=1$, and $F_k=F_{k-1}+F_{k-2}$ for $k\ge2$. Prove $$\sum^{\infty}_{n=0}{a_nx^n}=\frac{1-4x-9x^2+6x^3+x^4}{1-5x-15x^2+15x^3+5x^4-x^5}$$ where ...
4
votes
3answers
109 views

Palindrome Fibonacci words

Let Fibonacci words over the alphabet $\{0,1\}$ be recursively defined by $\omega_0=0$, $\omega_1=01$, and $\omega_n=\omega_{n-1}\omega_{n-2}$ for $n\geq{2}$. I am trying to show that the word created ...
2
votes
1answer
35 views

Proof of patterns in Fibonacci words

Let Fibonacci words over the alphabet $\{0,1\}$ be recursively defined by $\omega_0=0$, $\omega_1=01$, and $\omega_n=\omega_{n-1}\omega_{n-2}$ for $n\geq{2}$. I am trying to show that the patterns $11$...
1
vote
1answer
37 views

Showing that $(1, F_{2k-1}, F_{2k+1})$ is a Markoff triple for each integer $k \geq 1$

Problem: Let $(F_n)_{n\geq1}$ denote the Fibonacci sequence with $F_1 = F_2 = 1$. Show that $(1, F_{2k-1}, F_{2k+1})$ is a Markoff triple for each integer $k \geq 1$. For reference a Markoff triple ...
1
vote
1answer
65 views

Proving a Fibonacci relation by induction

Let $n\ge1$ be an integer. Prove that there exists an integer $k\ge1$ and a sequence of positive integers $a_1,a_2,a_3......a_k$ such that $a_{i+1}\ge2 + a_i$ for all $i=1,2,3,4......k-1$ and $n=F_{...
0
votes
0answers
44 views

Infinitely Nested Radical with Fibonacci Coefficients

I was wondering if the following infinitely nested radical can be evaluated. $x= \sqrt{1+ \textbf{1}\sqrt{1+ \textbf{1}\sqrt{1+ \textbf{2}\sqrt{1+ \textbf{3}\sqrt{1+ \textbf{5}\sqrt{1+ \dots }}}}}} $ ...
0
votes
2answers
43 views

Fibonacci rounding formula proof

Recently I had to solve a little problem related with Fibonacci numbers. I was using the Binet's formula for that: $$F_{n} = \frac{\Phi^n - \phi^n}{\sqrt{5}}$$ The effective solution I got by ...
3
votes
4answers
55 views

Strong Induction for Fibonacci

I'm a little lost of how to use strong induction to prove the following for the Fibonacci sequence: $F_n < 2^n$ for all natural numbers Any help would be very much appreciated!!
0
votes
1answer
40 views

Proving that if $E_n$ is an even number of the Fibonacci sequence, then the next even number is $E_{n+1} = 4E_{n} + E_{n-1}$

This statement is true for $E_n = 2$, since $E_{n+1} = 4 \cdot 2 + 0 = 8$. I was trying to take into account that there are always only two numbers between an even number and the next even number in ...
2
votes
1answer
56 views

How can I use the relationship between the Fibonacci numbers and the EA to fill squares?

For this first question, I know how to apply the Euclidean algorithm and if I do, I get that the gcd is 1. I found this theorem online, thinking it might be able to piece together the relationship ...
0
votes
1answer
66 views

Prove that \[(x^{2} +xy -y^{2})^{2}=1\] has consecutive Fibonacci numbers as solution [closed]

Apologies if it's a duplicate question. I was not able to find such question though. I don't know how to proceed on this.
2
votes
2answers
51 views

For $F(n)$ the $n$-th Fibonacci number, is $F(a)F(b)-F(a+1)F(b-1)$ always $\pm F(m)$ for some $m$?

For $F(n)$ the $n$th Fibonacci number, the expression $$F(a)F(b)-F(a+1)F(b-1)$$ seems to be $\pm F(m)$ for some $m$. I can't specify $m$ or the sign in terms of $a,b,$ and have not tried it out ...
0
votes
1answer
40 views

Fibonacci's sequence to calculate growth of a family

I'm trying to solve the following mathematical dilemma: On the 1st of July 2000 a Lizard bears 4 babies. On the 1st July 2001 each of those Lizard bears in turn 4 babies. And so on. Assumed that ...
2
votes
4answers
81 views

What are $x$ and $y$ in $xF_n$ + $yF_{n-1}$ = $1$?

We know that the $\gcd$ of consecutive Fibonacci numbers is $1$. But while finding the coefficients $x$ and $y$ in using euclidean algorithm in reverse direction I am not able to find any pattern so ...
0
votes
1answer
50 views

Storing numbers in an efficient way in computer.

I know that we can write a very large number such as 5040 in only 7!, and imagine I want to store this number in a binary file with the least number of bits. Saving 5040 takes 13 bits of space, while ...
4
votes
1answer
44 views

Counting 4-digit combinations such that the first digit is positive and even, second is prime, third is Fibonacci, and fourth is triangular

This seemed like a basic problem, but for some reason I can't figure it out: In a $4$-digit combination, the first digit has to be a positive even number, the second a prime number, the third a ...
1
vote
1answer
94 views

Proving that every natural number can be expressed as the sum of distinct Fibonacci numbers

The Fibonacci sequence $f_1, f_2, f_3, \ldots$ is defined by $f_1 = 1, f_2 = 2$, and $f_m = f_{m−1} + f_{m−2}$ for each integer $m \ge 3$. Prove that every $n \in \mathbb{N}$ can be expressed as the ...