Stack Exchange Network

Stack Exchange network consists of 174 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
0answers
27 views

Using a while loops in MATLAB : Topic - Golden Ratio [on hold]

I have been recently trying to figure out how to import a while loop into my MATLAB code that outputs the value of n at which the ratio of Fibonacci numbers is equal to the golden ratio, at least to a ...
0
votes
0answers
13 views

Lucas Number Non-Residues

I am currently reading the proof that if $L_n$ is two times a square, then $n = 0, \pm 6$. Throughout the paper containing this proof, there are several references to non-residues of Lucas and ...
0
votes
1answer
46 views

Divide and conquer: Why $F(0) = 0$? [on hold]

Reading algorithms. Fibonacci example. I saw an example where it said $F(1) = 1$ and $F(0) = 0$. (Fibonacci) Why $F(1) = 1$ and $F(0) = 0$? From where does it originate? Thanks.
1
vote
1answer
50 views

Fibonacci-type Sequence Problem [on hold]

Here is the question, If the tenth number in a Fibonacci-type sequence of increasing positive integers is 301, what is the fourth number? How do I go about solving this without overly complex math? ...
1
vote
1answer
40 views

Prove by induction that $W_n = F_{2n+2}$

My problem relies on an earlier recursive definition that we solved in class: $W_n = 3W_{n-1}- W_{n-2}$ if $n \ge 2, W_0=1$, and $W_1=3.$ It also recalls the Fibonacci recursive definition of $F_n = ...
1
vote
1answer
146 views

Prove $F_{n+1} ≤ (\frac74)^n $, where $F_n$ are Fibonacci numbers [duplicate]

Let $F_n$ be the $n$-th Fibonacci number, defined recursively by $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n−1} + F_{n−2}$ for $n ≥ 2$. Prove the following by induction (or strong induction): $(a)$ For ...
2
votes
1answer
37 views

Proof regarding the golden succession [closed]

Considering the golden number $\varphi=\frac{1+\sqrt 5}2$ and the succession defined by $$r_n=1 +\frac 1{r_{n-1}}$$ for all $n \geq 2$ where $r_1=1$ How do I prove that $r_n=\frac{f_n}{f_{n-1}}$...
1
vote
0answers
20 views

Slowest-growing divisibility sequence?

There are divisibility sequences of the form $\frac{p^k-1}{p-1}$ which have the property that if $a \mid b$, then $f(a) \mid f(b)$, ensuring (among other things) that only prime indices of the ...
1
vote
1answer
70 views

Relatively Prime Fibonacci numbers

We can call the $x$th Fibonacci number Fib($x$). What's the best asymptotic lower bounds on the amount of relatively prime Fibonacci numbers between Fib($n$) and Fib($n+m$)? In other words, if we ...
0
votes
1answer
32 views

Show, for $F(n)$ the $n$-th Fibonacci number, that $\gcd(F(n),F(n-1))=1$, and that the Euclidean algorithm calculation takes $n-2$ steps

Let $F(n)$ be the $n^{th}$ Fibonacci term where $F(1) = F(2) = 1$. Show that $GCD(F(n), F(n - 1)) = 1, n > 1$ and that if one calculates $GCD(F(n), F(n - 1)) = 1$ with Euclides algorithm, its ...
1
vote
1answer
40 views

Probability of no consecutive heads with Fibonacci numbers

Let $P_{n}$ be the probability that with $n$ flips of a fair coin, there are no consecutive heads. Now let $F_{n}$ be a modified version of the Fibonacci sequence such that $F_{0}=1, F_{2}=2, F_{3}=3$...
1
vote
1answer
49 views

Strong Inductive proof for inequality using Fibonacci sequence

I am trying to prove that $F_n \geq 4 * F_{(n - 3)}$ using the Fibonacci sequence, I think it the proof requires strong induction but I am unsure of how to apply it. My work so far: Define the ...
1
vote
0answers
79 views

For Fibonacci numbers: $\gcd(F_m, F_n) = F_{\gcd(m, n)}$

Let $(F_n\mid n\in\Bbb N)$ be the Fibonacci sequence. Then $\gcd(F_m, F_n) = F_{\gcd(m, n)}$ for all $m,n\in\Bbb N$. My attempt: Lemma 1: $m\mid n\implies F_m\mid F_n$ (A user presented a proof here)...
0
votes
1answer
72 views

