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

0
votes
2answers
100 views

Prove that a Fibonacci number is greater than $ φ^n$

How can I prove the following: If $f_n$ is a number of the Fibonacci sequence and φ= $\frac{1+\sqrt{5}}2$, then $f_n > φ^n$ for every $n >2$? I have tried using induction but I can't ...
0
votes
3answers
106 views

partial Fibonacci summation

Let $F_{n}$ be the n-th Fibonacci number. How to calculate the summation like following: $\sum_{n \geq 0} F_{3n} \cdot 2^{-3n}$
4
votes
2answers
423 views

Prove that the limit of two consecutive fibonacci numbers EXISTS. [duplicate]

Using the definition of Fibonacci numbers, $F_n=F_{n-1}+F_{n-2}$, I can prove that the limit of $\frac{F_{n+1}}{F_n}$ as $n\to\infty$ is $\phi$ if we assume that the limit exists. How can we prove ...
1
vote
1answer
141 views

Calculate Number of ways to make the grid

We wish to tile a grid of size Nx2 with rectangles (dominoes) of 2x1 (in either orientation).For given N I need to find the number of different ways to tile the grid. EXAMPLE : For N=1 answer is 1 ...
0
votes
0answers
56 views

Sequence of $r_n:=\frac{x_{n+1}}{x_n}$ where $x_n$ is a sequence

Let $f:X\rightarrow X$ be a function on some complete metric space $(X,d)$. Let, $x_n$ is a sequence in the metric space defined by $x_{n+1}=f(x_n)$ and starting from $x_0$. My questions are (1) ...
1
vote
3answers
111 views

How to go about solving this recurrence relation?

In my discrete math class we were given the problem of finding an explicit formula for this recurrence relation and proving its correctness via induction. $$a_n=2a_{n-1}+a_{n-2}+1, a_1 = 1, a_2=1.$$ I ...
2
votes
4answers
141 views

For the Fibonacci sequence prove that $\sum_{i=1}^n F_i= F_{n+2} - 1$

For the Fibonacci sequence $F_1=F_2=1$, $F_{n+2}=F_n+F_{n+1}$, prove that $$\sum_{i=1}^n F_i= F_{n+2} - 1$$ for $n\ge 1$. I don't quite know how to approach this problem. Can someone help and ...
4
votes
5answers
923 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
42 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
100 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
557 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
232 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
58 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
187 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
255 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
786 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
594 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
119 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
152 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
357 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
121 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
99 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
66 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
105 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
72 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
95 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
305 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
212 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
74 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
97 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
130 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
50 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
189 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
568 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
79 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
466 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
143 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
127 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
260 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
120 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
121 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
175 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
69 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 ...