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
44 views

Why is $\sum_{k=0}^{n} f(n,k) = F_{n+2}$?

If $f(n,k)$ is the number of $k$ size subsets of $[ n ] = { 1 , \ldots , n }$ which do not contain a pair of consecutive numbers, how can I show that $\sum_{k=0}^{n} f(n,k) = F_{n+2}$? ($F_{n}$ is the ...
2
votes
4answers
113 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
56 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
40 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
60 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
70 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
206 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
38 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
65 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
83 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
55 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
85 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
181 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
45 views

Fibonacci combinatorial identity

Can someone explain how to prove the following identity involving Fibonacci sequence $F_n$ $F_{2n} = {n \choose 0} F_0 + {n\choose 1} F_1 + ... {n\choose n} F_n$ ?
1
vote
1answer
67 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
78 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
197 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
134 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
172 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
212 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
67 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
47 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 ...
7
votes
3answers
294 views

Significance of starting the Fibonacci Series with 0, 1…

DISCLAIMER: I do not deal with in-depth mathematics on a daily basis as some of you may, so please pardon my ignorance or lack of coherence on this topic. QUESTION: What is the significance of ...
3
votes
1answer
174 views

Number of Fibonacci numbers in a range

The definition of the Fibonacci numbers is given by: $$\begin{align}f_1 &= 1;\\ f_2 &= 2;\\ f_n &= f_{n-1} + f_{n-2},\qquad (n >= 3); \end{align}$$ now we are given two numbers $a$ ...
1
vote
3answers
106 views

A Non-recursive Fibonacci Sequence

How can I determine the general term of a Fibonacci Sequence.It is impossible for any one to calculate F2013 and large numbers like this. Is there a general formula for the nth term of the Fibonacci ...
3
votes
2answers
52 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. ...
3
votes
1answer
39 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
181 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
43 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
180 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
140 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$ ...
2
votes
3answers
3k views

Help with Induction proof on Fibonacci sequence?

I can't seem to solve this problem. It is: The Fibonacci numbers $F(0), F(1), F(2),\dots $ are defined as follows: $F(0) ::= 0$ $F(1) ::= 1$ $F(n) ::= F(n-1) + F(n-2)\qquad(\forall n \ge 2 $) ...
5
votes
2answers
346 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
345 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
120 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
118 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
0answers
198 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 ...
0
votes
0answers
225 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
162 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
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
309 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
134 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
182 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) ...
1
vote
3answers
355 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
906 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
172 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
29 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 ...