Fibonacci system of equations: part 1

In this recent unanswered question I had asked about the probability of exactly one negative solution in a $3\times 3$ system of equations with Fibonacci-like coefficients, denoted by $F_i$. With $\...
3
votes
1answer
44 views

How to change the base cases of a tribonacci sequence solved by matrix exponentation

So the base case of a Fibonacci sequence is the following matrix: \begin{bmatrix}1&1\\1&0\end{bmatrix} Which I understood as being: \begin{bmatrix}F_2&F_1\\F_1&F_0\end{bmatrix} And ...
2
votes
1answer
41 views

A little help for building the Fibonacci spiral in a particular reference system

In the following picture, the numbers represent the building steps of the Fibonacci spiral (or Golden spiral). I would like to find the coordinates of the upper-left corner of the squares (black dots)...
4
votes
0answers
80 views

What is the probability of exactly one negative solution in a Fibonacci system of equations?

The Fibonacci numbers denoted by $F_i$ for $i\ge1$ are $$1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,\cdots$$ where they satisfy the property $F_{i+2}=F_{i+1}+F_i$. I have listed the first $15$ ...
1
vote
0answers
13 views

How to construct spiral phyllotactic pattern with the given number of spirals?

It is known that the spiral phyllotactic pattern is common in Nature, especially in Botany. It consists of two group of clockwise and anticlockwise spirals, starting from the center. In most cases ...
0
votes
1answer
62 views

Fibonacci summation proof using matrices?

I have a standard proof for the theorem: $$\sum_{}^n f_1+f_3+f_5+...+f_{2n-1} = f_{2n}$$ $$f_i$$ refers to the Fibonacci numbers for future reference. It involves setting p(k) as p(k+1) and ...
3
votes
1answer
69 views

Fibonaccith fibonacci number

Let $f_n$ denote the $n$th Fibonacci number. A positive integer $n$ is called good if $f_{f_n}$ is divisible by $n$ but $f_n$ is not divisible by $n$. My question is: how many good numbers are there. ...
16
votes
1answer
188 views

Continued fraction involving Fibonacci sequence

What is the limit of the continued fraction: $$\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{3+\cfrac{1}{5+\cfrac{1}{8+\cdots}}}}}}\ $$ that involves the Fibonacci sequence terms as denominators? I'...
2
votes
1answer
54 views

Fibonacci Coding Inductive Proof

Prove by induction on $n$, that every positive integer has a Fibonacci representation, as in the Fibonacci code representation. So, while I understand the premise behind the Fibonacci coding, and I ...
3
votes
0answers
72 views

Evaluating $\sum\limits_{n \ge 0} \frac{1}{x^{2^n}-y^{2^n}}$ where $x, y \in \mathbb R^{+}$ and $x \ne y, x>1.$

I reduced a competition problem involving Fibbonacci numbers to the evaluation of this simple sum. I've tried telescoping, factorization, and even rewriting the product as $$S = \frac{1}{x-y} \sum_{n ...
0
votes
3answers
49 views

Showing that the $n$-th Fibonacci number $f_n$ satisfies $f_n < 2^n$

Question: The Fibonacci numbers are $1,1,2,3,5,8,13,21,34,\dotsc$ In general, the Fibonacci numbers are defined by $f_1=1$, $f_2=1$, and $f_n = f_{n-1} + f_{n-2}$ for $n \geq 3$. Prove that the $n$-...
0
votes
2answers
60 views

Constant-recursive Fibonacci identities

Under what conditions does $F_z = a F_x + b F_y$ imply $F_{z+k} = a F_{x+k} + b F_{y+k}$? For example, $F_4 = 3 F_2 - F_0$, and $F_5 = 3 F_3 - F_1$, $F_6 = 3 F_4 - F_2$, etc. If I can prove using ...
0
votes
1answer
35 views

Ratio of 0's to 1's in the Fibonacci Word is the golden ratio

Define $S_0=0, S_1=01$. Then for $n\geq 2$ we define $S_n=S_{n-1}S_{n-2}$ (concatenating the previous sequence and the one before that). We obtain a limiting sequence, which we call the inifinite ...
0
votes
0answers
25 views

Fibonacci sieve and factoring

