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

4
votes
1answer
201 views

Golden parallelepiped

Define a golden parallelepiped as a $d$-dimensional box with side lengths $(1, \phi, \phi^2, \ldots, \phi^{d-1})$, where $\phi$ is the golden ratio: ...
6
votes
1answer
272 views

Finding ($2012$th term of the sequence) $\pmod {2012}$

Let $a_n$ be a sequence given by formula: $a_1=1\\a_2=2012\\a_{n+2}=a_{n+1}+a_{n}$ find the value: $a_{2012}\pmod{2012}$ So, in fact, we have to find the value of ...
3
votes
0answers
157 views

Which starting conditions for the Fibonacci sequence, gives most primes

I found the following question (at http://aperiodical.com/2012/05/matt-parkers-twitter-puzzle-25-may/): If you start the Fibonacci sequence 2,1 instead of 1,1 do you get more or fewer primes? ...
4
votes
1answer
313 views

What is the next “Tribonacci-like” pseudoprime?

Given the three roots of $x^3=x^2+x+1$. Then we get the tribonacci-like sequence, $B_n = x_1^n+x_2^n+x_3^n = 3, 1, 3, 7, 11, 21, 39, 71, 131,\dots$ where $B_n = B_{n-1}+B_{n-2}+B_{n-3}$, and the ...
7
votes
2answers
292 views

Fibonacci numbers with largest prime factor appearing more than once

$F_6=2^3$ and $F_{12}=2^43^2$. Is there an $n>12$ such that $F_n=p^2k$ with $p$ prime and $k$ is $p$-smooth?
0
votes
2answers
412 views

A game: Fibonacci sequences and probability.

Let's play a game. You have two biased coins: coin A has a $0.4$ and $0.6$ for H and T probability and coin B has the opposite ($0.6$ and $0.4$ for H and T). These coins must be flipped one at a time, ...
6
votes
2answers
188 views

Prove that $\sum\limits_{n=0}^{\infty}\frac{F_{n}}{2^{n}}= \sum\limits_{n=0}^{\infty}\frac{1}{2^{n}}$

I came up with this identity in high school, and I can't remember how I proved it :P Does anyone know how I would go about doing this? $$\sum_{n=0}^{\infty}\frac{F_{n}}{2^{n}}= ...
2
votes
2answers
557 views

Using linear algebra, how is the Binet formula (for finding the nth Fibonacci number) derived?

If possible, please refrain from any type of proof besides linear algebra. So, using the recursion formula $F_{n+1} = F_{n-1} + F_n$, for $n\gt 1$, and where $F_0 = 0$ and $F_1 = 1$, and the Fibonacci ...
1
vote
0answers
83 views

Lucas numbers theory confused [duplicate]

Possible Duplicate: Prove this formula for the Fibonacci Sequence How does one find a formula for the recurrence relation $a_{1}=1,a_{2}=3, a_{n+2}=a_{n+1}+a_{n}?$ How do I go about ...
7
votes
3answers
577 views

How to prove that $\lim \limits_{n\rightarrow \infty} \frac{F_{n+1}}{F_n}=\frac{\sqrt{5}+1}{2}$

How would one prove that $$\lim_{n\rightarrow \infty} \frac{F_{n+1}}{F_n}=\frac{\sqrt{5}+1}{2}=\varphi$$ where $F_n$ is the nth Fibonacci number and $\varphi$ is the Golden Ratio?
5
votes
1answer
434 views

(Long) Fibonacci Sequence Question

I am working on a rather long question. I am going to write out the question, and what I've come up with so far. I'm not sure if the question has too many parts to receive answers but I will ...
7
votes
4answers
17k views

What do Subscripted numbers in an equation mean?

$F_n= F_{n-1}+ F_{n - 2}$ I know that when a number is superscripted it means "to the power of", but what does the subscript mean?
1
vote
1answer
129 views

“Non-commutative” Recurrence relation $ C_m = \alpha_m C_{m-1} + \beta_m C_{m-2} $

I have a problem, which is probably quite trivial. Consider a recurrence relation of the form $$ C_m = \alpha_m C_{m-1} + \beta_m C_{m-2}, $$ where the coefficients $\alpha_m$ and $\beta_m$ are ...
6
votes
4answers
2k views

Fibonacci's final digits cycle every 60 numbers

How would you go about to prove that the final digits of the Fibonacci numbers recur after a cycle of 60? References: The sequence of final digits in Fibonacci numbers repeats in cycles of 60. The ...
9
votes
3answers
2k 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 ...
3
votes
2answers
129 views

Binet's Formula. An operational approach.

I read quite a while ago this proof of Binet's formula. ( I am not 100% sure this is the way it was presented, but it gives an idea. I'm not approving of this method or saying it is correct.) Let ...
7
votes
1answer
671 views

