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
151 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
100 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
128 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
2answers
86 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
0
votes
0answers
70 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 ...
3
votes
2answers
535 views

Induction Proof: Formula for Fibonacci Numbers as Odd and Even Piecewise Function

How can we prove by induction the following? $ F_{n+1} = \left\{ \begin{array}{l l} F_{n/2}^2+F_{(n+2)/2}^2 & \quad \text{if $n$ is even}\\ ...
2
votes
4answers
2k views

Induction Proof: Fibonacci Numbers Identity with Sum of Two Squares

Using induction, how can I show the following identity about the fibonacci numbers? I'm having trouble with simplification when doing the induction step. Identity: $$f_n^2 + f_{n+1}^2 = f_{2n+1}$$ I ...
2
votes
1answer
1k views

Induction Proof: Formula for Sum of n Fibonacci Numbers

I am stuck though on the way to prove this statement of fibonacci numbers by induction : my steps: definition: $F_{0}:=0, F_{1}:=1 $ and $F_{n}:=F_{n-1}+F_{n-2}$ The Hypothesis is: $\sum_{i=0}^{n} ...
3
votes
1answer
204 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
62 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
votes
2answers
481 views

Closed formula for the Fibonacci sequence (induction) [closed]

Let $f (n)$ denote the $n^{th}$ term of the sequence of integers given by the equation $f(n) = f(n-1) +f(n-2)$ for $n > 2$ and $f(1) = 1 \land f(2) = 1$, then using principle of mathematical ...
3
votes
1answer
115 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 ...
2
votes
0answers
80 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
67 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?
1
vote
1answer
1k views

Smallest Fibonacci number having a common factor with a given number

We have a number $k$ and we have to find the smallest Fibonacci number that has common factor with it(except $1$). We also have $2 \leq k \leq 1,000,000$. The required Fibonacci number is guaranteed ...
0
votes
1answer
90 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 ...
8
votes
1answer
88 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 ...
2
votes
2answers
174 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 ...
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 ...
4
votes
5answers
424 views

Showing that $f_{2n+1}=f_{n+1}^2+f_n^2$.

I am trying to solve the following exercise: Let $f_1=1$, $f_2=1$, $f_{n+1}=f_n+f_{n-1}$, where $n\in\mathbb{N}$. Show that $f_{2n+1}=f_{n+1}^2+f_n^2$. I have not had much progress, but this is ...
1
vote
4answers
196 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 ...
2
votes
3answers
132 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 ...
1
vote
1answer
101 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 ...
1
vote
1answer
77 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 ...
4
votes
1answer
140 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?
2
votes
3answers
510 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. ...
1
vote
1answer
27 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 ...
5
votes
1answer
152 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?
3
votes
1answer
63 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 ...
2
votes
1answer
67 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
106 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
420 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
48 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
456 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
93 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
64 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} $$ ...
9
votes
4answers
224 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. ...
1
vote
3answers
237 views

Proof of identity $F_m F_n + F_{m−1} F_{n−1} = F_{m+n−1}$ for Fibonacci numbers

I'm lost on where to start on this proof: Using the fact that $A^m A^n = A^{m+n}$ , prove the identity $F_m F_n + F_{m−1} F_{n−1} = F_{m+n−1}$ I want to use induction starting with n = 1, but would ...
0
votes
0answers
23 views

Solve the recurrence of T(n)= 3T(n-1)+1 with T(0)=2 as a first order linear recurrence. [duplicate]

Solve the recurrence of T(n)= 3T(n-1)+1 with T(0)=2 as a first order linear occurrence. I would do T(0)= 3T(-1)+1=2. I need to find a condition for n<0 and n>0. Any tips on getting started? ...
1
vote
2answers
107 views

Suppose that a recursive routine were invoked to calculate F(4). How many times would a recursive call of F(1) occur?

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$$ Suppose that a recursive routine were invoked to calculate $F_4$. How many times would a ...
2
votes
2answers
637 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 ...
1
vote
3answers
489 views

Prove that $F(n+3)=2F(n+1)+ F(n)$ for $n \ge 0$

The definition of a Fibonacci number is as follows: $$F(0)=0\\ F(1)=1\\ F(n)= F(n-2)+F(n-1)\text{ for }n\geq 2$$ Prove the given property of the Fibonacci numbers directly from the definition. ...
0
votes
1answer
67 views

Is the Fibonacci number-like function too trivial to investigate about?

To make some interesting recursive function, I generalized Fibonacci numbers to a function $f(x)$ such that satisfies the following condition: Given a function $g(x)$, such that $g(0)=0$ and ...
8
votes
7answers
348 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 ...
-1
votes
3answers
259 views

Show that the limit exists and find it's value? [duplicate]

The Fibonacci series defined recursively by $x(1) = 1, x(2) = 2$ and $x(n+1) = x(n) + x(n-1)$ Find$$\lim_{n\rightarrow\infty}\frac{x(n+1)}{x(n)}$$
5
votes
4answers
518 views

Is Binet's formula for the Fibonacci numbers exact?

Is Binet's formula for the Fibonacci numbers exact? $F_n = \frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2^n \sqrt{5}}$ If so, how, given the irrational numbers in it? Thanks.
6
votes
5answers
276 views

Fibonacci-like sequence

Today I have to deal with something which reminds Fibonacci sequence. Let's say I have a certain number k, which is n-th number of certain sequence. This sequence however is created by recursive ...
4
votes
0answers
62 views

A Fibonacci like Stochastic process

Let $X_0, X_1$ and $\{a_n,n\geq0\}\sim $Bernoulli$(1/2)$ taking values in $\{0,2\}$. Let us define $X_n$ for $n>1$ as below$$X_{n+1}=a_nX_n+a_{n-1}X_{n-1},\ n\geq1 $$ Then it follows that ...