Skip to main content

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
35 views

Infinite Fibonacci word generation

I was reading about the Fibonacci sequence and stumbled upon the Fibonacci word. It looks pretty straight forward, but one thing I do not understand. Probably something trivial. According to Wikipedia ...
lbfreak's user avatar
1 vote
0 answers
54 views

Calculate the number of functions $f:\{1;2;\cdots;n\} \to \{0;1;\cdots;n-1\}$

For $n \in \mathbb{N}^*$, calculate the number of functions $f:\{1;2;\cdots;n\} \to \{0;1;\cdots;n-1\}$ such that $f(k) \leq k-1$ for all $k \in \{1;2;\cdots;n\}$, and there do not exist three numbers ...
Math_fun2006's user avatar
0 votes
0 answers
28 views

Linear combinations of solutions to linear recurrences

I am working through MIT's Mathematics for Computer Science through OCW. Currently on homogeneous linear recurrences. A link with the course textbook is attached. My question is with the proof for the ...
Anton Everts's user avatar
0 votes
0 answers
36 views

The Fibonacci sequence: ratio of mature to young rabbit pairs within each generation also converges on the Golden Ratio (online or other reference?)

In looking at the breeding rabbit pair model which lies behind the Fibonacci sequence, one observes that for any given population of A(n) adult pairs (breeding) and Y(n) young pairs (non-breeding) in ...
Jimbo's user avatar
  • 215
0 votes
0 answers
74 views

Why seemingly wrong proof works in proving $\varphi^{n+1} = \varphi \cdot F_{n+1} + F_n$ by induction?

I was reading this post on this site. Which says: Fibonacci Rules: \begin{align*} F_0 = 0 && F_1 = 1 && F_{n+2} = F_n + F_{n+1} \end{align*} Prove, by induction, that $\varphi^{n+1} ...
Etemon's user avatar
  • 6,653
10 votes
0 answers
91 views

Primes of the form $F(a^{k+1})/F(a^k)$

Letting $F(n)$ be the $n$'th Fibonacci number, for what $a$ and $k\ge 1$ is $F(a^{k+1})/F(a^k)$ prime? I know of just $6$ examples: $$\eqalign{ 3 &= F(2^2)/F(2^1)\cr 7 &= F(2^3)/F(2^2)\cr 17 &...
Robert Israel's user avatar
0 votes
1 answer
29 views

Generating function of sequence depending on another sequence

Let $a(n,k) = |${$A ⊂ [n]: |A| = k, A$ does not contain two consecutive elements$}|$ Prove that $a(n,k) = a(n−1,k)+a(n−2,k −1)$ for $k ≥ 2$ and use it to compute the generating function $A_k(x) = \...
comedroidrive's user avatar
2 votes
1 answer
40 views

Is the sequence $1,2,3,5,8,13,21 ...$ (Fib starting with 1,2) a Sidon/$B_2$ sequence

