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

4
votes
5answers
1k views

Where do the first two numbers of Fibonacci Sequence come from? [duplicate]

I'm trying to code a simple algorithm that prints out the $n^{th}$ Fibonacci number. However, my program requires the initial seed values $F_0 = 0$ and $F_1 = 1$, when I'm hopeful I can figure ...
0
votes
1answer
43 views

asymptotics of $F_n = F_{k-1} F_{n-k-1} + F_{k-1} F_{n-k} + F_{k-2} F_{n-k} $

Starting from $F_n = F_{k-1} F_{n-k-1} + F_{k-1} F_{n-k} + F_{k-2} F_{n-k} $ and letting $F_k \approx \phi^k$, I am hoping to find the corresponding statement for the Golden ratio: $\phi^n = 2 ...
1
vote
0answers
103 views

I am trying to prove this problem by induction, how can can i prove the following?

I am given $$ F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}} $$ where, $\varphi = \frac{1 + \sqrt{5}}{2}$ and $\psi = \frac{1 - \sqrt{5}}{2}$ The textbook states that it's equal to the n-th Fibonacci ...
5
votes
1answer
571 views

How to prove that Fibonacci number is integer?

How to prove that formula for Fibonacci numbers are always integers, for all $n$: $$ F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}} $$ where, $\varphi = \frac{1 + \sqrt{5}}{2}$ and $\psi = \frac{1 - ...
0
votes
1answer
274 views

Proof by induction involving fibonacci numbers

The Fibonacci numbers are defined as follows: $f_0=0$, $f_1=1$, and $f_n=f_{n−1}+f_{n−2}$ for $n≥2$. Prove each of the following three claims: (i) For each $n≥0$, $f_{3n}$ is even. (ii) For each ...
1
vote
0answers
63 views

Inequality with Fibonacci numbers

The sequence $F_n$ of natural numbers defined by equation $F_{n+2}=F_{n+1}+F_{n}$, with $F_0=0, F_1=1$ is called the Fibonacci sequence. The n-th term in the sequence is called the n-th Fibonacci ...
5
votes
2answers
193 views

Number of bitstrings with $000$ as substring

I have $F_n$ number of bitstrings that have $000$, How would I prove that for $n \ge 4$ , $a_n = a_{n-1} +a_{n-2}+a_{n-3}+ 2^{n-3}$? Now there are many ways to go about this but if I choose starting ...
5
votes
1answer
288 views

Sum of digits in Fibonacci sequence

This is my first question here so please go easy on me. If you add the digits of each number on the Fibonacci sequence until your number is less than 10, it seems that you get a pattern of 24 numbers ...
4
votes
4answers
876 views

How to prove this is a rational number

I'm not sure how to prove this is a rational number $\frac{q}{m}$, can some one show me? $$\frac{q}{m}=\frac{(\frac{1+\sqrt5}{2})^n - (\frac{1-\sqrt5}{2})^n}{\sqrt5}$$
1
vote
1answer
689 views

Formula for binary sequences of length m with no n consecutive 1s?

Formula for binary sequences of length $m$ with no $n$ consecutive $1$s? I know The number of binary strings of length $m$ without consecutive $1$s is the Fibonacci number $F_{m+2}$. But how about ...
8
votes
1answer
123 views

Is this number rational or irrational?

Start writing down the Fibonacci numbers, using two digits for each one 01 01 02 03 05 08 13 21 34 55 ... Eventually you will reach three digit numbers. When ...
3
votes
1answer
164 views

Solve Recurrence Equation with Induction

Question: Given the recurrence equation for the recursive Fibonacci sequence program: $T(n) = T(n-1) + T(n-2) + b$ $T(0) = T(1) = a$ Using induction, show that $T(n) \leq f(n)$, where $f(n) = c2^n, ...
11
votes
1answer
373 views

Why does $\frac{1 }{ 99989999}$ generate the Fibonacci sequence?

$\frac{1}{99989999} = 1.00010002000300050008001300210034005500890144... \times 10^{-8}$ (Link), which includes the Fibonacci sequence $(1\ 1\ 2\ 3\ 5\ 8\ 13\ 21\ 55\ 89\ 144\ \ldots )$ This is ...
0
votes
2answers
145 views

Proving that $fib(n) < (5/3)^n$ for $n \ge 1$ by induction

I know this has been shown before here but no post really answered my question. I had this problem given to me as an induction practice problem and I couldn't solve it without help. When I got the ...
4
votes
1answer
101 views

Fibonacci numbers expressed as squares of lower Fibonacci numbers

I am no mathematician so my apologies for my ignorance. I notice that every number in the Fibonacci series can be expressed as a previous Fibonacci number squared plus or minus (alternating) another ...
2
votes
1answer
68 views

Source for relationship between $d$-ary Fibonacci numbers and generalized golden ratio?

I am not a mathematician (but a computer scientist) and stumbled across the following in the analysis of an algorithm (Berthold Vöcking: How Asymmetry Helps Load Balancing). The author gives Knuth: ...
2
votes
2answers
106 views

Internet problem solving contest question

I am trying to solve a problem from the IPSC http://ipsc.ksp.sk/2001/real/problems/f.html It basically asks to compute the following recursion. ...
0
votes
2answers
30 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 = ...
1
vote
1answer
31 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 ...
2
votes
0answers
73 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 ...
1
vote
4answers
96 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 ...
3
votes
1answer
62 views

All pairs sum to a different value

If we consider the integers $\{1,\dots,n\}$, what is the size of the largest subset $A$ so that all distinct pairs $x, y \in A$ sum to a different value? For this to make sense $(x,y)$ and $(y,x)$ ...
8
votes
1answer
355 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. ...
4
votes
3answers
224 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?
-2
votes
1answer
75 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
101 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
votes
3answers
137 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
53 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
196 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
3answers
765 views

Limit of the ratio of consecutive Fibonacci numbers [duplicate]

I have read in a book that the limit of the ratio of consequent Fibonacci numbers is the golden ratio. However, it was just mentioned thus not justified. So, my question is how would you derive the ...
2
votes
4answers
111 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
87 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
546 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 ...
2
votes
3answers
164 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
4
votes
1answer
129 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
2answers
58 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 ...
8
votes
2answers
277 views

Interpolated Fibonacci numbers - real or complex?

The common Binet-formula for the Fibonacci-numbers $$ f_n = {\varphi^n- (1-\varphi)^n \over \sqrt 5 } \small {\qquad \qquad \text{ where }\varphi={1+\sqrt 5\over 2}}$$ allows interpolation to ...
0
votes
3answers
137 views

Fibonacci divisibility

Is $2051$ a factor of any fibonacci number? It is not a factor of any perfect number. The prime factors of $2051$ are $7$ and $293$, which are both prime. the $8$th fibonacci number, is the first ...
0
votes
1answer
61 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
46 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. ...
2
votes
4answers
123 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 ...
6
votes
1answer
179 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 ...
1
vote
1answer
74 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
70 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
87 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
612 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
46 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
68 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
183 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
73 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 ...