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

0
votes
1answer
42 views

Sophie Germain and Fibonacci primes [on hold]

If $p$ is a Sophie Germain prime, are the Fibonacci numbers $F_{p}$ and $F_{2p+1}$ prime?
2
votes
1answer
46 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
61 views

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

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
49 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
22 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
71 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
46 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
41 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
49 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 ...
2
votes
2answers
39 views

Question regarding the First Few Terms of a Fibonacci-like Recurrence.

My friend handed me an interesting problem involving Fibonacci numbers and i was interested in trying to generalize it, and see what known results are around after that. But before I do that, i had a ...
9
votes
3answers
232 views

A sum of Fibonacci numbers

Let $F_n$ be the Fibonacci numbers. I would like to prove this really messy identity: $$\sum_{n=0}^{\infty}(-1)^n(n+1)^2\frac{5n^2F_{k}+(F_{k+3}+3F_{k+2})n+2F_{k+2}+F_{k-1}}{{2n+2\choose 1}{2n+2 \...
1
vote
3answers
69 views

Show that $\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix}^n$ for all $n ∈ N$.

The Fibonacci numbers $F_n$ are recursively defined by $F_0 = 0, F_1 = 1$ $F_{n+2} = F_{n+1} + F_n, n = 0,1,...$ i) Show that $\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix} = \begin{...
3
votes
2answers
26 views

Andrew wants to cross a 12-foot long bridge. He can either take a 1 foot step or a 2 foot step.Provide a recursive formula for this problem.

Other notes about the problem: Keep in mind that a 2 foot step then a 1 foot step is different than a 1 foot step then a 2 foot step. I have found it easy to think of the bridge as a 1x12 game board ...
0
votes
0answers
39 views

Fibonacci primes vs Mersenne primes

It seems that only 34 Fibonacci primes are known while 54 Mersenne primes are known, while Fibonacci numbers are sparser than Mersenne numbers. Compare https://en.wikipedia.org/wiki/Fibonacci_prime ...
5
votes
2answers
71 views

Proof $\sum_{k=0}^\infty \binom{k}{n-k} = f_{n+1}$ where $f_n$ is the n-th Fibonacci-number

In our combinatorics script it is written, that $$\sum_{k=0}^\infty \binom{k}{n-k} = f_{n+1}$$ where $f_n$ is the n-th Fibonacci-number. Apparently this can be proven through the generating function ...
0
votes
1answer
25 views

Fibonacci inequality proved by induction.

I need to show that $F_{n+2} \geq 2F_{n}$ for all $n \geq 1$. For n=1, $F_3=2=2(F_1)=2$.Checks out. Now for the inductive hypothesis, assume for some n that $F_{n+2} \geq F_{n}$. We need to show ...
5
votes
2answers
57 views

Let $(F_n)_{n\in \mathbb{N}}$ be the Fibonacci sequence. Prove that $F_{n+1}F_n - F_{n-1}F_{n-2} = F_{2n-1}$.

Let $(F_n)_{n\in \mathbb{N}}$ be the Fibonacci sequence. Prove that $F_{n+1}F_n - F_{n-1}F_{n-2} = F_{2n-1}$. I'm trying to prove usinge the induction principle, so here is my sketch: $(i)$ $n = 3 \...
2
votes
1answer
81 views

Proving that there are infinitely-many prime numbers that are not Fibonacci numbers

Fibonacci numbers $\{F_n\}_n\in\mathbb{N}$ are defined by the sequence $F_{n+2}=F_{n+1}+F_{n}$, $F_1=F_2=1$. Now prove that there are infinitely many prime numbers which are not Fibonacci numbers. I ...
4
votes
1answer
57 views

Are all Fibonacci words uniquely represented as concatenation of two palindromes?

Suppose Fibonacci word sequence is a word sequence defined by the following relations: $$\phi_1 = «0»$$ $$\phi_2 = «01»$$ $$\forall n > 2 \text{ } \phi_n = \phi_{n - 1}\phi_{n - 2}$$ Let’s prove, ...
4
votes
3answers
108 views

Have I discovered a new significance to a previously discovered constant?

I've been interested in infinite sums for a while, though I have no formal education of them. I was messing around with repeated division and addition (e.g. 1 + (1 / (1 + (1 /...)))) I then plugged ...
0
votes
1answer
25 views

Asymptotic for general Fibonacci sequence.

Consider the sequence $$f(n,k) = \sum_{i=1}^{k}f(n-i,k)$$ with the following initial conditions $f(n,k) = 0$ for $n<0$ and $f(0,k)=1.$ I noticed that $$\lim_{n\to \infty} \frac{f(n+1,k)}{f(n,k)}=\...
0
votes
0answers
34 views

Formula for the Tribonacci sequence [duplicate]

Is there a formula for the Tribonacci sequence, where the formula for Fibonacci is: $$F_n=\frac{(1+\sqrt 5)^n-(1-\sqrt 5)^n)}{2^n\sqrt 5}.$$
0
votes
0answers
33 views