A $B_2$ or a Sidon sequence is a sequence such that all pairwise sums are distinct. For example the sequence 1,2,8,9, is not a B_2 sequence, because $2+8 = 1+9$. I have the feeling such a sequence (1,...
Test Test's user avatar
0 votes
1 answer
63 views

A question about a step in a proof of $\log_{F_{n+1} } F_n < \log_{F_{n+2} }F_{n+1}.$

The question is about this proof. In the proof of case 1, the last two steps are $$\implies (\log F_{n} + \log F_{n+2} - \dfrac{1}{F_n})^2 > 4\log F_n \log F_{n+2}$$ $$\implies (\log F_{n} + \log (...
hbghlyj's user avatar
  • 2,842
3 votes
2 answers
102 views

Why is the difference of consecutive primes from Fibonacci sequence divisible by $4$?

The primes represented in the Fibonacci sequence are written in the form $6n + 1$ and $6n -1$, respectively. $$5=6\times1-1$$ $$13=6\times2+1$$ $$89=6\times15-1$$ $$233=6\times39-1$$ $$1597=6\times266+...
Polona Čuk Kozoderc's user avatar
1 vote
0 answers
23 views

Why does the sum of the set of Fibonacci numbers arranged where the units digit of the nth Fibonacci number is in the (n+1)th place equal 1/89? [duplicate]

If one were to take the Fibonacci numbers and arrange them so that the units digit of the nth Fibonacci number is in the $(n+1)th$ decimal place and sum these numbers up they would get the reciprocal ...
Casie Braden's user avatar
0 votes
3 answers
89 views

Closed form expressions for $T_n$ and $S_n$ of a Fibonacci-like sequence

I am a student curious about recurrence relations who has just bumped into the Intermediate 1st year (grade 11). I derived the closed form expressions for the $n^{th}$ term and the sum of $n$ terms of ...
Yatharth Shrivastava's user avatar
0 votes
0 answers
104 views

Are $144, 233, 377,$ and $17711$ the only Fibonacci Numbers that contains only two different digits(in base ten)?

Are $144, 233, 377,$ and $17711$ the only Fibonacci Numbers that contains only two different digits(in base ten)? I noticed that $144, 233, 377,$ and $17711$ are all Fibonacci Numbers and they contain ...
Thirdy Yabata's user avatar
1 vote
0 answers
44 views

Re-formation of Fibonacci sequence formula

I was doing some question on Fibonacci Sequence and came across this formula $$\large F_n = \frac{\left(\frac{1+\sqrt5}{2}\right)^n - \left(\frac{1-\sqrt5}{2}\right)^n}{\sqrt5}$$ I started thinking “...
user1150809's user avatar
12 votes
0 answers
239 views

Fibonacci but with ratio of sum and difference of the the previous two terms

I have discovered a pretty weird sequence $$a_0=1$$ $$a_1= 2$$ $$a_n=\frac{a_{n-1}+a_{n-2}}{a_{n-1}-a_{n-2}}$$ The first few terms are: $$1,\ 2,\ 3,\ 5,\,\ 4,\ -9,\ \frac{5}{13},\ -\frac{56}{61},\ \...
Bryle Morga's user avatar
2 votes
0 answers
65 views

For every positive integer $m$ there exists a Fibonacci number such that last $m$ digits are $0$ [duplicate]

I proved the claim that for every $m\in\mathbb{Z^+}$ the Fibonacci sequence repeats itself for modulo $m$. But how can I move on and make connections with it to prove that for every $m\in\mathbb{Z^+}$ ...
Elfryionnn's user avatar
1 vote
0 answers
53 views

How come Pisano periods develop this way for$\mod 2^m$?

I came across this fun little math / programming problem. The programming language is Java Now, to shortcut a few things... The n1 = n0 + (n0 = n1)) line affects ...
MichaelK's user avatar
  • 267
0 votes
0 answers
32 views

Is it possible to derive the identity $F_{n+1} = \sum_{k=0}^{n}\binom{n-k}{k}$ from the generating function $F(x) = \frac{x}{(1-x-x^2)}$ [duplicate]

if $F_{n+1}$ is the the $n+1$th Fibonacci number, is it possible to derive the identity $F_{n+1} = \sum_{k=0}^{n}\binom{n-k}{k}$ by using the generating function $F(x) = \frac{x}{(1-x-x^2)}$? The only ...
aroon's user avatar
  • 3
5 votes
1 answer
68 views

sufficient condition for a triangle to exist (and fibonacci numbers)

Let $n\in\mathbb{N}\setminus\{1,2\}.$ Let $a_1,a_2,\ldots,a_n$ be $n$ (not necessarily distinct) real numbers each in the interval $(1,F_n),$ where $F_n$ is the $n^{\text{th}}$ Fibonacci number. Show ...
idk's user avatar
  • 51
4 votes
1 answer
154 views

Find the prime which divides $f(n)+f(n+100)$ terms of Fibonacci sequence.

Let $f(n)$ denote $n$th number in the Fibonacci sequence. Find a two digit prime such that $p$ divides $f(n) + f(n+100)$ for all $n$. Well to be honest I have no idea how to solve this problem so I ...
Anay Gautam's user avatar
0 votes
1 answer
57 views

Tiling Puzzle - ways to tile a 1xn board given coloring restrictions.

This problem has come up in a puzzle I've been trying to solve -- Given a 1xn board and tiles up to 1xn length how many ways can you construct the board. All of the tiles are the same color, let's ...
HG11's user avatar
  • 3
2 votes
0 answers
125 views

Residues in Fibonacci sequence mod p

Let $p$ be prime. For a given residue $k \in \mathbb{Z}_{p}$, check, if exist fibonacci number $F_{n}$, such that $F_{n} \equiv k$ mod $p$. Using the Binet formula, $\frac{\phi^n - \psi^n}{\phi - \psi}...
Vitaliy Volovyk's user avatar
3 votes
1 answer
76 views

Induction Proof for the Sum of the First n Fibonacci Numbers

I'm trying to prove that there exists a formula for the sum of the first n Fibonacci numbers, using induction. $$\sum_{i=1}^{n} F_i$$ For my class, we have denoted the recursive definition of the ...
MattKuehr's user avatar
  • 163
1 vote
1 answer
44 views

Ratio of Fibonacci numbers

I have observed the following property: If $F_n$ denotes the $n^{th}$ Fibonacci number and $F_1=1; F_2=1$ Then $\frac{F_{2n+1}}{F_{2n}}>\phi$ And $\frac{F_{2n}}{F_{2n-1}}<\phi$ For all natural ...
Aarush Saharan's user avatar
0 votes
2 answers
116 views

Can the Fibonacci Spiral be expressed as a polar equation?

Related to this question: can the Fibonacci Spiral be expressed as a polar equation? I know the Golden Spiral can be and the Fibonacci differs in that it uses consecutive arcs of a circle for each ...
Nick's user avatar
  • 1,081
0 votes
1 answer
178 views

Fibonacci Spiral vs Golden Spiral?

I watched this video on constructing the Fibonacci Spiral. Does it differ from the Golden Spiral? The Fibonacci Spiral is constructed by using arcs of a circle on consecutive squares where the ...
Nick's user avatar
  • 1,081
2 votes
0 answers
164 views

Other than $1$, does the sequence $1,12,123,1234,\cdots$ contain a Fibonacci Number?

Other than $1$, does the sequence $1,12,123,1234,\dots$ contain Fibonacci Numbers? This is sequence A007908, and the numbers listed in this sequence is obtained by concatenating the first $n$ ...
Thirdy Yabata's user avatar
0 votes
1 answer
139 views

Why does Lucas get credit for Fibonacci's progression?

A so-called "Lucas Number" is, to me, nothing more than a standard Fibonacci progression of $n_2+n_1$ with a different starting point. There are infinitely many similar progressions, so why ...
mkinson's user avatar
  • 263
1 vote
3 answers
100 views

F(n) is a Fibonacci number. Why do we need two base cases: $n = 3$ and $n = 4$ for the induction to prove $F(n) \geq 2^{(n-1)/2}$ for all $n \geq3?$

F(n) = F(n-1) + F(n-2) is a Fibonacci number(F(1) = 1, F(2) = 1, F(3) = 2 so on...) I wonder why we need two base cases: $n = 3$ and $n = 4$ for the induction to show $F(n) \ge 2^{(n-1)/2} \;\forall ...
Tony's user avatar
  • 11
0 votes
1 answer
2k views

Given a particular starting integer, what negative number should you choose to make the alternating part of the sequence as long as possible?

Start with a positive integer, then choose a negative integer. We’ll use these two numbers to generate a sequence using the following rule: create the next term in the sequence by adding the previous ...
ShegzLP's user avatar
4 votes
1 answer
108 views

Why do the zeros of $\frac{(\phi^z)-(-1/\phi)^z}{\sqrt{5}}$, where $z$ is complex and $\phi$ is the Golden Ratio, appear on a line?

So while messing around with the Binet Formula for the Fibonacci numbers, I decided to input the Complex Numbers into it. And while doing so I noticed something. The Zero's of this sequence are all on ...
NameHereidk's user avatar
4 votes
1 answer
127 views

How can I prove that that $2024!$ cannot be written as product of (not necessarily distinct) Fibonacci Numbers?

How can I prove that $2024!$ cannot be written as product of (not necessarily distinct) Fibonacci Numbers? I know that some factorials can be written as product of different Fibonacci Numbers, such as:...
Thirdy Yabata's user avatar
0 votes
1 answer
77 views

Proof Fibonacci Matrix Proprety by Induction

Statement: Proof by induction for all $n\geq 1$ $$\begin{pmatrix}F_n\\F_{n+1}\end{pmatrix}=\begin{pmatrix}0 & 1\\\ 1 & 1\end{pmatrix}^{n-1}\begin{pmatrix}1\\1\end{pmatrix}$$ I'm know the ...
Alan Maciel's user avatar
2 votes
0 answers
65 views

Is there a Fibonacci Number that is also a Carmichael Number?

Nearly similar to my previous question, is there a Fibonacci Number that is also a Carmichael Number? We all know that for $n$ to be a Carmichael Number, it must be square-free and odd. $F_{n}$ cannot ...
Thirdy Yabata's user avatar
1 vote
2 answers
229 views

Can you prove that $\frac{f_n}{f_{n-1}}$ converges to $2\pi$ and $\frac{1}{2\pi}$ if $f_n=\frac{1}{f_{n-1}}+f_{n-2}$ where $f_0=0$ and $f_1=2$?

I imagine this is already found but I cannot find the proof. The formula also works for $f_1=\sqrt{2}^{1/x}$ to get many multiples of $\pi$ Can you also prove that when $f_1=\sqrt{\frac{2}{\pi}}$ then ...
Joe's user avatar
  • 534
0 votes
1 answer
114 views

Help with a solution this Fibonacci triangle question [closed]

I am currently studying maths at a high school level, I have been given this problem but can’t find any route into it, I have experimented with using Heron’s formula and the expression for the nth ...
RotterAlo's user avatar
0 votes
1 answer
56 views

Synonym for both addition and subtraction

I'm not sure if this is the best place to ask, but will try anyway. Is there a term that can mean either subtraction or addition? I'm working with a program that adds/subtracts up several numbers in ...
spaghettiCoder's user avatar
1 vote
2 answers
113 views

Exponential Fibonacci and its recurrence-relation to ϕ. [closed]

1,1,2,3,5,8,... = Additive Fibonacci: a(n-1) * phi is asymptotic to a(n) 2,2,4,8,32,256,... = Multiplicative Fibonacci a(n)=a(n-1)*a(n-2): a(n-1) ^ phi is asymptotic to a(n) 2,2,4,16,65536,1.158*10^77....
Peter Woodward's user avatar
0 votes
0 answers
70 views

What approach could be taken to prove this property of Fibonacci numbers? [duplicate]

I noticed that starting with Fibonacci numbers 2 and 3, alternating pairs of sequential Fibonacci numbers, fn and fn+1 switch between having fn2=1 (mod fn+1) and having fn2= -1 (mod fn+1). 22=1 (mod 3)...
user1153980's user avatar
  • 1,131
1 vote
1 answer
35 views

A question regarding the divisibility of Fibonacci sequence

Knowing that $F(n)$ is the Fibonacci sequence. The question is to prove that $F(n)$ is divisible by $F(m)$ if $n$ is divisible by $m$. I show my method in the picture below, however, I did not solve ...
Jason Young's user avatar
3 votes
1 answer
128 views

Formally Prove that the Ratio of Fibonacci Numbers is Always Greater than 1.5

Consider the Fibonacci number $1,2,3,5,8,13,21,\cdots.$ It is well known that the limit of the ratio of Fibonacci numbers tends to the Golden Ratio $\phi$. Today, I want to show that $1.5$ is the ...
mathz2003's user avatar
  • 532
4 votes
1 answer
161 views

BMO1 number theory question on fibonacci sequence and divisibility

This is question 2 from the 1983 British Maths Olympaid The fibonacci sequence $f_{n}$ is defined by $f_{1} = 1, f_{2} = 1,$ and $f_{n} = f_{n-1} + f_{n-2}, n > 2$ prove that there are integers a,...
Chris Daniel's user avatar
0 votes
0 answers
49 views

help with Lamé's Theorem (Knuth) induction step

I am trying to prove a part of the therom stating: let $a,b\in \Bbb N$ such that $1 \lt b \lt a$ assume euclidean algorithm takes n steps show that $b\ge F_n$ where $F_n$ is the nth fibonacci number. ...
Gidfuck's user avatar
  • 61
3 votes
0 answers
72 views

Linear clustering when plotting Pisano periods

Recently I saw a video on YouTube where the Fibonacci numbers were studied and around minute 4:20 appears a graph showing the period against the modulus. Something that caught my attention is that ...
Amahury Diaz's user avatar
0 votes
1 answer
139 views

Seeking Literature on Fibonacci-related Patterns in Sequence Operations

Hey fellow math enthusiasts! Problem: The number breaking machine only processes natural numbers. Even numbers are halved, odd numbers are reduced by $1$, e.g. $6\to3$; $5\to4$. Now the result is put ...
Appollonius's user avatar
1 vote
1 answer
181 views

Algebra Problem in Korean Mathematical Olympiad

Let $a_1=5, a_2=25, a_{n+2}=7a_{n+1}-a_n-6$. Prove that $\exists x, y \in \Bbb{Z} $ s.t. $a_{2023}=x^2+y^2.$ Doing some trials and errors, I found that $a_n=(2F_{2n-1})^2+F_{2n}^2$. ($F_n$: Fibonacci ...
RDK's user avatar
  • 2,785
1 vote
2 answers
244 views

The $n$th urinal number is the $(n+1)$th Fibonacci number [duplicate]

This post is inspired by a joke on a meme page which claims/conjectures that the number of "allowed" occupations of $n$ adjacent urinals is the $(n+1)$th Fibonacci number $F(n+1)$. Since it ...
Neckverse Herdman's user avatar
1 vote
0 answers
40 views

How to find the basis for the set of all infinite sequences such that the addition of two terms in a row yields the subsequent term?

Like the question asks, if I have a subspace, F, of $ \mathbb{R}^\mathbb{N}$ (the set of all infinite sequences that follow $(a_1, a_2,...)$) such that the infinite sequence must satisfy $$a_i + a_{i+...
EAO123's user avatar
  • 61
2 votes
3 answers
158 views

how to find the formula for $n$-th Fibonacci numbers ($F_n = \frac{a^n-b^n}{a-b}$) and prove it without induction.

The Fibonacci sequence is defined by the recurrence relation $F_{n+2 } =F_{n+1}+ F_n$ A well-known formula for the n-th Fibonacci number is $F_n = \frac{a^n-b^n}{a-b}$ where $a$ and $b$ are the roots ...
pie's user avatar
  • 5,607
0 votes
2 answers
98 views

Fibonacci like series - determination of 1st and 2nd element

Determining nth value of the Fibonacci series or Fibonacci like series is well known and easy to calculate. Can that be reversed? Can we calculate 1st and 2nd element of the series by giving the value ...
Jacek R.'s user avatar

1
2 3 4 5
44