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

Filter by
Sorted by
Tagged with
0 votes
0 answers
21 views

Hamiltonian paths in a 3 by n grid

The problem states that how many hamiltonian paths are there from the bottom left corner to bottom right corner My guess was some number of the fibonacci sequence but I really go any further any ideas?...
user avatar
0 votes
2 answers
51 views

Proof that $\sum_{n=1}^\infty\frac{F_n}{3^n n} = \frac{\ln(\phi+1)}{\sqrt{5}}$

I conjectured by computation the following, but I’m not sure where to start to prove it. $$\sum_{n=1}^\infty\frac{F_n}{3^n n} = \frac{\ln(\phi+1)}{\sqrt{5}}$$ where $F_n$ are the Fibonacci numbers. I’...
user avatar
  • 3,195
2 votes
2 answers
112 views

Expressing the continued fraction $[k,\dots,k]$ as a closed form

For positive integers $a_1,\dots,a_n\geq 2$, let $[a_1,\dots,a_n]$ denote the continued fraction $$ [a_1,\dots,a_n]=a_1-\frac{1}{a_2-\frac{1}{\cdots-\frac{1}{a_n}}}.$$ Then we have $[2,\dots,2]=(n+1)/...
user avatar
  • 2,034
6 votes
1 answer
52 views

Fibonacci sequences within the Fibonacci sequence recurrence

I'm trying to perform a runtime analysis of the following simple recursive Fibonacci number algorithm: ...
user avatar
  • 75
3 votes
1 answer
62 views

Prove that the number of ways of tiling a $1\times n$ rectangular grid with squares and dominoes is equal to $F_{n+1}$, where $n\geq1$ [closed]

Here $F_n$ refers to the Fibonacci numbers. I know the definition of the Fibonacci numbers and various recurrence relations that they satisfy but I'm not sure how to prove this statement.
user avatar
  • 81
-2 votes
0 answers
91 views

is F a context free language?

is F a context-free language? F = {$0^{F_n}$ | 1 $\le$ n } ={0,00,000,00000,00000000, ...} where $F_n$ are Fibonacci numbers. I think this is not a context-free language. Only way I know how to do it ...
user avatar
  • 55
1 vote
0 answers
39 views

How to prove that $a_{2n} = a_nb_n$ in a Lucas sequence? [duplicate]

Here's the question in in my book: Define $(b_n)$ by $b_1=1$, $b_n = a_{n+1}+a_{n-1}$ for $n ≥ 2$. $(b_n)$ is known as the sequence of Lucas numbers. Prove (i) $b_n = b_{n-1} + b_{n-2}$ for $n ≥ 3$. (...
user avatar
0 votes
1 answer
70 views

Fibonacci squareroot; and r-th root

Define a sequence similar to the Fibonacci sequence: \begin{eqnarray} s(1,r) &=& 0\\ s(2,r) &=& 1\\ s(n,r) &=& \left[ \; s(n-1,r) + s(n-2,r) \; \right]^{1/r} \end{eqnarray} So ...
user avatar
0 votes
0 answers
34 views

What's the intuition of the relation between fibonacci-like sequences and the proportion used to obtain the golden ratio?

Everyone knows that we can obtain the golden ratio from the following proportion: $$\frac{a}{b} = \frac{a+b}{a}$$ We also know that we get ${\phi}^N$ when we try to find a function that satisfies the ...
user avatar
  • 1
0 votes
3 answers
178 views

Evaluating this sum involving Fibonacci numbers: $\frac11 + \frac14+\frac2{16}+\frac3{64}+\frac5{256}+\frac8{1024}+\frac{13}{4096}+\cdots$ [duplicate]

This question was given to me today on a sheet of questions containing 'sum to infinity' questions. There are no hints as to how to solve it. The series is: $$\frac11 + \frac14+\frac2{16}+\frac3{64}+\...
user avatar
1 vote
1 answer
39 views

Fibonacci numbers are O(n), faulty induction

I'm currently working through the Book "Data Structures & Algorithms in Python" by Goodrich et al. in self-study. I have no "profound" mathematics background and am stuck at ...
user avatar
0 votes
1 answer
53 views

Triangle of Fibonacci

I was reading in a book a presentation about the arithmetic triangle of Fibonacci (to me it also looks like the pascal triangle). The figure presented is as follows: The text says: Having arranged ...
user avatar
  • 1,517
0 votes
1 answer
32 views

Find $\sum_{j = 1}^{2004} i^{2004 - F_j}$ where $F_n$ is the nth Fibonacci number

