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
0answers
228 views

fibonacci numbers mod some prime number

Moderator Note: This is a current Code Chef challenge question. When the current challenge ends on 15 October 2013 this question will be unlocked. I have prime numbers ($\geq11$) and of the form ...
2
votes
1answer
224 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 ...
0
votes
0answers
56 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 ...
4
votes
1answer
584 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
171 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
211 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
625 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 ...
6
votes
3answers
1k 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
222 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
31 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
174 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
116 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
179 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?
0
votes
0answers
88 views

Fibonacci sequense, problem od division

How to show that $7\mid F_m\Longrightarrow 8\mid m$ and $4\mid F_m\Longrightarrow 6\mid m$, knowing that (I) Two consecutive terms in the Fibonacci sequence are relatively prime. (II) In ...
5
votes
3answers
1k 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 : ...
6
votes
1answer
730 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
301 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
70 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?
0
votes
2answers
84 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)?
3
votes
2answers
657 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
127 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 ...
3
votes
2answers
182 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
86 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
72 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
89 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
240 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
93 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
293 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
95 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
149 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 ...
2
votes
2answers
197 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
28 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
79 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
163 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
154 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
104 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
215 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
66 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
70 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
116 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 ...
6
votes
0answers
464 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
51 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
3answers
576 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
121 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
58 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
74 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
66 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} $$ ...
10
votes
4answers
242 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. ...
2
votes
2answers
772 views

Solve the recurrence of $T(n)= 3T(n-1)+1$ with$ T(0)=2$ by iteration of the recurrence

Solve the recurrence of $T(n)= 3T(n-1)+1$ with $T(0)=2$ by iteration of the recurrence. (I was told that there is no need to prove it by induction) I googled "iteration of the recurrence." I did not ...
2
votes
3answers
714 views

For the Fibonacci numbers, show for all $n$: $F_1^2+F_2^2+\dots+F_n^2=F_nF_{n+1}$

The definition of a Fibonacci number is as follows: $$F_0=0\\F_1=1\\F_n=F_{n-1}+F_{n-2}\text{ for } n\geq 2$$ Prove the given property of the Fibonacci numbers for all n greater than or equal to 1. ...