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

3
votes
3answers
286 views

Another way to go about proving Binet's Formula

As I showed in another question of mine, it is easy to prove that $$\tag{1}\phi^{n+1} =F_{n+1} \phi+F_{n }$$ given $F_1=1$ , $F_2=1$ , $F_{n+1}=F_n+F_{n-1}\text{ ; }n\geq2$. Now, extending $(1)$ ...
0
votes
2answers
26 views

Express recursive funtion in Fibonacci

Given the Fibonacci function and the function $L_n = L_{n-1} + L_{n-2} + 1$, how do I go from this: $L_n + 1 = L_{n-1} + L_{n-1} + 1 + 1 \\ (L_n + 1) = (L_{n-1} + 1) + (L_{n-2} + 1)$ To this: $L_n = ...
7
votes
1answer
208 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. ...
1
vote
1answer
28 views

Converting Fibonacci number $F_{5n+3}$ to Lucas numbers $L_{n+k}$

I'm trying to prove that$F_{5n+3}\text{mod}10 = L_{n}\text{mod}10$. I rearranged it into a more solvable form of $F_{5n+3}-L_n = 10k$ (because if two numbers end in the same digit, their difference ...
1
vote
4answers
89 views

New Fibonacci sequence

I have new Fibonacci number That I want to know is there any special direct formula to count f(n). like the normal Fibonacci: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2) For example I want to ...
2
votes
0answers
65 views

Lucas Number Equivalent of the Pisano Period?

I'm doing some work with the Pisano Period, and it's leading to also talk about the Lucas numbers $mod \ m$, and their period. Is there a specific notation already designated? Sticking with using a ...
4
votes
3answers
197 views

Probability that a chosen number will be a Fibonacci number

Suppose that I randomly choose an integer $x$ with $1 \leq x \leq n$ where $n$ is a natural number. What is the probability that $x$ will be a Fibonacci number?
6
votes
1answer
228 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$. ...
-2
votes
1answer
67 views

Application of convergence of Fibonacci series

'There are infinite prime numbers' is a fact that can be deduced by 'reciprocal of primes diverges' statement, so from this can we deduce the fact that --> 'there are finite Fibonacci numbers in ...
1
vote
1answer
86 views

Find all solution to $a^{2}\equiv -1 \pmod b$ and $b^{2}\equiv -1\pmod a$ (self-answer)

There was a question here just a moment ago but was deleted by the author. It is to find all solution to $a^{2}\equiv -1 \pmod b$ and $b^{2}\equiv -1 \pmod a$ with $a,b>1$. But I already typed up ...
1
vote
3answers
878 views

Fibonacci numbers and proof by induction

Consider the Fibonacci numbers $F(0) = 0; F(1)=1; F(n) = F(n-1) + F(n-2)$. Prove by induction that for all $n>0$, $$F(n-1)\cdot F(n+1)- F(n)^2 = (-1)^n$$ I assume $P(n)$ is true and try to show ...
0
votes
2answers
829 views

Summation of series of product of Fibonacci numbers

What is the sum of following product of Fibonacci numbers $$\sum_{k=1}^{n-1} Fib(k)*Fib(n+3-k)$$ can anyone suggest only approach to find general term?
-1
votes
3answers
110 views

Fibonacci Sequence or Golden Ratio?

Using the polar coordinate system, $r$ increases directly with $\theta$. In other words, $r=k\theta$. Which of the following shapes is constructed? A) Fibonacci Sequence B) Golden Ratio C) ...
1
vote
1answer
48 views

Pascal/Fibonacci and Combinatorics notation

I'm doing Pascal's Triangle and there are a ton of questions related to Pascal and the Fibonacci numbers embedded in the triangle, but I have a question about combinatorics which is most likely a very ...
6
votes
3answers
181 views

Is there a proof for this Fibonacci relationship?

I was looking at the decomposition of Fibonacci numbers using the definition of $F_n = F_{n-1} + F_{n-2}$, and noted the pattern in the coefficients of the terms were Fibonacci numbers. It appears to ...
2
votes
4answers
107 views

Fibonacci proof question [closed]

Show that $$f_{n+1}f_{n-1}-f_n^2=(-1)^n$$ when $n$ is a positive integer and $f_n$ is the $n$th Fibonacci number.
1
vote
1answer
71 views

Fibonacci… Easier by induction or directly via Binet's formula

I have tried both for several of them and haven't been able to get anywhere in 3 hours of work. It seems to not matter which method I choose, I end up in the middle of a HUGE mess of algebra. Could ...
2
votes
3answers
304 views

Why is 11 times the 7th term of a fibonacci series equal to the sum of 10 terms?

