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
1answer
114 views

Fibonacci series mod a number

I'm trying to write a program with an input of numbers $n$ and $k$ (where $n<10^{20}$ and $k<10^9$), where I compute fib[n] % k. What is a good FAST way of computing this? I have read many ...
3
votes
3answers
257 views

Fibonacci Sequence, Golden Ratio

I've been asked to show that $x_n \rightarrow L$ as $n \rightarrow \infty$ where $x_n = F_{n+1}/F_{n}$ for $n \in \mathbb{Z}^+$, where $F_n$ denotes the $n^{th}$ Fibonacci number. I am supposed to use ...
5
votes
3answers
981 views

Fibonacci trick and proving it. [duplicate]

I am trying to learn Fibonacci tricks and I have one that I can not prove. I know it works because Ive tried it multiple times but I have not a clue how to prove. Here it is: ...
0
votes
2answers
69 views

Interesting a Fibonacci quesiton. Need help.

Alice claims that she knows another formula for the Fibonacci numbers: Fn = $e^{n/2−1}$ for $n = 1,2,\cdots$ (where $e = 2.718281828$... is, naturally, the base of the natural logarithm). Is she ...
3
votes
1answer
81 views

Question about generating function of kind of fibonacci partial sum

$F_n$ here is $n$-th fibonacci number We know that $$\sum_{n=0}^\infty \left(\sum_{k=0}^n F_kF_{n-k}\right)x^n$$ is a generating function of multiplying two G.F: $a_n =\langle F_n \rangle$ and $b_n = ...
2
votes
0answers
53 views

Summation involving Fibonacci numbers

Find: $$ \sum_{n=0}^\infty \sum_{k=0}^n \frac{F_{2k}F_{n-k}}{10^n} $$ where $F_n$ is $n$-th Fibonacci number.
2
votes
1answer
133 views

Help with induction proof for formula connecting Pascal's Triangle with Fibonacci Numbers

I am in the middle of writing my own math's paper on the topic of Pascal's Triangle. During the investigation I have came up with a formula for counting elements of Fibonacci Sequence using the ...
0
votes
1answer
52 views

Fibonacci Proof with Induction [duplicate]