Another way to go about proving the limit of Fibonacci's sequence quotient.

It is not difficult to inductively prove that $$\eqalign{ & \phi = \phi + 0 \cr & {\phi ^2} = \phi + 1 \cr & {\phi ^3} = 2\phi + 1 \cr & {\phi ^4} = 3\phi + 2 ...
2
votes
1answer
98 views

How to calculate variety of a vector under this constraint?

I am currently working through W. Ross Ashby's An Introduction to Cybernetics, and I'm stuck on a problem of calculating variety for a vector. I know the answer (I caved and checked), but I can't ...
14
votes
2answers
308 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 ...
4
votes
1answer
510 views

Why Fibonacci numbers are too often found on nature?

Fibonacci number has something to do with natural growth. Though the function is very straight forward, we see this in nature. Does nature follow the function or its the simplified model of the ...
1
vote
4answers
273 views

Generalized Fibonacci sequences

Why Fibonacci sequence start at $0$, Tribonacci sequence with $0,0$, Tetranacci with $0,0,0$, etc. [ref OEIS] Has any good reasons for that? These sequences arise in generalization of Pascal Triangle ...
1
vote
1answer
104 views

Recovering two first terms from sequence $f(n)=f(n-1)+f(n-2)$

Having very simple sequence $f(n)=f(n-1)+f(n-2)$ and having $n-th$ term given how can we calculate from which first two terms this $n-th$ term came? I know the answer can be not unique so highest ...
4
votes
2answers
2k views

Fibonacci, tribonacci and other similar sequences

I know the sequence called the Fibonacci sequence; it's defined like: $\begin{align*} F_0&=0\\ F_1&=1\\ F_2&=F_0+F_1\\ &\vdots\\ Fn&=F_{n-1} + F_{n-2}\end{align*}$ And we ...
1
vote
2answers
3k views

How to find the closed form to the fibonacci numbers? [duplicate]

Possible Duplicate: Prove this formula for the Fibonacci Sequence How to find the closed form to the fibonacci numbers? I have seen is possible calculate the fibonacci numbers without ...
3
votes
3answers
167 views

Prove for Fibonacci numbers: $3\mid f(n) \iff 4\mid n$

Let $f(n)$ be the $n$th Fibonacci number. Prove that $$3\mid f(n) \iff 4\mid n$$ I tried to use induction to prove it but I couldn't continue when I reached $n+1$ case.
8
votes
1answer
340 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
4answers
2k 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 ...
2
votes
1answer
437 views

Prime power divisors of the fibonacci numbers

I came across a result that if $p^n \mid f_m$ for some $n\geq1$ then $p^{n+1} \mid f_{pm}$. I was wondering if this is true.
51
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} ...
5
votes
2answers
249 views

Prefix of Fibonacci number

Given some prefix how can we check if this prefix belongs to a Fibonacci number? If yes then to which one? By the prefix of number I define first $n$ digits. For example ...
5
votes
1answer
315 views

Expanding the generating function of the Fibonacci numbers to find a cute formula

$F_0=1$, $F_1=1$, $F_n=F_{n-1}+F_{n-2}$. The generating function is $-\frac{1}{x^2+x-1}$. I have to expand it to prove that $F_n=\sum_k\binom{k}{n-k}$. Could you help me please?
5
votes
1answer
617 views

On the generating function of the Fibonacci numbers

