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

0
votes
1answer
158 views

Proving Lucas Identity by Induction

I am trying to prove the following identity (I decided to use induction, but if that's not the best way feel free to mention that in the answers): $$L^2_n = 5F^2_n + 4(-1)^n \space\space ...
2
votes
1answer
327 views

Fibonacci Sequence Exercise

I need some help checking the following solution. The Fib sequence is defined by $a_1 = 1, a_2 = 1$ and for all $n\geq 2$, $a_{n+1} = a_n + a_{n-1}$. Thus, the sequence begins: 1, 1, 2, 3, 5, 8, ...
1
vote
1answer
347 views

Pisano periods of fibonacci mod

The wikipedia article on Pisano periods utilises the Binet's formula and quadratic residues to find $f(n)$ such that $F_n=f(n) \pmod{p}$ where $p$ is a prime number and $F_n$ is a Fibonacci number. ...
0
votes
2answers
242 views

find a general expression for the remainder when a prime divides a fibonacci.

I have primes of form $5k\pm1$. Consider the equation: $F_n=f(n)\pmod p$ where $F_n$ is the nth fibonacci number. Now given a c, how can i check whether or not there exists a solution for $f(n)=c ...
1
vote
0answers
516 views

Calculating Pisano periods for any integer

I recently stumbled across this SPOJ question: http://www.spoj.com/problems/PISANO/ The question is simple. Calculate the Pisano period of a number. After I researched my way through the web, I found ...
2
votes
1answer
349 views

Cycles in the Generalized Fibonacci Sequence modulo a Prime

Suppose I have a fibonacci sequence 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 Now if I have a modulo 5 fibonacci sequence,it will look like ...
1
vote
0answers
68 views

Probability of Runs of Heads of Length N [duplicate]

For example: $“THHTHTTHHHTHTHTTHHTHT”$ contains 1 run of heads of length 3, 2 runs of length 2, and 4 runs of length 1. Assuming $P(H) = p$ and $P(T) = (1-p)$, calculate (using properties such as ...
5
votes
1answer
1k views

Fibonacci with Mortal Bunnies

I am trying to understand a twist on the Fibonacci bunnies scenario, where the bunnies die x generations after their birth (where x is a positive integer). An example is shown here. I understand the ...
6
votes
2answers
328 views

Divisibility of Fibonacci numbers

This question is inspired by a Project Euler problem I was working on. Noticing something that did not make sense led me to the conclusion that for all primes $p$ ending in $1$ or $9$, the $(p-1)$st ...
1
vote
1answer
284 views

Showing the fibonacci sequence for any number n

My lecturer was explaining how the Fibonacci sequence can be displayed for a number n. The formula is fib(n)=fib(n-1) +fib(n-2) ...
2
votes
3answers
954 views

Using induction to prove a result about the Fibonacci sequence

The Fibonacci sequence $F_0, F_1, F_2,...,$ are defined by the rule $$F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}$$ Use induction to prove that $F_n\geq2^{0.5n}$ for $n\geq 6$ So far I have done the ...
7
votes
4answers
2k views

Show that $f(2n)= f(n+1)^2 - f(n-1)^2$

Let $f(n)=f(n-1)+f(n-2)$ be the Fibonacci sequence with $f(0)=0,f(1)=1$. Show that $$f(2n)= f(n+1)^2 - f(n-1)^2.$$ I have tried several different approaches to this problem. Both inducting from the ...
0
votes
2answers
365 views

Prove the given property of the Fibonacci numbers directly

The definition of the Fibonacci numbers is as follows: $F(0)=0$, $F(1)=1$, $F(n)=F(n-2)+F(n-1)$ for $n ≥ 2$. Prove the given property of the Fibonacci numbers directly from the definition (hint: do ...
1
vote
1answer
42 views

Determine the number of n-term sequences of 0s and 1s containing no two consecutive $0$s

I am reading a chapter about Fibonacci number and generating function. And there's a question come up but without solution. I think about it for quite some time, but still can't come up with a ...
1
vote
1answer
201 views

Fibonacci Mystery

I saw this on a "numberphile" video and tried to prove it but couldn't do anything. Theorem: Let $n \ge 2$ and $F_m$ is the $m^{\text{th}}$ number in the Fibonacci sequence. Then, if we look all ...
-1
votes
2answers
143 views

Please help to understand Fibonacci numbers' property.

Theorem: The Fibonacci numbers are defined recursively thus: $$x_{n+1} = x_n + x_{n-1}$$ with $$x_1=x_2=1.$$ Prove that $$x_n=(a^n-b^n)/(a-b),$$ where $a$ and $b$ are the roots of the quadratic ...
1
vote
2answers
329 views

Counting function for Fibonacci numbers

Are there some results about "Fibonacci-counting function" - the function counting the number of Fibonacci numbers less than or equal to some real number x?
3
votes
3answers
2k views

Strong Induction Proof: Fibonacci number even if and only if 3 divides index

The Fibonacci sequence is defined recursively by $F_1 = 1, F_2 = 1, \; \& \; F_n = F_{n−1} + F_{n−2} \; \text{ for } n ≥ 3.$ Prove that $2 \mid F_n \iff 3 \mid n.$ Proof by Strong Induction : ...
8
votes
2answers
836 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
1answer
453 views

The Principle of Mathematical Induction

The question is Let $( F_0, F_1, F_2,... )$ be the Fibonacci sequence defined by $F_0=0,\, F_1=1, and F_{n+1}=F_n+F_{n-1}$, n greater than or equal to 1. Prove the following identities. ...
0
votes
1answer
104 views

The relation between piano 12-scale and Fibonacci?

One of my books says there is a relation between the chromatic musical scale [CC#DD#EFF#GG#AA#BC] and the Fibonacci sequence. So...what's the relation?
1
vote
2answers
117 views

Sum of Fibonacci-Numbers

Is there a closed formula for the sum of the first $n$ even (or odd) Fibonacci numbers, like there is one for the $n$th number (Moivre-Binet)?
6
votes
2answers
2k views

Inductive proof of the closed formula for the Fibonacci sequence [duplicate]

Fibonacci numbers $f(n)$ are defined recursively: $f(n) = f(n-1) +f(n-2)$ for $n > 2$ and $f(1) = 1$, $f(2) = 1$. They also admit a simple closed form: $$\sqrt 5 f( n ) = \left(\dfrac{1+ \sqrt ...
3
votes
1answer
152 views

Monotonicity of the sequence $ ( F_n^{\frac{1}{n}} ) $, where $ ( F_n ) $ is the Fibonacci sequence

Let $ F_n = F_{n-1} + F_{n-2} $ with $ F_0 = 1 $, $ F_1 = 1 $ (the Fibonacci sequence). I would like to know whether $ F_n^{\frac{1}{n}} $ is monotonically increasing in $ n $. It is not difficult to ...
4
votes
2answers
274 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 ...
2
votes
0answers
111 views

Why is the reciprocal of the second Fibonacci number negative?

The second Fibonacci number is 1, so it's reciprocal should be 1, right? Why is it that I get $-1$ when I plug in $2$ for n in the reciprocal of Binet's equation ...
1
vote
2answers
77 views

What is the approx value of $f(50001)/f(50000)$ where $f(i)$ gives the value of the $i$-th number in the Fibonacci series?

What is the approx value of $f(50001)/f(50000)$ where $f(i)$ gives the value of the $i$-th number in the Fibonacci series?
0
votes
2answers
97 views

How to prove that the Fibonacci sequence $7\mid U_m\Longrightarrow 8\mid m$ and $4\mid U_m\Longrightarrow 6\mid m$

How to prove that the Fibonacci sequence $$7\mid U_m\Longrightarrow 8\mid m$$ and $$4\mid U_m\Longrightarrow 6\mid m$$I was confused because there $\{ 4,7 \}$ in Fibonacci sequece
6
votes
1answer
270 views

Let $F_n$ be a Fibonacci number and $p$ a prime. Verify that for $p \le 61$, if $p\equiv\pm1 \pmod{5}$ then $p\mid F_{p-1}$

Define the Fibonacci entry point of $p$ to be the least integer $n$ such that $p\mid F_n$ So for example, for $p = 3$ - the Fibonacci entry point is $n = 4$ since $F_4 = 3$ and obviously $3\mid 3$. ...
8
votes
1answer
119 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 ...
1
vote
4answers
485 views

Divisibility and the Fibonacci sequence

While studying the Fibonacci sequence I encountered this problem in the handout, and I can not understand how to do it. Show that if the Fibonacci sequence has a term divisible by a natural number ...
0
votes
1answer
102 views

Two issues of Number Theory

Knowing in Fibonacci sequence$$u_n\mid u_m\Longleftrightarrow n\mid m$$ Question 1: In Fibonacci sequence, show that $$5\mid u_m\Longleftrightarrow 5\mid m$$ Show: $\Longrightarrow$ In ...
2
votes
3answers
229 views

Statement on the Fibonacci sequence

Question: Let $n,m,\in\mathbb{N^*}$ with $n>1$ and let $u_n$ denote the $n$-th term of the Fibonacci sequence, then $$u_{n+m}=u_{n-1}u_m+u_nu_{m+1}$$ I know these theorems: Two consecutive ...
3
votes
2answers
248 views

Prove that if $F_n$ is highly abundant, then so is $n$.

Define $F_n$ to be the $n$th Fibonacci number, define $\sigma(n)$ to be the sum of the divisors of $n$, and call $n$ highly abundant if and only if $\sigma(n)>\sigma(m) \hspace{3mm} \forall ...
1
vote
1answer
30 views

Prove that $F_{\sum_{i=1}^ka_i}\geq \prod_{i=1}^kF_{a_i}\forall a_i,k \geq 1$

Is there an elegant way to do this? I don't think it's particularly difficult, since $F_n \sim \frac{\phi^n}{\sqrt{5}}$, so we expect that $F_{\sum_{i=1}^ka_i} \sim ...
1
vote
1answer
85 views

About the percentage of the mutiples of a prime $p$ in Fibonacci sequence

Suppose that a sequence $\{f_n\}$ is defined as $$f_1=f_2=1, f_{n+2}=f_{n+1}+f_n\ \ (n\ge1).$$ Supposing that for a prime number $p$ and a natural number $N$,$$F_p(N)=\{\ n\ |\ n \in\mathbb N,\ n\le ...
5
votes
1answer
174 views

Prove that $F_{n}^{2}+F_{n+1}^{2}=F_{2n+1}$ [duplicate]

Prove that $F_{n}^{2}+F_{n+1}^{2}=F_{2n+1}$ This identity holds for $n>=1$ Instead of using induction, how do I prove it in a geometry approach?
5
votes
1answer
187 views

Prove $F_{1}^{2}+F_{2}^{2}+\dots+F_{n}^{2}=F_{n}F_{n+1}$

Prove the identity: $F_{1}^{2}+F_{2}^{2}+\dots+F_{n}^{2}=F_{n}F_{n+1}$, where $F_i$ denotes a Fibonacci number. How can I prove it using a geometric approach?
1
vote
1answer
110 views

Prove that if $\sigma(F_a)<\sigma(F_b)$, where $1 \leq b < a$, then $\sigma(a)<\sigma(b)$ also

Prove that if $\sigma(F_a)<\sigma(F_b)$, where $1 \leq b < a$, then $\sigma(a)<\sigma(b)$ also. Here $\sigma(x)$ denotes the sum of the divisors of $x$ and $F_x$ is the $x$th Fibonacci ...
2
votes
1answer
250 views

Determine whether every characteristic factor of the nth Fibonacci number is $\equiv \pm 1 \mod n$

Determine whether all characteristic factors of the $n$th Fibonacci number, which are primes $p_1, p_2,..., p_k$ such that $p_i \mid F_n$ and $p_i \not\mid F_m \hspace{3 mm} \forall i \in [1,k], m \in ...
3
votes
1answer
71 views

Prove that $F_{x^{n+1}} \sim 5^{\frac{x-1}{2}}F_{x^n}^x \forall x,n \geq 1$, holding either variable constant while the other goes to infinity

I noticed from looking at the prime factorizations of some Fibonacci numbers that all those with an index equal to a power of 5 divided that power of five, a property not guaranteed by the strong ...
3
votes
1answer
79 views

A Generalized Fibonacci sequence

I have the following recurrence $$u_{n+1}=u_{n}+a^{N-n}u_{n-1}\quad n\ge 1$$ where $$N\ge 1,\quad u_1=u_0=1,\quad 0< a\le 1$$ I want to find out $u_N$. My Try: For $a=1$ this is just the Fibonacci ...
2
votes
2answers
129 views

Is Fibonacci sequence the minimum of unique pairwise sum sequence?

Let $(a_n)_{n=1}^\infty$ be a strictly increasing (condition added per earlier answer of Amitesh Datta) sequence of natural numbers where all pairwise element sums are unique. Can anyone prove or ...
7
votes
0answers
504 views

A conjecture about Lucas series

Let $L_n$ be the Lucas series: $L_0=2,L_1=1,L_n=L_{n-1}+L_{n-2}(n>1).$ $p$ is a prime number and $p\equiv3,7\pmod {20}$, hence $\exists x,y\in \mathbb Z:2p=x^2+5y^2.$ Is it true that ...
0
votes
3answers
55 views

Fibonacci terms with primal distances

Given any prime $p$, are there fibonacci numbers $F_k $ and $F_n$ such that $|F_n - F_k|=p^i , i \in \mathbb N$?
2
votes
4answers
999 views

Strong inductive proof for this inequality using the Fibonacci sequence.

Problem I need to determine for what natural numbers is $2n < F_n$, where $F_n$ is the $n^{th}$ Fibonacci number determined by $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n-1}+F_{n-2}$. I then need to ...
1
vote
1answer
149 views

Sums and products involving Fibonacci

In summary, if $\phi$ is the golden ratio, I want to show: \begin{align} \sum_{n=1}^\infty \frac1{F_n} &= 4-\phi \\ \sum_{n=1}^\infty \dfrac{(-1)^{n+1}}{F_nF_{n+1}} &= \phi-1 \\ ...
1
vote
1answer
59 views

Solving $ F_{n} = \sum_{i=1}^{n-1} (F_{i}\cdot F_{n-i}) $?

I need to find $F_{n}$ in : $$ F_{n} = \sum_{i=1}^{n-1} (F_{i}\cdot F_{n-i}) , F_0 = 0 , n>=2 $$ This equation screams convolution , I think , but I find it as a quite long solution sometimes. ...
1
vote
3answers
77 views

Find $F_{n}$ in : $F_{n} +2F_{n-1} + … + (n+1)\cdot F_{0} = 3^{n}$

I'm stuck with the question for a while : Find in $$F_{n} +2F_{n-1} + ... + (n+1)\cdot F_{0} = 3^{n}$$ the element $F_{n}$ . Placing $n-1$ instead on $n$ results in : $$F_{n-1} +2F_{n-2} + ... + ...
2
votes
1answer
80 views

Solve a recursion using generating functions?

Given the recursive equation : $$F_n+F_{n-1}+⋯+F_0=3^n , n\geq0$$ A fast solution that I can think of is placing $n-1$ instead of $n$ , and then we'll get : $$F_{n-1}+F_{n-2}+⋯+F_0=3^{n-1} $$ ...