$$f(n) = \left\{\begin{matrix} 0 & n=1\\ 1 & n=2\\ f_{n-1} + f_{n-2} & n\geqslant 2\end{matrix}\right.$$ How can I prove by induction that $$f_{n} \geq \left ( 1.5 \right )^{n-1}$$ ...
2
votes
2answers
69 views

Fibonacci Proof Using Induction

$$f(n) = \left\{\begin{matrix} 0 & n=1\\ 1 & n=2\\ f_{n-1} + f_{n-2} & n\geqslant 2\end{matrix}\right.$$ How can I prove by induction that $$f_{n} \leq \left ( \frac{1+\sqrt{5}}{2} ...
2
votes
1answer
84 views

Fibonacci proof by induction

I have fibonacci numbers defined as such: $$ f(n) = f(n-1) + f(n-2)$$with$$ f(0) = 0 $$$$f(1) = 1$$ I have to prove that $$ F(n) \geq 1.5^{n-1}, n \geq 6$$ Base Case: $$ f(6) = 8 \geq (1.5)^5 ...
3
votes
1answer
168 views

What is the sum of Fibonacci reciprocals?

How can I calculate $\sum\limits_{n=1}^{\infty}\frac{1}{F_n}$, where $F_0=0$, $F_1=1$ and $F_n=F_{n-1}+F_{n-2}$? Empirically, the result is around $3.35988566$. Is there a "more mathematical way" to ...
3
votes
1answer
92 views

A Fibonacci series

Let $F_n$ be the $n^{th}$ term of the Fibonacci sequence. That is, $F_1 = F_2 = 1$ and $F_n$ is defined recursively for $n\geq3$ by $F_n = F_{n-2}+F_{n-1}$. It is a known fact that $$ ...
0
votes
1answer
36 views

how to use Newton's polynomials calculate this?

Say we have Fibonacci recurrence: $ F_{n+2}=F_{n+1}+F_n$, with $F_0=1,F_1=1$ We can write $F_n = a \alpha^n + b \beta ^n$, so how do we use Newton's polynomials to determine the value of $\alpha^r + ...
3
votes
2answers
96 views

a manipulation of Fibonacci recurrence

Let $F_n$ be the Fibonacci number, and we know $F_{n+2} = F_{n+1} + F_{n} $ with $F_0 =1,F_1 = 1$ And this can be manipulated to $F_{n+6} = 4F_{n+3} + F_n$ if we let n be a multiple of 3, we can ...
2
votes
2answers
126 views

Sum $\frac{1}{1\times2}+\frac{1}{1\times3}+\frac{1}{2\times5}+\frac{1}{3\times8}+\cdots$

If $f_n$ is the Fibonacci series, with $1,1,2,3,5,8,\ldots$ prove that $$\sum_{i=2}^\infty\frac{1}{f_{i-1}\cdot f_{i+1}} = 1$$ So my idea was to try to convert this series into a telescoping sum ...
6
votes
4answers
703 views

Fibonacci numbers and golden ratio

Let $\Phi$ be the golden ratio and $F_n$ be the usual Fibonacci numbers. How can I derive the following formula? $$ \Phi = \lim_{n\rightarrow \infty} \sqrt[n]{F_n} $$ I know the usual relation $$ ...
1
vote
3answers
52 views

Prove the given property of the Fibonacci numbers

I found in one of the books I read a lot of interesting properties of fibonacci numbers and among others this one in particular: For all $n \in \mathbb N$, $F_{n+1} F_{n-1} - F_n^2 = (-1)^n$. I ...
0
votes
2answers
83 views

Limit of ratio of successive n-nacci numbers?

The n-nacci numbers are defined as $${}_nF_k = {}_nF_{k - 1} + {}_nF_{k - 2} + \cdots + {}_nF_{k - n + 1}$$ Now, it's pretty well-known that the limit of successive $2$-nacci numbers (i.e. the ...
2
votes
2answers
78 views

What is the relation between this binary number with no two 1 side by side and fibonacci sequence?

I saw this pattern of binary numbers with constraints first number should be 1 , and two 1's cannot be side by side. Now as an example ...
1
vote
2answers
64 views

Generating function for squared fibonacci numbers

We know that generating function for fibonacci numbers is $$B(x)=\frac{x}{1-x-x^2}$$ How can we calculate $B(x)^2$? I thought that, if we have $B(x)=F_n*x^n$ then $$B(x)*B(x) = \sum_{n=0}^\infty ...
0
votes
1answer
41 views

Generating function for kind of sum of Fibonacci numbers

Let's have a sequence $$a_n = \sum_{i=0}^n F_iF_{n-i}$$ where $F_n$ is n-th Fibonacci number. I tried to solve it somehow, but i'm pretty stuck. Defining Fibonacci numbers $$b_0=0, b_1=1, ...
1
vote
1answer
41 views

How do I calculate the number of members in a limited Fibonacci series? [duplicate]

Looking for an algorithm that will give me the number of members that will result from calculating a Fibonacci series, given a particular limit. For example, if I start the series at 1 and limit my ...
0
votes
1answer
53 views

Generalisation of Fibonacci

Somehow a generalisation of the fibonacci numbers, do numbers created by the formula $ F(n) = F(n-1) + [F(n-1)-F(n-2)+F(n-3)-F(n-4)+F(n-5)-F(n-6).....]$ with $F(1) = 1$ have a specific name?
0
votes
2answers
59 views

Fibonacci Sequence and odd/even addition [duplicate]

Prove that f0 – f1 + f2 - … - f2n-1 + f2n = f2n-1 – 1. For n is all positive numbers. I have an idea to what I must do, but I can't figure what the base case is. I think it is f(0) = 0 and f(1) = 1. ...
2
votes
1answer
80 views

No advantage to the closed form for Fibonacci numbers?

The closed forms for the Fibonacci sequence, such as: $$F_n=\frac{\varphi^n-\widehat\varphi^n}{\sqrt5}=\frac{\varphi^n}{\sqrt5}-\frac{\widehat\varphi^n}{\sqrt5}\;,$$ the Binet formula, do not seem ...
1
vote
1answer
62 views

Question on Proof that the Fibonacci Word is Sturmian

I am currently reading a text where it is proved that the infinite Fibonacci Word $u$ defined as the limit of the sequence $$ u_n = \varphi^n(0) $$ where the morphism is given by $\varphi(0) = 01, ...
6
votes
4answers
95 views

Proof by induction that if $n \in \mathbb N$ then it can be written as sum of different Fibonacci numbers

Proof that every natural number $n\in \mathbb N$, can be written as the sum of different Fibonacci numbers between $F_2,F_3,\ldots,F_k,\ldots$. For example: $32 = 21 + 8+3 = F_8+F_6+F_4$ Research ...
2
votes
2answers
64 views

Proof by induction of a Fibonaci relation [duplicate]

We know: $F_0 = 0$ $F_1 = 1$ $F_i = F_{i-1} + F_{i-2}$ for $i \geq 2$ Prove by induction: $F_i = \dfrac{\phi^i-{\phi^{*}}^i}{\sqrt{5}}$ where $\phi = (1+\sqrt{5}) / 2$ and $\phi = (1-\sqrt{5}) / ...
-1
votes
2answers
212 views

how to find nth term of different fibonacci series with golden ratio [duplicate]

what i know : if i want to find $Nth$ term of a fibonacci series like : 1 1 2 3 5 8 13 21 ....... then to find $6th$ term we use golden ratio ...
0
votes
1answer
312 views

Fibonacci proof by Strong Induction

Prove by strong induction that for a ∈ A we have $F_a + 2F_{a+1} = F_{a+4} − F_{a+2}.$ $F_a$ is the $a$'th element in the Fibonacci sequence
1
vote
5answers
147 views

Limit of Ratio of Adjacent Fibonacci numbers $\to \phi$ [duplicate]

We define the $n^{th}$ Fibonacci number as $a_1 = a_2 = 1$ and $a_n = a_{n-1} + a_{n-2}$ for $n \geq 3$. Consider $$ \lim_{n \to \infty} \frac{a_{n+1}}{a_n}. $$ I wrote a script and found that this ...
43
votes
5answers
4k views

Does every prime divide some Fibonacci number?

I am tring to show that $\forall a \in \Bbb P\; \exists n\in\Bbb N : a|F_n$, where $F$ is the fibonacci sequence defined as $\{F_n\}:F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$ $(n=2,3,...)$. How can ...
0
votes
2answers
103 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
119 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
497 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
151 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
120 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
144 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
974 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
102 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
564 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
263 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
62 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
192 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
283 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
847 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
643 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 ...