Show that $F(3n) = F(n)(L(2n) + (-1)^n)$

Let $F_n, L_n$ be the Fibonacci and Lucas sequences respectively. Show that $F(3n) = F(n)(L(2n) + (-1)^n)$. In my attempt I am using Binet's formula, and the equivalent for the Lucas numbers. $F(3n) =...
0
votes
1answer
33 views

How to show this inequality involving generalized Fibonacci sequence?

Define recursively, $$f(n,k) = \sum_{i=1}^{k}f(n-i,k)$$ with initial conditions $f(n,k)=0$ for $n<0$ and $f(0,k)=1.$ For starters observe that $$\lim_{n\to \infty}\frac{f(n+1,k)}{f(n,k)}=\phi(k)$$ ...
-1
votes
2answers
47 views

Calculating how many 2's appear in the last digits of the first 2004 Fibonacci numbers.

I have had some trouble with the following question (It is from the Australian Mathematics Competition). If anyone would be able to produce a solution (with considerable working), that requires no use ...
0
votes
0answers
44 views

Prove $F(n+2) - 1 = 1 + n(h-1) + n(h-2)$ by mathematical induction

$F(0)= 0$ and $F(1) = 1$ are predefined; $F(n)$ references the $n^{th}$ Fibonacci number. $n(h)$ is the minimal number of nodes needed to construct a AVL binary tree of height $h$. The theory shouldn'...
0
votes
1answer
48 views

Given a Fibonacci number, find what number in the sequence it is [duplicate]

I came across the formula for the $n$th Fibonacci number: $$\frac{\Phi^n-(-\Phi)^n}{\sqrt5} = x,$$ where $x$ is the $n$th Fibonacci number. This formula works one way around, but I cannot seem to ...
2
votes
4answers
90 views

Prove Fibonacci Sequence Property: $x^2_n + x^2_{n+1}=x_{2n+1}$