The Fibonacci sequence is defined by $F_1 = F_2 = 1$ and $F_n = F_{n - 1} + F_{n - 2}$ for $n \ge 3.$ Compute $$\displaystyle\sum_{j = 1}^{2004} i^{2004 - F_j}.$$ I tried computing the first few ...
user avatar
0 votes
1 answer
43 views

Reaching Fibonacci $\in O(\phi ^ n)$, without closed form formula

I've been asked to prove that there exists a $c>1$ such that $f(n)=\Theta(c^n)$ with $f$ mapping to a Fibonacci(-esque, $f(1)$ is 1 and not 0) sequence, so $f(1)=1$, $f(2)=1$ and $f(n)=f(n-1)+f(n-2)...
user avatar
  • 425
0 votes
1 answer
39 views

Help with proof regarding Fibonacci sequence?

I have to prove that $$ F_{n}^{2} - F_{n+1}F_{n-1} = (-1)^{n} \;\;\;\;\;\;(n>1)$$ By induction, we can see this is true for $n=2$ (note that the sequence starts with $F_{0} = 1$). When proving the ...
user avatar
5 votes
1 answer
211 views

A pattern of periodic continued fraction

I am interested in the continued fractions which $1$s are consecutive appears. For example, it is the following values. $$ \sqrt{7} = [2;\overline{1,1,1,4}] \\ \sqrt{13} = [3;\overline{1,1,1,1,6}] $$ ...
user avatar
  • 408
2 votes
1 answer
46 views

Rational approximations of the golden ratio: how to prove this limit exists?

Given a positive real number $\alpha$ and a positive rational number $p/q$ in reduced form let's define the quality of $p/q$ as an approximation to $\alpha$ as$$-\log_q|\alpha - p/q|$$ I'm looking at ...
user avatar
1 vote
0 answers
74 views

proof fibonacci sequence is small o(2^n) without using closed formula

I need to prove that for the given fibonacci sequence, with initial values: f(1)=1 f(2)=2 f(n)=f(n-1)+f(n-2) f(n) is belong to small o(2^n). I need to prove it without using the closed formula of ...
user avatar
0 votes
0 answers
40 views

solve the positive integers $(m,n)$ such $(F_{m})^m=((F_{n})^n+1)^2$

Suppose $F_n$ to be the nth term of the Fibonacci sequence.($F_1=F_2=1,F_{n+2}=F_{n+1}+F_n$) (1)Find all duals $(m,n)$, so that $$F_m^m=(F_n^n+1)^2$$. (2)Find all triples $(m,n,t)$, so that $$F_m^m=...
user avatar
0 votes
3 answers
89 views

The sum of Fibonacci numbers $F_{4k}$

Consider the sum, $$\sum_{k=0}^n F_{4k}$$ I would like to find this sum, $F_n$ being the $n$-th Fibonacci number.
user avatar
1 vote
0 answers
32 views

proving that we don’t need more than n bits to represent F(n)

