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

learn more… | top users | synonyms

1
vote
1answer
66 views

Proof that golden angle successively divides the largest gap by the golden ratio?

The golden angle divides the circumference of a circle by the golden ratio. "If radial spokes are placed successively into the circle, each spaced by a golden angle increment, then each additional ...
30
votes
4answers
579 views
1
vote
4answers
190 views

Determine which Fibonacci numbers are even

(a) Determine which Fibonacci numbers are even. Use a form of mathematical induction to prove your conjecture. (b) Determine which Fibonacci numbers are divisible by 3. Use a form of mathematical ...
1
vote
4answers
47 views

Help understanding Recursive algorithm question

We have a function that is defined recursively by $f(0)=f_0$, $f(1)=f_1$ and $f(n+2) = f(n)+f(n+1)$ for $n\geq0$ For $n\geq0$, let $c(n)$ be the total number of additions for calculating $f(n)$ ...
2
votes
1answer
57 views

What's the Lucas version of the Möbius test for Fibonacci numbers?

I recently came across the following, attributed to Möbius: $$(a\in\mathbb N)=F_n\iff\left[\varphi a-\tfrac{1}{a},\varphi a+\tfrac{1}{a}\right]\ni(b\in\mathbb N)$$ It is the lesser-known test used to ...
1
vote
1answer
34 views

What is the Lucas counterpart to the Fibonacci identity $5F_n^2\pm~4=\lambda^2$?

It's a well-known rule that a number $x$ belongs to the Fibonnaci Sequence iff: $$\begin{align}5x^2\pm~4&=\lambda^2&\lambda\in\mathbb Z\end{align}$$ In other words, if and only if $5x^2\pm~4$ ...
1
vote
1answer
46 views

Looking for a sum 1/(Fib(n)*Fib(n+2))

I am looking for the sum of the series: $$\sum_{n=1}^{\infty}\frac{1}{F_{n}F_{n+2}},$$ where $F_{n}$ is the $n$-th Fibonacci number. I was thinking about splitting the fraction into 2 like in the ...
1
vote
2answers
59 views

Compute $F_{1000} \bmod F_{11}$, where $F_n$ denote the Fibonacci numbers

Compute $F_{1000} \bmod F_{11}$, where $F_n$ denote the Fibonacci numbers. Progress: $F_{11}=89$ . I believe you should find the period of $F_n \bmod 89$ and use that to solve it. But I'm not not ...
0
votes
1answer
37 views

finding $n$ consecutive composite Fibonacci numbers.

For each $n$, How can we find $n$ consecutive composite Fibonacci numbers?
2
votes
3answers
97 views

Is it true that $5^k \mid f(5^k)$?

I guess if it is true that $5^k \mid f(5^k)$, where $f(n)$ denotes the $n$-th Fibonacci's number. I have tried to prove it by induction on $k$, but nothing. Have you got any ideas?
2
votes
1answer
37 views

Is a Lucas Number with either a power of 2 or a prime index always coprime with all previous Lucas Numbers?

I was looking at this webpage which lists the first 200 Lucas Numbers color-coded with their prime factors and I noticed that all the Lucas numbers with power of two or prime indexes were relatively ...
1
vote
1answer
70 views

Compute $F_{1000} \bmod 1001$, where $F_n$ denote the Fibonacci numbers

Compute $F_{1000} \bmod 1001$, where $F_n$ denote the Fibonacci numbers. I have tried using the fact that $F_{n^k} \bmod F_n = 0, k=1,2,3,...$ but that doesn't get me anywhere. Thanks!
3
votes
0answers
54 views

Are $1$ and $3$ the only numbers of the form $2^n-1$ that exist in the Fibonacci sequence? [duplicate]

Are $1$ and $3$ the only numbers of the form $2^n-1$ that exist in the Fibonacci sequence? Then, if they are not the only ones, are there infinite cases? I have tried finding another example using a ...
0
votes
1answer
66 views

Function relating Euler's constant and the golden ratio

Okay, I was messing around on Excel with some coefficients and I stumbled onto this. Not sure if it converges but it gets pretty damn close around the 1024th term mark. Was wondering if somebody could ...
0
votes
1answer
42 views

Help with a proof involving Fibonacci numbers.

I'm working through SICP MIT course, and I'm a little lost on how to prove the following statement. I think I'm able to demonstrate it, but have no idea how to prove this statement. I may ...
1
vote
2answers
112 views

Non integer Fibonacci numbers