For Fibonacci Sequence, We know that the recursive difference equation is: $$ x_{n+2} = x_n + x_{n+1}\ \ \ \ n\ \geq 0 $$ And that the closed form solution is: $$ x_n = \frac{1}{\sqrt{5}}\left[ \...
1
vote
1answer
41 views

Generating function for Fibonacci-like sequence

I have been reading the book Irresistible Integrals lately, and it inspired this problem. For some constants $a,b\in \Bbb R$ we define the sequence $S(a,b)=\{e_n(a,b):n\in\Bbb Z_{\geq0}\}$ by the ...
9
votes
4answers
172 views

Proving the Fibonacci identity $(−1)^{m−k}(F_{m+k+1}F_{m−k−1}−F_{m+k}F_{m−k}) =F_{k}^2+F_{k+1}^2$

Prove that for two natural numbers $m$ and $k$, where $m>k$ the following identity holds: $$(−1)^{m−k}(F_{m+k+1}F_{m−k−1}−F_{m+k}F_{m−k}) =F_{k}^2+F_{k+1}^2$$ Here the exercise comes with a ...
2
votes
1answer
68 views

Proving That Consecutive Fibonacci Numbers are Relatively Prime

The Problem: Prove that consecutive Fibonacci numbers are relatively prime. I have seen proofs where people use induction and show that if $\gcd(F_n, F_{n+1})=1$, then $\gcd(F_{n+1}, F_{n+2})=1$ ...
2
votes
3answers
408 views

Why is the 0th term of the padovan sequence 1 but for fibonacci it is 0?

padovan numbers are: P(0)=1, P(1)=1, P(2)=1, P(3)=2, P(4)=2, P(5)=3, 4, 5, 7, 9, 12, 16, 21, etc WHERE P(n) = P(n-2) + P(n-3) fibonacci numbers are: F(0)=0, F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, ...
0
votes
4answers
88 views

Prove for the Fibonacci sequence: $F(m+n) = F(m-1) \cdot F(n) + F(m) \cdot F(n+1)$

The following formula shall be proved by induction: $$F(m+n) = F(m-1) \cdot F(n) + F(m) \cdot F(n+1)$$ Where $F(i), i \in \mathbb{N}_0$ is the Fibonacci sequence defined as: $F(0) = 0$, $F(1) = ...
0
votes
1answer
76 views

How to prove that Fibonacci number pairs are the only solution to this equation?

I need to find all the solutions to the equation $$x^2 + xy - y^2 = 1$$ However, I am not interested in using Pell's equation the way it has been suggested in a similar question here: Find all ...
1
vote
2answers
110 views

What is the first 11 digit prime of Fibonacci?

I am having difficulty finding the first eleven-digit prime number of Fibonacci.. If anyone has an answer I would greatly appreciate it. I'm mostly asking this because it's one part of a greater ...
1
vote
2answers
56 views

Why is $F_n = r^n$ a solution of the difference equation if $r$ satisfies $r^2-r-1=0$?

The following is from p.4 of https://www.math.ucdavis.edu/~hunter/intro_analysis_pdf/ch3.pdf The terms in the Fibonacci sequence are uniquely determined by the linear difference equation $$...
-2
votes
1answer
58 views

Fibonacci numbers. how to prove? [duplicate]

We are give Fibonacci numbers.{fi | i ∈ N}, where f0 = 0, f1 = 1, fn+2 = fn +fn+1, n∈ N. How to proof with mathematical induction that if n divides by m, then fn divides by fm? I am having trouble ...
0
votes
1answer
45 views

Determine the index of a given Fibonacci number

As shown here, the (rounded) index $n$ of a given Fibonacci number $F$ is calculated with $$ n(F) = \left\lfloor \log_\varphi (F \cdot \sqrt{5} + \frac12) \right\rfloor, $$ where $$ \log_\varphi(x)...
2
votes
1answer
58 views

Proof by Induction of Sum of Squares of Fibonacci using Difference Opperators

Consider the sequence of Fibonacci numbers $\{F_n\}_{n\geq0}$ where $F_0=0,F_1=1$ and $F_n=F_{n-1}+F_{n-2}$ for $n\geq2$. It is proved that \begin{equation}\sum_{i=0}^nF_i^2=F_nF_{n+1}.\end{equation} ...
0
votes
2answers
31 views

Explaining the proof of Fibonacci number using inductive reasoning

Fibonacci numbers are defined as follows. $$F_{1}= F_{2} = 1$$ When $n \geq 3$, $$F_{n} = F_{n-1} + F_{n-2}$$ Task: Prove the following statement using mathematical induction: When $n \...
0
votes
0answers
29 views

Proof Ideas - Strong Induction, Pascal's Triangle and Fibonacci Numbers

I'm looking for attributes/characteristics/properties to prove about Pascal's Triangle or the Fibonacci numbers. Preferably something that requires a strong induction proof that is on the same level ...
10
votes
4answers
96 views

Recurrence and Fibonacci: $a_{n+1}=\frac {1+a_n}{2+a_n}$

For the recurrence relation $$a_{n+1}=\frac {1+a_n}{2+a_n}$$ where $a_1=1$, the solution is $a_n=\frac {F_{2n}}{F_{2n+1}}$, where $F_n$ is the $n$-th Fibonacci number, according to the convention ...
0
votes
1answer
46 views

Pisano period upper-bound for Tribonacci (3 step Fibonacci)

For the Pisano Period of a 2-step Fibonacci at modulo $n$ a common and simple upper bound, according to this list of open problems, is $n^2-1$. Is there a similar upper bound for the Pisano Period of ...
1
vote
1answer
32 views

Does $N(mn)|N(m)N(n)$ for $\gcd(m,n)=1$? (Fibonacci Sequence)

Consider Fibonacci Sequence Mod m, n and mn. And let N(m) be the period of Fibonacci Sequence mod m. For several $m,n$ I tried to compare $N(mn)$ with $N(m)N(n)$. It looks that there is no specific ...
0
votes
0answers
21 views

Infinite sequence to produce negatives and imaginary numbers from reals?

I'm interested in having a sequence or sequences that I can show is complete in the notion of computational completeness with respect to the ability to derive all integers, reals, imaginary numbers ...
6
votes
2answers
1k views

A pattern in determinants of Fibonacci numbers?

Let $F_n$ denote the $n$th Fibonacci number, adopting the convention $F_1=1$, $F_2=1$ and so on. Consider the $n\times n$ matrix defined by $$\mathbf M_n:=\begin{bmatrix}F_1&F_2&\dots&F_n\...
0
votes
1answer
36 views

Generating function of number of assignments with constraints

Suppose I have $N$ boxes on a ring. Each box can be assigned number $0$ or $1$. Neighboring boxes can not have both $1$. so the assignment $0000$ is allowed, but the assignment $0110$, $1001$ etc are ...
2
votes
1answer
82 views

A Fibonacci convolution

A Fibonacci convolution. Recall that $$F(x)=\sum_{n=0}^\infty F_n x^n =\frac{x}{1-x-x^2} =\frac{1}{\sqrt{5}} \left(\frac{1}{1-\Phi x} -\frac{1}{1-\bar{\Phi}x}\right).$$ (a) Prove that $\displaystyle ...
1
vote
2answers
73 views

Show that these non-linear recursions produce integers only

The recurrence is of third order: Start with \begin{align*}a_0(x)&=1\\ a_1(x)&=1\\ a_2(x)&=x \end{align*} and then \begin{align*}a_{n+3}(x)&=\frac{a_{n+2}^2(x)-a_{n+1}^2(x)}{a_{...
0
votes
3answers
46 views

Fibonacci sequence/recurrence relation (limits)

Let $\lbrace F_n\rbrace_{n \in \mathbb{N_0}}$ be the Fibonacci sequence. $F_{n+1}=F_{n-1}+F_{n-2}$ for $n \in \mathbb{N}$ with $n \geq 2$ and start values $F_0:=0$ and $F_1:=1$. How to determine: $...