I'm trying to prove that for Fibonacci numbers, we don't need more than n bits to represent F(n), where F(n) is the nth Fibonacci number. For this, I got that the closed-form $F(n) = \frac{\phi^n-(1-\...
user avatar
  • 151
0 votes
1 answer
42 views

infinite sum and equivalence

I'm studying generating functions and I came across the Fibonacci number generating function. Given the Fibonacci succession: $$f_n= \begin{cases} 0 & n=0 \\ 1 &n= 1 \\ f_{n-...
user avatar
0 votes
2 answers
106 views

n+1 th fibonacci term

Hello I was trying to prove $$\sum_{0 \leq k \leq n}^{} \binom{n-k}{k} = \operatorname{Fib}_{n+1}$$ which the approach I made was Prove that it holds for $n=0$, $n=1$. Then use the fact that sum of $...
user avatar
0 votes
1 answer
44 views

Formal proof of convergence of slope of Fibonacci sequence

I am trying to find $n\in \Bbb{N}$ such that $$\forall m\geq n\quad \lvert \frac{F_m}{F_{m-1}} - \phi \rvert < \frac{1}{100}$$ where $F_n$ is the n-th term of the Fibonacci sequence and $\phi = \...
user avatar
2 votes
1 answer
58 views

The probability that no runs of k consecutive heads OR tails will occur in n coin tosses

I am trying to find the probability that no runs of k consecutive heads or tails will occur in n coin tosses. After doing some reading, I found this that shows that the probability that no k ...
user avatar
-2 votes
1 answer
45 views

How do I figure out the sequence of a custom Fibonacci sequence? [closed]

x=1:1 x=2:2 x=3:3 x=4:6 x=5:9 x=6:15 x=7:25 x=8:39 x=9:63 x=10:99 I've tried using the normal Fibonacci sequence although there were always slight small ...
user avatar
1 vote
0 answers
33 views

To prove that the Fibonacci sequence is periodic modulo m for all positive integers m. [duplicate]

So in order to prove this I am asked to first start off by proving fa ≡ fb(mod m) and fa+1 ≡fb+1 (mod m). The question doesn't specify much. I have an idea on how to prove that the residues are ...
user avatar
  • 31
0 votes
0 answers
11 views

Proof of and equality for Fibonacci sequence by induction [duplicate]

The equality This is a question from "Challenge and Thrill of Pre-College Mathematics". I have the base case as 3. I am new to induction so I can't seem to figure out the inductive step. I ...
user avatar
  • 1
0 votes
2 answers
45 views

Compute $p_{n+1} = p^2 \frac{r_1^n-r_2^n}{r_1-r_2}, n \geq 0$

I need to compute $$p_{n+1} = p^2 \frac{r_1^n-r_2^n}{r_1-r_2}, n \geq 0$$ where $p=\frac{1}{2}$, $r_1= \frac{1+\sqrt5}{4}= \frac{1}{2}\varphi$ and $r_2= \frac{1-\sqrt5}{4}$. Using properties of ...
user avatar
2 votes
2 answers
69 views

Linear independence Fibonacci vectors

Let $F_n$ be the usual Fibonacci sequence i.e. with $F_0=0$, $F_1=1$ and $$F_n=F_{n-1}+F_{n-2}$$ I was wondering if the vectors $$\pmatrix{F_n \\ F_{n+1}} \text{ and } \pmatrix{F_{n+2} \\ F_{n+3}}$$ ...
user avatar
  • 996
2 votes
0 answers
41 views

Can we tell from the generating function of the Fibonacci sequence that the generating function of the squared sequence is rational? [duplicate]

The formal power series of the Fibonacci sequence is given by $$ \sum_{n \geq 0} f_nq^n=q+q^2+2q^3+3q^4+5q^5+\cdots $$ whereby $f_n=f_{n-1}+f_{n-2}$ denotes the $n$-th Fibonacci number. Its closed ...
user avatar
  • 1,902
0 votes
0 answers
33 views

Compositions of $n$ where $l$ parts have at least size $k$.

The problem I came up with is the following. Let $n,l,k$ be (non-zero) natural numbers such that $lk\leq n$. Determine the number $N_n(k,l)$ of compositions of $n$ for which at least $l$ parts have ...
user avatar
1 vote
0 answers
78 views

Does a closed form expression of this series exist?

I have a function $y=\frac{1}{x}$. If $x = 1$, then $y = 1$; if $x = 2$, then $y = 0.5$, etc. If I wanted to add the previous term to the current term, I would have $x = 1.5$, $x = 2.167$ etc. The ...
user avatar
  • 11
2 votes
0 answers
117 views

Binet's formula of Fibonacci Sequence

In an attempt to find the $n^{th}$ Fibonacci number by Binet's formula, the derivation of this formula starts by using the quadratic equation $$x^2-x-1 = 0$$ If we try to find roots of this equation ...
user avatar
  • 1,071
0 votes
0 answers
39 views

Binet's Formula for Negative Fibonacci Sequences

I have recently learnt the Binet's formula for calculating Fibonacci Sequences and got my mind blown. $F_n = \frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2^n \sqrt{5}}$ This has worked charm for positive ...
user avatar
1 vote
0 answers
96 views

Closed form of the n-th term of the recurrence relation $x_{n+1}=x_{n}x_{n-1}+x_{n}+x_{n-1}$

Let $x_{n} \in \mathbb Q$ be the n-th term of the recurrence relation $$x_{n+1}=x_{n}x_{n-1}+x_{n}+x_{n-1}\;\;\;\;\;(1)$$ Given a subset $S \subset \mathbb N$, a solution of the relation $(1)$ is $$x_{...
user avatar
5 votes
1 answer
136 views

How to invert Binet's formula for Fibonacci numbers

According to Wikipedia, it is possible to invert Binet's formula for Fibonacci numbers: $$F_n = \frac{\varphi^n-\psi^n}{\varphi-\psi} = \frac{\varphi^n-\psi^n}{\sqrt 5}$$ where $\varphi = \frac{1 + \...
user avatar
  • 455
4 votes
1 answer
94 views

Showing that the Fibonacci's $\binom{n}{k}_F$ is an integer by following the Benjamin-Plot proof

In this paper of A. T. Benjamin and S. S. Plot https://www.fq.math.ca/Papers1/46_47-1/Benjamin_11-08.pdf there's the proof that the following coefficient is an integer: $$\binom{n}{k}_F = \frac{F_nF_{...
user avatar
0 votes
0 answers
29 views

Are there any uses for the Catalan identity?

For the Fibonacci sequence, the Catalan identity is for integers $n>r$, $F_n^2-F_{n-r}F_{n+r}=(-1)^{n-r}F_r^2$. I'm curious as to where knowing this identity for Fibonacci numbers would be useful ...
user avatar
  • 1,073
0 votes
0 answers
29 views

average distance between 2 Delaunay on a Fibonacci spiral

what is the furthest/average distance between 2 Delaunay triangle points on the surface of a Fibonacci spiral/sphere for $N$ points? triangle side length average, $N = 500 \text{ points }$
user avatar
4 votes
1 answer
168 views

If $(3p_n\pm \sqrt{5p_n^2-4})\Delta/(2p_n)$ is an integer then $p_n$ is an odd-indexed Fibonacci number

Suppose $1<p_1<\dots<p_n$ are pairwise relatively prime integers and let $\Delta=p_1\cdots p_n$. In the proof of Lemma 4.8 of this paper (https://arxiv.org/pdf/1606.08656.pdf), there is the ...
user avatar
  • 2,034
0 votes
1 answer
47 views

Equations for half-integer points on generalized complex Fibonacci sequence (metallic mean sequence)

I have been experimenting with generalizing the Fibonacci sequence, and Fibonacci-like "metallic mean" sequences such as the Pell sequence, to non-integer and complex values. The standard, ...
user avatar
  • 751
1 vote
1 answer
59 views

Is there an algorithm to define a recursive function such that consecutive terms approach any arbitrary constant?

The Fibonacci sequence is defined by the recursive function, $f(n)=f(n-1)+f(n-2)$. Consecutive terms in this sequence approach the constant, $\frac{1+\sqrt{5}}{2}$. Is there an algorithm that produces ...
user avatar
0 votes
0 answers
43 views

Proof for nearest Fibonacci number

For all k ≥ 0, since $|\frac{φ^{−k}}{\sqrt{5}}| < \frac{1}{2}$, $F_k = \frac{φ^{k}}{\sqrt{5}} + \frac{φ^{-k}}{\sqrt{5}} = \operatorname{round}(\frac{φ^{k}}{\sqrt{5}})$. So the return value switches ...
user avatar
  • 151
0 votes
1 answer
25 views

Different methods for encoding 3D positions as single number?

The obvious one is modulation/multiplication of each axis by different pitch, or dedicating different bits for each axis (in computer terms) But are there known smarter methods? i.e. normalized ...
user avatar
0 votes
0 answers
29 views

Finite sum of Fibonacci numbers in an arithmetic sequence

Is there a closed form expression for $G(n,k,m)=\sum_{i=0}^{n}F_{ik+m}$ or at least for $G(n,k,1)$? I could find \begin{align} G(n,k,0)&=\frac{F_{nk+k}-(-1)^kF_{nk}-F_k}{L_k-(-1)^k-1}\\\\ &=G(...
user avatar
  • 1
0 votes
0 answers
50 views

Frobenius Number for Fibonacci Numbers

I'm trying to find the Frobenius number for certain groups of Fibonacci numbers, i.e. $g(F_{3n}, F_{3n+3}, F_{3n+k})$, where $n$ is an integer, $k$ is an integer larger than 3 and $g(a_{1}, a_{2}, a_{...
user avatar
0 votes
1 answer
30 views

Equality of two Fibonacci Semigroup

I'm trying to prove that the semigroup $<F_{i}, F_{i+3}, F_{i+3n}>$ is equivalent to the semigroup $<F_{i}, F_{i+3}>$. From my understanding, a numerical semigroup is a specific kind of ...
user avatar
0 votes
1 answer
83 views

GCD of Three Fibonacci Numbers

I'm trying to prove that the $\gcd$ of Fibonacci numbers is $1$, i.e. $\gcd(F_{i}, F_{i+3}, F_{i+k}) = 1$, where $i \neq 0 \pmod 3$. I've tried to combine the formulae of $\gcd(F_{m}, F_{n}) = F_{\...
user avatar
-1 votes
2 answers
81 views

Sum of Fibonacci Numbers in an Arithmetic Sequence [closed]

Let these two be summations of Fibonacci numbers:$$F_{2} + F_{5} + F_{8} + F_{11} + F_{14} +..... + F_{3n-1}=\sum\limits_{n=1} F_{3n-1}$$ and $$F_{0} + F_{3} + F_{6} + F_{9} + F_{12} +..... + F_{3n}=\...
user avatar

1
2 3 4 5
41