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
2answers
21 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
22 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 ...
9
votes
4answers
84 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
27 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
28 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
33 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
74 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
68 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
42 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: $...
0
votes
1answer
13 views

difference equation, LTI system, Z-transform, impulse response

exercises 2 and 3 instructions are in picture Here is a z-table that I can use to make inverse z-transforms I did questions 2a and 2b, but I don't know much about how to do the final 2c (I got stuck ...
7
votes
2answers
103 views

Sequence in which adding 2 produces a square

Consider the sequence defined by $x_1=2$, $x_2=x_3=7$, $x_{n+1}=x_{n}x_{n-1}-x_{n-2}$. Then $x_4=7 \cdot 7 - 2 = 47, x_5=47 \cdot 7 - 7=322, x_6=322 \cdot 47 - 7 =15127, x_7=15127 \cdot 322 -47=...
0
votes
1answer
24 views

Show that $F^2_{n+2} – F^2_{n-2}$ is not a multiple of a Fibonacci number.

For $F_n$ as n-th Fibonacci number, I tried for a few first numbers $n=2,3,4,5$ the numerical value of $F^2_{n+2} – F^2_{n-2}$. Unlike the previous exercises of the book, when the r.h.s. was another ...
6
votes
4answers
97 views

Does $a_{n}/a_{n-1}$ converge to the golden ratio for all Fibonacci-like sequences?

Yesterday a friend challenged me to prove that $$\lim_{n\rightarrow\infty}\frac{a_n}{a_{n-1}}=\varphi\; ,$$ where $\varphi$ is the golden ratio, for the Fibonacci series. I started rewriting the ...
1
vote
3answers
65 views

Proof of a Well-Known Fibonacci Identity Involving Cubes of Fibonacci Numbers

The following is due to Lucas in 1876: $$F_{n + 1}^3 + F_n^3 - F_{n - 1}^3 = F_{3n}$$ I am unable to locate an elementary proof of this identity, and am unable to reproduce it myself. Would anyone ...
0
votes
1answer
34 views

Prove the Fibonacci Sequence by induction (Sigma F2i+1)=F2n

Prove the following by using mathematical induction. The Fibonacci sequence is defined as a recursive equation: $F_{1}=1$;$F_{2}=1$; and $F_{k}$=$F_{k-1}$+$F_{k-2}$. For all n∈N, the Fibonacci ...
10
votes
0answers
130 views

A conjecture about the connection between a Penrose tiling and the Fibonacci word fractal

Consider the Penrose tiling $P3$, inflated up to $6$ generations: We draw a line passing through the center of the tiling (red dot) and the outer vertex of the rightmost starting tile (black dot). ...
0
votes
1answer
39 views

Why $\frac{F_{n+2}}{F_{n+1}}=1+\frac{F_n}{F_{n+1}}$?

Why $\frac{F_{n+2}}{F_{n+1}}=1+\frac{F_n}{F_{n+1}}$ (seems to) hold for every fibonacci number $F_n$?
0
votes
0answers
18 views

Issues developing Fibonacci Search algorithm with R.

[edited] I compiled this code for an Operations Research class. I ended up submitting another format that relied on R packages; however, I feel that I am close to a functioning algorithm. I ...
1
vote
1answer
40 views

Fibonacci induction

The question requires strong induction. Prove that a sum of a set of Fibonacci numbers can represent any natural number n. For example, 49 is the sum of a set (34, 13, 2) of Fibonacci numbers. I ...
1
vote
2answers
48 views

How do we use the hint to show the divisibility?

I want to show that if $m=n^{13}-n$ and $n>1$ then $30290 \mid F_m$. (Hint: Show first that $a^{13} \equiv a \mod{2730}$.) $F_m$ is the $m$-th Fibonacci number. I have shown the hint as follows: ...
0
votes
0answers
18 views

Proof for $\forall n \in \mathbb {Z^{+}} f_n \geq (\frac{3}{2})^{n-2}$

I've written the following proof to prove the above identity. Have I done this right? Any tips would be appreciated. Let S(n) be $f_n \geq (\frac{3}{2})^{n-2}$. I will define the Fibonacci numbers as ...
2
votes
0answers
45 views

Does some Lucas sequence contain infinitely many primes?

Does some nontrivial Lucas sequence contain infinitely many primes? The Mersenne numbers $M_n=2^n-1:n$ not necessarily prime are a Lucas sequence with recurrence relation $x_{n+1}=2x_n+1$. It's an ...
0
votes
0answers
13 views

Why does the Euclidean Algorithm on naturals a, b <= fib(n) have a steps <= (n-2)

