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

47
votes
1answer
3k views

Quadratic reciprocity via generalized Fibonacci numbers?

This is a pet idea of mine which I thought I'd share. Fix a prime $q$ congruent to $1 \bmod 4$ and define a sequence $F_n$ by $F_0 = 0, F_1 = 1$, and $\displaystyle F_{n+2} = F_{n+1} + \frac{q-1}{4} ...
45
votes
4answers
3k views

Fibonacci number that ends with 2014 zeros?

This problem is giving me the hardest time: Prove or disprove that there is a Fibonacci number that ends with 2014 zeros. I tried mathematical induction (for stronger statement that claims that ...
41
votes
5answers
4k views

Does every prime divide some Fibonacci number?

I am tring to show that $\forall a \in \Bbb P\; \exists n\in\Bbb N : a|F_n$, where $F$ is the fibonacci sequence defined as $\{F_n\}:F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$ $(n=2,3,...)$. How can ...
35
votes
7answers
3k views

Project Euler, Problem #25

Problem #25 from Project Euler asks: What is the first term in the Fibonacci sequence to contain 1000 digits? The brute force way of solving this is by simply telling the computer to generate ...
33
votes
4answers
800 views

Conjecture: There's only one Fibonacci number that is the sum of two cubes

As the title says, I need help proving or disproving that there is only one Fibonacci number that's the sum of two (positive) cubes, $2$. I did a small brute force test with Fibonacci numbers below ...
30
votes
3answers
615 views

Very curious properties of ordered partitions relating to Fibonacci numbers

I came across some interesting propositions in some calculations I did and I was wondering if someone would be so kind as to provide some explanations of these phenomenon. We call an ordered ...
28
votes
4answers
554 views

Fibonacci numbers from $998999$

Is there a nice explanation of ...
28
votes
5answers
8k views

Checking if a number is a Fibonacci or not?

The standard way (other than generating up to $N$) is to check if $(5N^2 + 4)$ or $(5N^2 - 4)$ is a perfect square. What is the mathematical logic behind this? Also, is there any other way for ...
26
votes
2answers
1k views

Why do some Fibonacci numbers appear in an approximation for $e^{\pi\sqrt{163}}$?

It is rather well-known that, $e^{\pi\sqrt{43}} \approx 960^3 + 743.999\ldots$ $e^{\pi\sqrt{67}} \approx 5280^3 + 743.99999\ldots$ $e^{\pi\sqrt{163}} \approx 640320^3 + 743.999999999999\ldots$ Not ...
21
votes
7answers
899 views

How are we able to calculate specific numbers in the Fibonacci Sequence?

I was reading up on the Fibonacci Sequence when I've noticed some were able to calculate specific numbers. So far I've only figured out creating an array and counting to the value, which is incredibly ...
20
votes
1answer
315 views

The Fibonacci sum $\sum_{n=0}^\infty \frac{1}{F_{2^n}}$ generalized

The evaluation, $$\sum_{n=0}^\infty \frac{1}{F_{2^n}}=\frac{7-\sqrt{5}}{2}=\left(\frac{1-\sqrt{5}}{2}\right)^3+\left(\frac{1+\sqrt{5}}{2}\right)^2$$ was recently asked in a post by Chris here. I ...
15
votes
16answers
6k views

Applications of the Fibonacci sequence

The Fibonacci sequence is very well known, and is often explained with a story about how many rabbits there are after $n$ generations if they each produce a new pair every generation. Is there any ...
15
votes
1answer
6k views

Prove that two any consecutive terms of Fibonacci sequence are relatively prime

Prove that two any consecutive terms of Fibonacci sequence are relatively prime My attempt: We have $f_1 = 1, f_2 = 1, f_3 = 2...$. So obviously $\gcd(f1, f2) = 1$. Suppose that $\gcd(f_n, ...
14
votes
1answer
1k views

Combinatorial proof of a Fibonacci identity: $n F_1 + (n-1)F_2 + \cdots + F_n = F_{n+4} - n - 3.$

Does anyone know a combinatorial proof of the following identity, where $F_n$ is the $n$th Fibonacci number? $$n F_1 + (n-1)F_2 + \cdots + F_n = F_{n+4} - n - 3$$ It's not in the place I thought it ...
14
votes
1answer
247 views

Fibonacci Sequence in $\mathbb Z_n$.

Consider a Fibonacci sequence, except in $\mathbb Z_n$ instead of $\mathbb Z$: $$F(1) = F(2) = 1$$ $$F(n+2) = F(n+1) + F(n)$$ It is easy to see that each of these sequences must cycle through some ...
13
votes
3answers
654 views

Prove the Fibonacci sum $\sum \limits_{n=0}^{\infty}\frac{F_n}{p^n} = \frac{p}{p^2-p-1}$

We are familiar with the nifty fact that given the Fibonacci series $F_n = 0, 1, 1, 2, 3, 5, 8,\dots$ then $0.0112358\dots\approx 1/89$. In fact, $$\sum_{n=0}^{\infty}\frac{F_n}{10^n} = ...
13
votes
2answers
540 views

Fibonacci[n]-1 is always composite for n>6. why?

In[11]:= Select[Table[Fibonacci[n], {n, 1, 10000}], PrimeQ[# - 1] &] Out[11]= {3, 8} Edit: Fibonacci[n]-1 is always composite for n>6. why? $$\sum\limits_{i = 0}^n {{F_i}} = {F_{n + 2}} - 1$$ ...
13
votes
4answers
357 views

Converting recursive equations into matrices

How do we convert recursive equations into matrix forms? For instance, consider this recursive equation(Fibonacci Series): $$F_n = F_{n-1} + F_{n-2}$$ And it comes out to be that the following that ...
12
votes
2answers
295 views

Generalized Fibonacci Sequence Question

The Fibonacci Sequence is defined as the recurrence $a(n)=a_{n-1}+a_{n-2}$ where $a(0)=0$ and $a(1)=1$. Today, I was bored so I considered the sequence $a(n)=\sqrt{a_{n-1}}+\sqrt{a_{n-2}}$. Ten ...
11
votes
8answers
1k views

Showing that an equation holds true with a Fibonacci sequence: $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$

Question: Let $F_n$ the sequence of Fibonacci numbers, given by $F_0 = 0, F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$. Show for $n, m \in \mathbb{N}$: $$F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$$ ...
11
votes
1answer
341 views

Why does $\frac{1 }{ 99989999}$ generate the Fibonacci sequence?

$\frac{1}{99989999} = 1.00010002000300050008001300210034005500890144... \times 10^{-8}$ (Link), which includes the Fibonacci sequence $(1\ 1\ 2\ 3\ 5\ 8\ 13\ 21\ 55\ 89\ 144\ \ldots )$ This is ...
11
votes
4answers
4k views

The generating function for the Fibonacci numbers

Prove that $$1+z+2z^2+3z^3+5z^4+8z^5+13z^6+...=\frac{1}{1-(z+z^2)}$$ The coefficients are Fibonacci numbers $\left\{1,1,3,5,8,13,21,...\right\}$.
11
votes
5answers
1k views

How to tell if a Fibonacci number has an even or odd index

Given only $F_n$, that is the $n$th term of the Fibonacci sequence, how can you tell if $n \equiv 1 \mod 2$ or $n \equiv 0 \mod 2$? I know you can use the Pisano period, however if $n \equiv 1$ or ...
11
votes
1answer
297 views

Why do the Fibonacci numbers recycle these formulas?

The Fibonacci numbers $F_n = 0, 1, 1, 2, 3, 5, 8, 13, \dots$ obey the following recurrence relations, $ \begin{aligned} &F_{n}-\;F_{n-1}-F_{n-2} = 0\\[1.5mm] &F_{n-1}^3-F_{n}^3-F_{n+1}^3 = ...
10
votes
4answers
3k views

Why does the Fibonacci Series start with 0, 1?

The Fibonacci Series is based on the principle that the succeeding number is the sum of the previous two numbers. Then how is it logical to start with a 0? Shouldn't it start with 1 directly?
10
votes
3answers
242 views

Evaluate the sum: $\sum\limits_{n=0}^{\infty} \frac1{F_{(2^n)}}$

Evaluate the sum: $$\sum_{n=0}^{\infty} \frac{1}{F_{(2^n)}}$$ where $F_{m}$ is the $m$-th term of the Fibonacci sequence. I need some support here. Thanks.
10
votes
4answers
238 views

Fibonacci Cubes: $F_n^3 + F_{n+1}^3 - F_{n-1}^3 =F_{3n}$

Prove $$F_n^3 + F_{n+1}^3 - F_{n-1}^3 =F_{3n}$$ I've tried induction, either its just very long or a neat trick is required in the inductive step but for some odd reason its not working out. ...
9
votes
3answers
372 views

Significance of starting the Fibonacci sequence with 0, 1…

DISCLAIMER: I do not deal with in-depth mathematics on a daily basis as some of you may, so please pardon my ignorance or lack of coherence on this topic. QUESTION: What is the significance of ...
9
votes
2answers
796 views

Find all integer solutions for the equation $|5x^2 - y^2| = 4$

In a paper that I wrote as an undergraduate student, I conjectured that the only integer solutions to the equation $$|5x^2 - y^2| = 4$$ occur when $x$ is a Fibonacci number and $y$ is a Lucas number. ...
8
votes
4answers
3k views

Fibonacci modular results

Can any one give a generalization of the following properties in a single proof? I have checked the results, which I have given below by trial and error method. I am looking for a general proof, which ...
8
votes
7answers
390 views

Why is the Fibonacci ratio though a decreasing function, it is alternating and decreasing?

I tried to find the ratio of consecutive terms of the Fibonacci series and found that it is a decreasing function and it converges . I tried it though a small code piece in python so that I can have a ...
8
votes
2answers
475 views

Infinite Series: Fibonacci/ $2^n$

I presented the following problem to some of my students recently (from Senior Mathematical Challenge- edited by Gardiner) In the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55... each term ...
8
votes
3answers
1k views

How many numbers are in the Fibonacci sequence

Assuming I'm asked to generate Fibonacci numbers up to N, how many numbers will I generate? I'm looking for the count of Fibonacci numbers up to N, not the Nth number. So, as an example, if I ...
8
votes
3answers
2k views

Interesting properties of Fibonacci-like sequences?

Everyone is familiar with the Fibonacci Sequence, [0] 1 1 2 3 5 8 ... and many of it's interesting properties. For example, as the sequence continues, the ratio of ...
8
votes
1answer
302 views

Prove: the intersection of Fibonacci sequence and Mersenne sequence is just $\{1,3\}$

$$\frac{{{\varphi ^n} - {{(1 - \varphi )}^n}}}{{\sqrt 5 }} = {2^m} - 1 .$$ Here $\varphi = \frac{{1 + \sqrt 5 }}{2}$ . This integer equation has no solution for $n>3$ and $m>2$. How to prove?
8
votes
3answers
114 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 ...
8
votes
1answer
115 views

Is this number rational or irrational?

Start writing down the Fibonacci numbers, using two digits for each one 01 01 02 03 05 08 13 21 34 55 ... Eventually you will reach three digit numbers. When ...
8
votes
1answer
125 views

An analogue of Hensel's lifting for Fibonacci numbers

In this question Oleg567 conjectured the following interesting fact about Fibonacci numbers: $$ k\mid F_n\quad\Longrightarrow\quad k^d\mid F_{k^{d-1}n} $$ that can be regarder as an analogue of the ...
8
votes
1answer
92 views

Prove that $\forall p \in \Bbb P;p \ne 5,$ $F_{p^n - \left(\frac{5}{p}\right)p^{n-1}} \equiv 0 \mod p^n$

Prove that $\forall p \in \Bbb P,n \in \Bbb Z^+;p \ne 5,$ $F_{p^n - \left(\frac{5}{p}\right)p^{n-1}} \equiv 0 \mod p^n$ and $F_{5^n} \equiv 0 \mod 5^n$, where $\left(\dfrac{5}p\right)$ is the Legendre ...
8
votes
1answer
67 views
+200

If the generating function summation and zeta regularized sum of a divergent exist, do they always coincide?

One could assign a value to divergent series by means of several summation methods. One summation method we could consider is the generating function method. Let's sum, for example, the fibonacci ...
7
votes
1answer
718 views

How to prove that $\mathrm{Fibonacci}(n) \leq n!$, for $n\geq 0$

I am trying to prove it by induction, but I'm stuck $$\mathrm{fib}(0) = 0 < 0! = 1;$$ $$\mathrm{fib}(1) = 1 = 1! = 1;$$ Base case n = 2, $$\mathrm{fib}(2) = 1 < 2! = 2;$$ Inductive case ...
7
votes
8answers
830 views

Need help deriving recurrence relation for even-valued Fibonacci numbers.

That would be every third Fibonacci number, e.g. $0, 2, 8, 34, 144, 610, 2584, 10946,...$ Empirically one can check that: $a(n) = 4a(n-1) + a(n-2)$ where $a(-1) = 2, a(0) = 0$. If $f(n)$ is ...
7
votes
3answers
2k views

Fibonacci sequence divisible by 7?

Make and prove a conjecture about when the Fibonacci sequence, $F_n$, is divisible by $7$. I've realized it's when $n$ is a multiple of $8$. I just don't know how to go about proving it.
7
votes
7answers
591 views

Prove the following equality: $\sum_{k=0}^n\binom {n-k }{k} = F_n$ [duplicate]

I need to prove that there is the following equality: $$ \sum\limits_{k=0}^n {n-k \choose k} = F_{n} $$ where $F_{n}$ is a n-th Fibonacci number. The problem seems easy but I can't find the way to ...
7
votes
2answers
394 views

Fibonacci numbers divisible by $9$

The $n$th Fibonacci number $F_n$ is defined as follows,$$F_1=F_2=1\mbox{ and } F_{n+2}=F_{n+1}+F_{n}\mbox{ for } n\geq 1$$ I want to know how many of the first $1000$ Fibonacci numbers are divisible ...
7
votes
3answers
167 views

How can I show that $\sum\limits_{n=1}^\infty \frac{z^{2^n}}{1-z^{2^{n+1}}}$ is algebraic?

Show that $$\sum_{n=1}^\infty \frac{z^{2^n}}{1-z^{2^{n+1}}}$$ is algebraic. More specifically, solve this and get exact values. Then use the result to evaluate $$\sum_{n=0}^\infty ...
7
votes
3answers
492 views

Proof of this result related to Fibonacci numbers?

$$\begin{pmatrix}1&1\\1&0\end{pmatrix}^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}$$ Somebody has any idea how to go about proving this result? I know a proof by ...
7
votes
1answer
138 views

Identity for $e$ in terms of the Fibonacci sequence.

The following identity appears in Martin Gardner's paper, "Dr. Matrix on Little Known Fibonacci Curiosities: $$e = \frac{1 + 1 + \frac{2}{2!} + \frac{3}{3!} + \frac{5}{4!} + \frac{8}{5!} + ...
7
votes
4answers
1k views

Proof by Induction: Alternating Sum of Fibonacci Numbers [duplicate]

Possible Duplicate: Show that $f_0 - f_1 + f_2 - \cdots - f_{2n-1} + f_{2n} = f_{2n-1} - 1$ when $n$ is a positive integer This is a homework question so I'm looking to just be nudged in ...
7
votes
1answer
225 views

Proof that Fibonacci Sequence modulo m is periodic?

It's well known that the Fibonacci sequence modulo m (where m is any integer) is periodic. I have figured out a proof for this, but upon googling, I found proofs online that were far more complicated. ...