Why is 11 times the 7th term of a fibonacci series equal to the sum of 10 terms? I was watching scam-school on youtube the other day and this number trick just astonished me. Can someone please ...
1
vote
3answers
125 views

Golden ratio / Fibonacci which branch of math?

Friends, The Golden ratio / Fibonacci sequence are studied under which branch of math? Can you recommend some good textbooks on the subject? Thanks
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
171 views

Rectangle with coordinates of all vertices Fibonacci numbers

Suppose the coordinates of all vertices of a given (non-degenerate) rectangle are Fibonacci numbers. Suppose that the rectangle is not such that one of its vertices is on the $x$-axis and another on ...
4
votes
1answer
124 views

Proof/Disproof of property of perpendicular lines in the Fibonacci grid

In my struggle to try to make progress on this question, I am trying to find a proof or counterexample of the following, stronger, statement: Denote by $K$ the subset of the Gaussian integers such ...
2
votes
4answers
118 views

Fibonacci sequence proof

Prove the following: $$f_3+f_6+...f_{3n}= \frac 12(f_{3n+2}-1) \\ $$ For $n \ge 2$ Well I got the basis out of the way, so now I need to use induction: So that $P(k) \rightarrow P(k+1)$ for some ...
0
votes
1answer
60 views

Proof by Induction for a $f_3 + f_6 + · · · + f_{3n} = \frac{1}{2} (f_{3n+2} - 1)$ [duplicate]

The Fibonacci numbers are defined as follows: $f_0 = 0,\ f_1 = 1$, and for $n ≥ 2,\ f_n = f_{n−1} +f_{n−2}$. Prove that for every positive integer $n$, $$f_3 + f_6 + \ldots + f3_n = \frac{1}{2} ...
1
vote
1answer
45 views

Question about Fibonacci sequence

I proved that at Fib. $$\frac{1}{f_{n-1}f_{n+1}}=\frac{1}{f_{n-1}f_{n}}-\frac{1}{f_{n}f_{n+1}}$$ I need to prove two thing: 1.$$\sum_{n=2}^{\infty}\frac{1}{f_{n-1}f_{n+1}}=1$$ 2. ...
1
vote
1answer
48 views

Proof for subsets of Fibonacci numbers

Let $a(n)$ be the number of subsets $A$ of $\{1,2,...,n\}$ with the property that $A$ is either the empty set or $\forall k \in A ( k \geq |A|)$. How can I prove that $a(n) = F(n+2)$ and show that ...
1
vote
1answer
62 views

Limit of a function not using Stirling's Approximation

I want to compute the following limit: $$\lim_{n\to\infty} \frac{\left(\frac{e}{F_{n+1}}\right)^{F_{n+1}} F_{n+1}!}{\left(\frac{e}{F_n}\right)^{F_n} F_n!},$$ where $F_n$ is the $n$th Fibonacci ...
1
vote
3answers
77 views

recurrence relation for squares of fibonacci numbers

I have a problem finding a proof that the squares of the Fibonacci numbers satisfy the recurrence relation $a_{n+3} - 2*a_{n+2} - 2*a_{n+1} + a_n = 0$ and solving this recurrence relation. Some help ...
0
votes
1answer
312 views

Induction on Fibonacci Sequence and the Golden Ratio

I'm trying to prove $f_n \leq \left(\frac{1 + \sqrt{5}}{2}\right)^{n-1}$ with induction, and I'm stuck in the induction step. Basis: n = 2 $f_{2} \leq \left(\frac{1 + \sqrt{5}}{2}\right)^{2-1} ...
0
votes
1answer
40 views

Proof Help dealing Lucas and Fibonacci Numbers

Claim: $L_n=F_{n-1}+F_{n+1}$ for all $n >0$ Could someone please help me prove this. My professor mentioned it in class, but didn't show us how to prove it. I was just curious. The L stands for ...
4
votes
2answers
67 views

Fibonacci induction stuck in adding functions together

Using Fibonacci... I am Proving: $$f_3 + f_6 + \cdots + f_{3n} = \frac12(f_{3n+2}-1) $$ I did the assumption of $f_1$ which gave $\mathrm{LHS}=2=\mathrm{RHS}$. For the second part where it is $n+1$ ...
3
votes
1answer
116 views

Taylor series with Fibonacci coefficients

Let $\{a_n\}$ be the Fibonacci numbers given by $a_0=0,a_1=1,a_{n+2}=a_{n+1}+a_n$ for $n\geq 0$. Prove that $f(z)=a_0+a_1z+a_2z^2+\ldots$ is a rational function, and determine which rational ...
1
vote
1answer
64 views

Fibonacci sequences