I'm pretty sure we're all familiar with the Fibonacci sequence. Most people with more than passing knowledge of this most marvelous gem are aware of the Binet formula, $Fib(n) = (\varphi^n - ...
8
votes
2answers
268 views

Interpolated Fibonacci numbers - real or complex?

The common Binet-formula for the Fibonacci-numbers $$ f_n = {\varphi^n- (1-\varphi)^n \over \sqrt 5 } \small {\qquad \qquad \text{ where }\varphi={1+\sqrt 5\over 2}}$$ allows interpolation to ...
1
vote
2answers
99 views

How many $a$-nary sequences of length $b$ never have $c$ consecutive occurrences of a digit?

Let $S(a,b,c): = \#\{a$-nary sequences of length $b$ without $c$ consecutive occurrences of a digit$\}$. For example, $S(2,n,3)$ would be the number of binary sequences of length $n$ without $3$ ...
-3
votes
2answers
957 views

Expressing Fibonacci numbers as the sum of squares.

As we know that by observation, the Fibonacci numbers ($F_0=0$, $F_1=1$, $F_{n}=F_{n-1}+F_{n-2}$) have the identity $$F_{2k+1}=F_k^2 + F_{k+1}^2.$$ In particular, if $n$ is odd, then $F_n$ is a sum of ...
2
votes
2answers
85 views

Fibonacci combinatorial identity

Can someone explain how to prove the following identity involving Fibonacci sequence $F_n$ $F_{2n} = {n \choose 0} F_0 + {n\choose 1} F_1 + ... {n\choose n} F_n$ ?
8
votes
3answers
134 views

Asking About Binomial Sum Related to Fibonacci

How would I prove $$ \sum\limits_{i,j\ge 0} {n-i \choose j} {n-j \choose i}=F_{2n+1} $$ where $n$ is a nonnegative integer and $\{F_n\}_{n\ge 0}$ is a sequence of Fibonacci numbers? Thank you very ...
1
vote
1answer
73 views

Does this mean some Wall-Sun-Sun primes have already been found?

In the PrimeGrid project statistics page for Wall-Sun-Sun Prime Search, it says, Wall-Sun-Suns ... 2 Near Wall-Sun-Suns ... 208 However, all the internet search ...
2
votes
0answers
66 views

Fibonacci applied to human population living to dead ratio problem

If this forum is not the right one for my question, please redirect it. I do not know where to ask it. The question might seem tongue-in-cheek, believe me it's not! Last week to occupy my mind, I ...
1
vote
2answers
57 views

Help with a proof I can't quite

Let $(F_j)^\infty_{j=1}$ be the sequence of Fibonacci numbers. For all $n \in \mathbb{N}$, $\sum\limits_{k=1}^{2n-1}F_kF_{k+1}=(F_{2n})^2$. I handled the base case quite well but couldn't go very ...
3
votes
1answer
146 views

Magic Squares with Lucas and Fibonacci Numbers

I am quite curious about can we construct magic squares using only Lucas and Fibonacci numbers(of course not repeating them? If yes, how can we construct them? And if not , what is the proof?
0
votes
1answer
30 views

Inequality of Lucas Numbers

Can it be shown that \begin{align} \frac{1}{\ln(1+L_{n}) -1} \geq \frac{L_{n}}{(L_{n}-1)(e^{L_{n}}-1)} \end{align} where $L_{n}$ is the $n^{th}$ Lucas number. Show results in full detail.
1
vote
0answers
79 views

Linear combination of numbers: Express the $n^{th}$ Fibonacci number in terms of known constants.

Given the concept that any number can be expressed as a combination of other numbers can the $n^{th}$ Fibonacci number be expressed in terms of $\zeta(3)$ and $\ln(2/e)$ ? If possible, show all work ...
4
votes
2answers
468 views

Number of Fibonacci numbers in a range

The definition of the Fibonacci numbers is given by: $$\begin{align}f_1 &= 1;\\ f_2 &= 2;\\ f_n &= f_{n-1} + f_{n-2},\qquad (n >= 3); \end{align}$$ now we are given two numbers $a$ ...
1
vote
4answers
110 views

Summation of Fibonacci numbers $F_n$ with $n$ odd vs. even

Compare the summation below: $$\begin{align} \smash[b]{\sum_{i=1}^n F_{2i-1}}&=F_1+F_3+F_5+\cdots+F_{2n-1}\\ &=1+2+5+\cdots+F_{2n-1}\\ &=F_{2n}\\ \end{align} $$ with this one: ...
3
votes
1answer
98 views

Using matrices to calculate fibonacci?

I have been told a couple of times it possible to calculate the fibonacci sequence much quicker using matrices but I never understood/they never elaborated. Would somebody be able to show how this ...
3
votes
2answers
152 views

Check if the number is a result of multiplying two fibonacci numbers

Is there a way to check if a given number is a result of multiplication of two fibonacci numbers? Any theory/characteristics allowing to quickly decline some of these given numbers?
5
votes
2answers
983 views

How to prove Fibonacci sequence with matrices?

How do you prove that: $$ \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n\\ F_{n} & F_{n-1} \end{pmatrix}$$
0
votes
0answers
25 views

Fibonacci binary (only 1's and 0's) how to get it

i know what fibonacci numbers are $ F_{n+2}=F_{n+1}+F_{n} $ but what is the case of fibonacci binary string which has only 1 and 0 ? how could i get this string :D is just taking the fibonacci ...
1
vote
1answer
62 views

Question on Proof that the Fibonacci Word is Sturmian

I am currently reading a text where it is proved that the infinite Fibonacci Word $u$ defined as the limit of the sequence $$ u_n = \varphi^n(0) $$ where the morphism is given by $\varphi(0) = 01, ...
1
vote
2answers
286 views

Modular Fibonacci series

My second observation is the following. Let $p$ be a prime not equal to $5$. Then $5$ is a quadratic residue modulo $p$ if and only if $p\equiv\pm1\pmod5$. And $5$ is not a quadratic residue modulo ...
0
votes
0answers
23 views

Relation between series and equations

There is following quotes from wiki on Plastic number: The powers of the plastic number $A(n) = ρ^n$ satisfy the recurrence relation $A(n) = A(n − 2) + A(n − 3)$ for $n > 2$. And 2nd is that ...
1
vote
3answers
120 views

How to go about solving this recurrence relation?

In my discrete math class we were given the problem of finding an explicit formula for this recurrence relation and proving its correctness via induction. $$a_n=2a_{n-1}+a_{n-2}+1, a_1 = 1, a_2=1.$$ I ...
2
votes
4answers
6k views

Help with Induction proof on Fibonacci sequence?

I can't seem to solve this problem. It is: The Fibonacci numbers $F(0), F(1), F(2),\dots $ are defined as follows: $F(0) ::= 0$ $F(1) ::= 1$ $F(n) ::= F(n-1) + F(n-2)\qquad(\forall n \ge 2 $) ...
3
votes
0answers
76 views

Fibonacci Quadratic Residue

After some research I have came up with a conjecture on fibonacci quadtratic residue: ...
0
votes
1answer
32 views

Factoring for Strong Induction for Fibonacci Sequence

Fibonacci: prove the following theorem: define the Fibonacci sequence $\left\{ a_n\right\}_{n=0}^{\infty}$ by $a_0=a_1=1$ and for integers $k>1$, $a_k=a_{k-1}+a_{k-2}$. Then, for each integer $n$, ...
3
votes
2answers
104 views

Successively longer sums of consecutive Fibonacci numbers: pattern?

Consider the following: $$\begin{align} F_{n-1}+F_{n-2}&=F_n\\ F_{n-1}+F_{n-2}+F_{n-3}&=F_{n-1}+F_{n-1}\\ &=2F_{n-1}\\ F_{n-1}+F_{n-2}+F_{n-3}+F_{n-4}&=F_n+F_{n-2}\\ &=L_{n-1}\\ ...
0
votes
1answer
47 views

Understanding Recursive algorithm using FIB

I am studying for an exam, and I came across this question, I think I got the answer correct, just need some validation. ...
2
votes
0answers
57 views

Could Fibonacci numbers be related to Riemann zeros?

this is my question can tghe fibonacci numbers $$ F_{n+2} =F_{n+1} +F_{n} $$ be related to the zeros of the Riemann zeta function ?? i heard that in the webpage ...
1
vote
4answers
73 views

Remainder of a high fibonacci number

I found a question in my assessment book: What is the remainder when the 1995th number of the fibonacci sequence is divided by 8? How to solve?
3
votes
3answers
255 views

Fibonacci Sequence, Golden Ratio

I've been asked to show that $x_n \rightarrow L$ as $n \rightarrow \infty$ where $x_n = F_{n+1}/F_{n}$ for $n \in \mathbb{Z}^+$, where $F_n$ denotes the $n^{th}$ Fibonacci number. I am supposed to use ...
7
votes
1answer
749 views

Proof by induction on Fibonacci numbers: show that $f_n\mid f_{2n}$

I was studying Mathematical Induction when I came across the following problem: The Fibonacci numbers are the sequence of numbers defined by the linear recurrence equation- $f_n = f_{n-1} + ...
4
votes
2answers
203 views

Fibonacci using proof by induction: $\sum_{i=1}^{n-2}F_i=F_n-2$

everyone. I have been assigned an induction problem which requires me to use induction with the Fibonacci sequence. The summation states: $$\sum_{i=1}^{n-2}F_i=F_n-2\;,$$ with $F_0=F_1=1$. I ...
5
votes
3answers
981 views

Fibonacci trick and proving it. [duplicate]

I am trying to learn Fibonacci tricks and I have one that I can not prove. I know it works because Ive tried it multiple times but I have not a clue how to prove. Here it is: ...
3
votes
1answer
81 views

Question about generating function of kind of fibonacci partial sum

$F_n$ here is $n$-th fibonacci number We know that $$\sum_{n=0}^\infty \left(\sum_{k=0}^n F_kF_{n-k}\right)x^n$$ is a generating function of multiplying two G.F: $a_n =\langle F_n \rangle$ and $b_n = ...
0
votes
2answers
69 views

Interesting a Fibonacci quesiton. Need help.

Alice claims that she knows another formula for the Fibonacci numbers: Fn = $e^{n/2−1}$ for $n = 1,2,\cdots$ (where $e = 2.718281828$... is, naturally, the base of the natural logarithm). Is she ...