Let's define the Fibonacci numbers as $F_0=1$, $F_1=1$ and $F_n=F_{n-1}+F_{n-2}$. Using this recurrence I was able to calculate the generating function of the Fibonacci numbers to be ...
4
votes
1answer
130 views

Prove that If $f_n$ where $n>3$ is prime, then $n$ is prime for a Fibonacci series where $f_1$=$f_2$=1

This problem came up in my conversation with a friend—not sure how basic it is, but it seems quite interesting: Prove that if $f_n$ where $n>3$ is prime, then $n$ is prime for a Fibonacci sequence ...
9
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.
5
votes
2answers
670 views

Fibonacci and Lucas identity

By the trial and error method I have observed the following identity by taking some numerical values. Those are $F_m$|$L_n$ is valid only if one of the following holds. a) $m = 1$ or $m =2$ b) $m ...
36
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 ...
7
votes
3answers
526 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 ...
1
vote
1answer
218 views

Fibonacci modular results 2

In my study I understand that the Fibonacci sequence mod $k$ is periodic, with period less than $k^2$. Can any one generalize this with good proof?
3
votes
2answers
811 views

$f_n$ is divisible by $4$ if and only if $n$ is divisible by $6$

I thought I had this question down, but while looking over my solution, I think I'm missing a step. I want to show for $f_n$ the nth fibonacci number, that $f_n$ is divisible by $4$ if and only if ...
4
votes
1answer
769 views

Understanding fibonacci ratio in plants

Recently, a 13year old kid has re-dicovered that there is a magic ratio for branching in plants. Following article describes his work in his own words. ...
5
votes
1answer
344 views

Fibonacci identity

The Fibonacci numbers, given by $f_0 = 1$, $f_1 = 1$ and $f_n = f_{n-1} + f_{n-2}$, for $n \geq 2$ have many interesting properties. Many of these interesting properties can be easily proven ...
2
votes
1answer
195 views

An identity involving Lucas numbers

Let $L_n$ be the Lucas numbers, defined by $L_n = F_{n-1} + F_{n+1}$ where f is the Fibonacci numbers. How to prove that $L_{2n+1} = \displaystyle \sum_{k=0}^{\lfloor n + 1/2\rfloor}\frac{2n+1}{2n+1 ...
1
vote
3answers
247 views

Proving Fibonacci Identites [duplicate]

Possible Duplicate: Showing that an equation holds true with a Fibonacci sequence: $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$ Hi! I needed to solve several Fibonaccii identites, but I couldn't ...
3
votes
2answers
2k views

Deriving formulas for recursive functions

If I had a recursive function (f(n) = f(n-1) + 2*f(n-2) for example), how would I derive a formula to solve this? For example, with the Fibonacci sequence, Binet's ...
7
votes
1answer
278 views

Common terms in general Fibonacci sequences

Mathworld notes that "The Fibonacci and Lucas numbers have no common terms except 1 and 3," where the Fibonacci and Lucas numbers are defined by the recurrence relation $a_n=a_{n-1}+a_{n-2}$. For ...
3
votes
2answers
211 views

Fibonacci/Lucas Number Congruences

Is there a compendium of well-known (and elementary) Fibonacci/Lucas Number congruences? I've proven the following and would like to know if it is (a) trivial, (b) well-known, or (c) possibly new. $$ ...
1
vote
1answer
355 views

Lucas Numbers and Tilings

Show that $f_{n-1} + L_n = 2f_{n}$. So we need to find a $2$ to $1$ correspondence. Set 1: Tilings an $n$-board. Set 2: Tiling of an $n-1$-board or tiling of an $n$-bracelet. So we need to ...
6
votes
4answers
364 views

Prime Appearances in Fibonacci Number Factorizations

Okay, THIS one is considerably more analytical... :P (Used my post here as a basis.) When successive Fibonacci numbers are factored, the primes appear in a specific order, which goes $2, 3, 5, 13, 7, ...
16
votes
1answer
7k 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, ...
1
vote
3answers
279 views

Fibonacci Numbers: Is This Notation Clear? How Can It Be Improved?

I am writing up an assignment with includes many identities of Fibonacci numbers. I have made up the following notation (here $f_n$ is the number of tilings of an $n$-board by dominoes and squares - a ...