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
63 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
80 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
336 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
41 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
124 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
104 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
271 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
77 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
92 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
244 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
204 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
89 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
53 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
59 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
202 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
47 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
225 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$ ...
5
votes
2answers
425 views

Computing nth term of fibonacci-like sequence for large n

Sum up to nth term of fibonacci sequence for very large n can be calculated in O($\log n$) time using the following approach: $$A = \begin{bmatrix} 1&1 \\\\1&0\end{bmatrix}^n$$ ...
2
votes
1answer
347 views

What is the least upper bound on the number of pairs of disjoint subsets of a binary step-order set S whose sums differ by 1?

Define a binary step-order set as a finite set S of positive integers si, i = 0 to n-1, where si ≡ 2i (mod 2i+1) for each i from 0 to n-1. So, i is the power of 2 appearing in the prime factorization ...
0
votes
1answer
131 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
131 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, ...
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 ...
0
votes
0answers
55 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 ...
2
votes
2answers
1k views

Finding index of a Fibonacci number: any mathematical solution possible?

The problem: Given a Fibonacci number,find its index. I am aware of the standard solution 'generate-hash-find'. I am just curious if there is ...
4
votes
1answer
507 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
161 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
205 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
527 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
217 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
171 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
112 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
168 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
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
0
votes
0answers
86 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
560 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}\\ ...
3
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 ...
3
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} ...
4
votes
1answer
282 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
66 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?
3
votes
1answer
125 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
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 ...