I have heard that the worst case for the euclidian algorithm is in the case of Fibonacci numbers. Can this be proven, and can it be proven only n-2 divisions are required (where euclidian algorithm is ...
0
votes
1answer
67 views

Is the Fibonacci sequence exponential?

I could not find any information on this online so I thought I'd make a question about this. If we take the Fibonacci sequence $F_n = F_{n-1} + F_{n-2}$, is this growing exponentially? Or perhaps if ...
0
votes
0answers
193 views

Strong induction. Fibonacci numbers

Using Strong Induction, prove that the (n + 3)-rd Fibonacci number can be computed as 1 plus the sum of the first n + 1 Fibonacci numbers (remember n includes 0). so it has to be proven by Strong ...
0
votes
1answer
30 views

Show the given property about divisibility

I want to show that if $m \geq 1, n \geq 1$ and $gcd(m,n)=1$, then $F_m F_n \mid F_{mn}$. $F_n$ is the $n$-th Fibonacci number. I have tried the following so far: $$F_{mn}=F_{mn-1}+F_{mn-2}=2F_{mn-...
0
votes
1answer
38 views

The intuition behind recursive math formula's

I am working on a problem case to try gaining more intuition behind recursion and mathematical formula's. I understand how to solve the case by using code and recursion. However, I find the ...
3
votes
4answers
68 views

If $2 \mid F_n$, then $4 \mid F_{n+1}^2-F_{n-1}^2$, where $F_n$ is $n$-th Fibonacci number

I want to show that If $2 \mid F_n$, then $4 \mid F_{n+1}^2-F_{n-1}^2$ If $3 \mid F_n$, then $9 \mid F_{n+1}^3-F_{n-1}^3$ where $F_n$ is the $n$-th Fibonacci number. I have tried ...
2
votes
3answers
152 views

Show that for each $n \geq 1$ it holds that $2^{n-1} F_n \equiv n \pmod{5}$

I want to show that for each $n \geq 1$ it holds that: $$2^{n-1} F_n \equiv n \pmod{5}$$ where $F_n$ is the $n$-th Fibonacci number. Could you give a hint how we can show this? The sequence $F_n$ ...
2
votes
2answers
30 views

How to prove Fibonacci recurrence holds mod p?

Let $$J_n \equiv c^{-1} \Big( \Big( \dfrac{1+c}{2} \Big)^n - \Big( \dfrac{1-c}{2} \Big)^n \Big) \ \text{(mod p)},$$ with $c$ and $c^{-1}$ integers such that $c^2 \equiv 5 \ \text{(mod p)}$ and $cc^{-...
1
vote
3answers
46 views

Prove $\sum^{k}_{i=0}{F(i)} + 1 = F(k+2)$ without induction

I want to prove that $\sum^{k}_{i=0}{F(i)} + 1 = F(k+2)$, where $F(0) = 0$, $F(1) = 1$ and for all $n \geq 2$, $F(n) = F(n-1) + F(n-2)$ without using induction. I want to prove it without induction ...
0
votes
0answers
20 views

Fibonacci sequence from natural numbers

Is there a manipulation that can be performed on the natural number sequence (1,2,3,...) in order to give the Fibonacci sequence? I know the recurrence relation starting from 1,1 and successively ...
1
vote
2answers
32 views

Find all possible to ways to reach a point $N$ meters away using steps that are of lengths 1 meter or 2 meters.

Find all possible to ways to reach a point $N$ meters away in only 2 possible steps that are of 1 meter and 2 meter respectively. Now let me illustrate using an example: Let the point be 4 meters ...
1
vote
2answers
65 views

Log Fibonacci = Theta [duplicate]

I'm trying to prove that $\log F_n = Θ(n)$ and where $$F_n = F_{n-1} + F_{n-2}$$ $F_1 = 1$, $F_0 = 0$ There's already a thread about this question, but the accepted answer doesn't explain a ...
1
vote
2answers
75 views

Show that log $Fib_{n}$ is $\theta(n)$

I need to show log $Fib_{n}$ is $\theta(n)$ by the Fibonacci numbers defined as $$ F_n=F_{n-1}+F_{n-2}$$ for $$ n \geq 2 $$ $ F_{0} = 0 $ and $ F_{1} = 1 $ I'm not sure how to approach this. I ...
1
vote
2answers
51 views

Prove by induction that $Fib_{n} \geq (3/2)^{n-1}$

I need help with the last inductive steps, can someone help? I hope my formatting is good enough, first time here. The case: "Let the fibonacci sequence be recursivly defined so that $$F_0 = 0, F_1 ...
2
votes
3answers
27 views

Fibonacci Numbers and Linear Recurrences

Today while doing this topic our professor gave an example with tiles. The example: There are 2 kinds of tiles, A= 1 x 1 and B= 2 x 1. In how many ways can you arrange tiles in a line n units long? ...
0
votes
1answer
16 views

fibonacci seq. in an array of size n of 2 states {a,b} where no 2 a's can be congruent

I've recently been given this task: there is an array of $n$ binary states, $\{a,b\}$ (for example $n=5$, $aabba$). For given $n$, compute the amount of possible such arrays where there are no 2 ...
2
votes
0answers
38 views

Induction on Fibonacci numbers

For a homework problem, I need to prove $f_0f_1+f_1f_2+...+f_{2n-1}f_{2n}=f_{2n}^2$ for $n\geq1$ with induction. So far, using my basis step, I have $$\sum_{i=1}^{k+1} f_{2(k+1)-1}f_{2(k+1)}=$$ $$\...
0
votes
0answers
16 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 ...
1
vote
1answer
57 views

Fibonacci-type Sequence Problem [closed]

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
43 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
165 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
42 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
1answer
24 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
75 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
42 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
55 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$...