I want to know different sieve techniques for Fibonacci numbers and how they works. In wikipedia it is written only that the Cassinie's identity are useful in setting up the special number field sieve ...
0
votes
1answer
41 views

Proving that $\left | \frac{1+\sqrt{5}}{2}-R_k \right |>\frac{1}{Q_k^2\sqrt{5}}$.

I have to prove this inequality, where $Q_k$ is the $k$-th Fibonacci number and $R_k$ is the $k$-th convergent of $[1;1,1,...]$: $$R_1=1$$ $$R_2=1+\frac{1}{1}$$ $$R_3=1+\frac{1}{1+\frac{1}{1}}$$ and ...
-2
votes
1answer
53 views

Write $F_{1}-F_{2}+F_{3}-F_{4}+…+F_{2n-1}-F_{2n}$ as a summation

Let $F_{i}$ be the $i^{th}$ Fibonacci number (a) Write $F_{1}-F_{2}+F_{3}-F_{4}+...+F_{2n-1}-F_{2n}$ as a summation (b) Prove $F_{1}-F_{2}+F_{3}-F_{4}+...+F_{2n-1}-F_{2n}=1-F_{2n-1}$ I'm quite ...
1
vote
1answer
153 views

Does my rearrangement of the sequence to prove that - any $n\in\mathbb N$ can be written as the sum of Fibonacci numbers - look fine?