I have the following: $$ f_3+f_6 + \dots+f_{3n} = \frac 12 (f_{3n+2}-1) $$ for $f_0=0$ and $f_1=1$ When I calculate $n\ge2$ and $f_n= f_{n-1}+f_{n-2}$, I get: LHS = 8 while RHS = 10. LHS $$f_6 ...
0
votes
1answer
96 views

Simplifying Sigma Notation

I am working on the proof on showing the ratio of two consecutive Fibonacci numbers converges to the golden ratio to explain to a student I am tutoring. I am getting to some confusion in a ...
2
votes
1answer
250 views

Exponential lower bound for Fibonacci numbers

Can someone show me how to solve through induction, $F(N) \geq (3/2)^N$ for all $N\geq N_0$, where $F(n)$ is the Fibonacci function and $N_0$ is some positive integer. I know that $N_0$ should be ...
1
vote
1answer
75 views

Proof by induction that fibonacci sequence are coprime

I have a bit difficulty to proofe that two consecutive numbers are coprime. I have the following The property $P(n)$ is the equation $(F_{n+1},F_n)=1$ where F_i the sequence of fibonacci is and $n ...
0
votes
1answer
91 views

Fibonacci Proof: Prove that $\frac{F_n-F_{n+16}}{7}$ is always an odd integer.

Im stuck on this question, i have to prove that $$\frac{F_n-F_{n+16}}{7}$$ is always an odd integer. I tried induction to do this but i just can't see how to prove it. thanks for any help
1
vote
1answer
235 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. ...
1
vote
2answers
145 views

Induction proof with Fibonacci numbers

Prove by induction that for Fibonacci numbers from some index $i > 10$ $1.5^i ≤ f_i ≤ 2^i$ Notice! Because Fibonacci number is a sum of 2 previous Fibonacci numbers, in the induction hypothesis ...
2
votes
1answer
197 views

How do I use telescopic cancellation to prove the Fibonacci Sum Identity

I am reading a textbook which attempts to prove the Fibonacci Sum Identity by rearranging the Fibonacci recurrence relation as follows and then using telescoping cancellation to prove the identity: ...
2
votes
1answer
214 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 ...
1
vote
1answer
86 views

Matrix powers and recurrence relations

The nth Fibonacci number can be found by raising the matrix $\begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix}$ to the nth power. Are there other recurrence formulas that can be solved like this? ...
0
votes
0answers
51 views

how would you represent the tribonacci spiral?

As we all know, the Fibonacci Sequence has a very famous spiral representation. Here we can see it. Now it's easy to see the fibonacci is the sum of the 2 squares that compose it to form a ...
3
votes
2answers
58 views

Gcd of every other Fibonacci number

Let $f_n$ be Fibonacci Sequence. $$gcd(f_{n},f_{n+2})=1,\quad \forall\,n\in\mathbb{N}.$$ Prove Could you help me with this one? I have done the base case, I just can't figure out the inductive step. ...
4
votes
1answer
41 views

N-binacci numbers and ratios generated by them

I was bored at home today and playing with "n-bonacci" numbers, numbers generated by $$x_0=0,x_1=1,...,x_k=k; x_n=\sum_{i=0}^{n-1}x_i$$ I made an assumption based upon the quadratic responsible for ...
3
votes
1answer
200 views

GCD of Fibonacci-like recurrence relation

What is the greatest common denominator of $t(c^a)$ and $t(c^b)$, if $t(n) := k_1 f_1^n + k_2 f_2^n $? I already found out that the gcd is always a member of $t(n), n \in N $. $t(n)$ was originally ...
0
votes
1answer
46 views

Generating Function for the adjusted Fibonacci numbers

The task is to find another relation for the adjusted Fibonacci numbers. I've found there genertaing function $$A(x)=\dfrac{1}{1-x-x^{2}}$$ Furthermore I've created the generating function in a ...
0
votes
3answers
215 views

Prove the Number of Additions of Fibonacci Number Algorithm

I am studying for a final exam and I'm having trouble with this question: The following recursive algorithm FIB takes as input an integer $n \ge 0$ and returns the $n$-th Fibonacci number $F_n$: ...
0
votes
2answers
83 views

Prove the following identity for Fibonacci numbers

Prove this: for any positive integer $a,b,c$, $F_{a+b+c+3}=F_{a+2}(F_{b+2}F_{c+1}+F_{b+1}F_c)+F_{a+1}(F_{b+1}F_{c+1}+F_bF_c)$ Is there any way other than induction to prove this?
3
votes
2answers
149 views

Finite bit strings that do not contain '$00$'

I am studying for an exam and I am having trouble with this practice question: In this question, we consider finite bit strings that do not contain $00$. Examples of such bitstrings are $0101010101$ ...