I have this problem in my textbook. I spent many days to come up with the solution. While I'm quite sure about the first part of my proof, I'm unable to verify the second part (which is related to the ...
0
votes
1answer
53 views

Derivation of Fibonacci sequence by difference equation/Z transform

I'm trying to derive the Fibonacci sequence. I have the following problem: $$N(t) = N(t-1)+ N(t-2) \quad \quad \quad \quad (I)$$ With initial conditions $N(1) = 2$ and $N(2) = 3$. Using: $$N(t+2) =...
3
votes
2answers
104 views

Proving $\sum_{j=0}^n (-1)^j {n \choose j} F_{s+2n-2j} = F_{s+n} $, where $F_n$ is the $n$-th Fibonacci number

$$\sum_{j=0}^n (-1)^j {n \choose j} F_{s+2n-2j} = F_{s+n} $$ ($F$ is Fibonacci number). I have been trying to prove this by mathematical induction. First I assume this is true for n. If I ...
0
votes
2answers
58 views

Sum of specific Fibonacci sequence [closed]

This is from problem 20 Is there a simplified expression for sum of Fibonacci numbers: $$F(a)+F(a+4)+F(a+8)+\ldots + F(a+4m)\;\;?$$ https://resources.thiel.edu/mathproject/atps/PDF/Chapt02.PDF It is ...
2
votes
1answer
91 views

Fibonacci-type Sequence with Complex Numbers [duplicate]

I have been playing around with Fibonacci-type of sequence that involve complex numbers. I have stumbled upon the following sequence, which seemed interesting to me: $$0,1,2i,-3,-4i,5,6i,...$$ so $...
0
votes
1answer
75 views

Fibonacci gcd proof

How to prove that gcd of Fibonacci numbers set is $1$, I mean $\gcd(a_{n+1},a_{n})=\gcd(a_{n},a_{n−1})$ because of Euclidean algorithm $\gcd(a_{n+1},a_{n})=\gcd(a_{n},r)$ $r$ - the remainder after ...
6
votes
1answer
75 views

In a mathematical induction, can you prove the “n'th case implies n+1'th case” step by contrapositive?

I'm attempting to prove the first part of Exercise 1.5, in Tom Apostol's Mathematical Analysis, regarding the Fibonacci numbers: The Fibonacci numbers $1, 1, 2, 3, 5, 8, 13 \dots$ are defined by ...
4
votes
1answer
72 views

$p~|~f_{p-1}$ if $p\equiv\pm1$ (mod$10$)

(I edited) Let $\big(f_{n}\big)$ be the Fibonacci sequence which defined by $f_{n}=f_{n-1}+f_{n-2}$ with $f_{1}=1$ and $~f_{2}=1$. Now I have deduced that for all prime $p\ge 7$, either $p~|~f_{p-1}...
3
votes
1answer
88 views

Fibonacci numbers and prime numbers

I'm sorry but I couldn't find anything similar and I don't know how to search my problem so I ask it. I hope that is not duplicate. If we call $n$th element of Fibonacci sequence with $F_n$ and if $p$ ...
1
vote
0answers
34 views

Show that $\{\frac{f_k}{n}\}$ undergoes a cycle, where $\{M\}$ is the fractional part of $M$ and $f_k$ is the $k^\text{th}$ Fibo number [duplicate]

Show that the sequence $\Big<\Big\{\frac{f_k}{n}\Big\}\Big>_{k=1}^\infty$ is periodic, where $\{\mathrm{F}\}$ is the fractional part of $\mathrm F$ and $f_k$ is the $k^\text{th}$ Fibonacci ...
1
vote
1answer
80 views

How can I create new identities with sums?

1. There are a lot of ``simple'' identities like $$ 1+\dotsb+n = \frac{n(n+1)}{2} $$ or $$ 1^2+\dotsb+n^2 = \frac{n(n+1)(2n+1)}{6} $$ 2. Some include Fibonacci numbers, like in Prove Fibonacci ...
1
vote
1answer
39 views

Expected number of tosses to obtain two consecutive heads

I solved it using Recursive method, i.e. $$E=\frac12(E+1)+\frac14(E+2)+\frac14*2$$ Which gave the answer $E=6$ I Also found probablity that it ends in $n$ tosses is $\frac{F_{n-1}}{2^n}$ Thus $$E[X]...
1
vote
1answer
49 views

How Fibonacci sequence works in rabbits problem?

I can't understand the explanation in my textbook. In the following text $f_{n-1}$ is explained as the number on the island the previous month while $f_{n-2}$ is explained as the newborn pairs. But ...
0
votes
0answers
102 views

Generating series for powers of Fibonacci numbers

Denote $(f_n)_n$ the Fibonacci numbers and $(l_n)_n$ the Lucas numbers. The definition is such that $$ \begin{array}{lll} f_0 = 0,& f_1= 1,& f_{n+2}=f_{n+1}+f_n,\\ l_0 = 2,& l_1=1, & ...
1
vote
3answers
58 views

Proving $a_{n+1}^2=a_n·a_{n+2}+(-1)^n$ for Fibonacci sequence $\{a_n\}$ [duplicate]

Let $a_1,a_2,a_3,...,a_n$ be the sequence of Fibonacci numbers. Then we are required to prove by induction that $$a_{n+1}^2=a_n \cdot a_{n+2} + (-1)^n$$ My Attempt: Initially putting a few values ...
0
votes
2answers
43 views

How to approach this question about recursive sequences

Just practicing some questions about sequences and came across the one below The sequence $(F_n)$ of Fibonacci numbers is defined by the recursive relation $F_{n+2} = F_{n+1} + F_n\ $ with $F_1=...
4
votes
1answer
102 views

Leftmost digit of Fibonacci sequence

So, on another math forum, someone posted a question about the leftmost digit of a randomly chosen Fibonacci number. It likely follows Benford's Law for the distribution of the leftmost digit. I know ...
1
vote
3answers
51 views

Even Fibonacci terms

I'm doing a high school level question and one of the questions is figuring out which of the Fibonacci sequence numbers must be even. The 61st, 62nd, 63rd, 64th, or 65th. And the only information I'm ...
4
votes
1answer
76 views

Every $k$th Fibonacci generating function

To get the generating function of $F_n$, I use the basic recurrence $F_n = F_{n-1} + F_{n-2}$. I think the same approach will work for $F_{kn}$. For example, $$F_{2n} = 3F_{2(n-1)} - F_{2(n-2)}$$ $$...
0
votes
1answer
64 views

Generating Function for even and odd Fibonacci Numbers, Missing Steps

I am working through this post:https://math.stackexchange.com/a/787841/283262 and its connected to this one too: Recurrences for even and odd indexed of Fibonacci Numbers I did not get all parts so I ...
0
votes
1answer
50 views

Recurrences for even and odd indexed of Fibonacci Numbers

I have a Recurrence: $$a_{0}=1$$ $$ a_{n}=\sum_{k=0}^{n-1}(n-k)a_{k}$$ I have evaluated some a's:$a_{0}=1, a_{1}=1,a_{2}=3,a_{3}=8,a_{4}=21,a_{5}=55,...$. In the previous exercise on had to derive a ...