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

Factoring for Strong Induction for Fibonacci Sequence

Fibonacci: prove the following theorem: define the Fibonacci sequence $\left\{ a_n\right\}_{n=0}^{\infty}$ by $a_0=a_1=1$ and for integers $k>1$, $a_k=a_{k-1}+a_{k-2}$. Then, for each integer $n$, ...
1
vote
0answers
32 views

Fibonacci series and prime series [on hold]

If $a(n) = \sqrt{1}+\sqrt{1}+\sqrt{2}+\sqrt{3}+\sqrt{5}+\sqrt{8}+\sqrt{13}+....$ upto nth term and $b(n)= \sqrt{2}+\sqrt{3}+\sqrt{5}+\sqrt{7}+\sqrt{11}+.....$ upto nth term . Find the value(s) of $n$ ...
2
votes
2answers
58 views

Successively longer sums of consecutive Fibonacci numbers: pattern?

Consider the following: $$\begin{align} F_{n-1}+F_{n-2}&=F_n\\ F_{n-1}+F_{n-2}+F_{n-3}&=F_{n-1}+F_{n-1}\\ &=2F_{n-1}\\ F_{n-1}+F_{n-2}+F_{n-3}+F_{n-4}&=F_n+F_{n-2}\\ &=L_{n-1}\\ ...
0
votes
1answer
20 views

Understanding Recursive algorithm using FIB

I am studying for an exam, and I came across this question, I think I got the answer correct, just need some validation. ...
1
vote
0answers
34 views

Could Fibonacci numbers be related to Riemann zeros?

this is my question can tghe fibonacci numbers $$ F_{n+2} =F_{n+1} +F_{n} $$ be related to the zeros of the Riemann zeta function ?? i heard that in the webpage ...
7
votes
2answers
674 views

Find all integer solutions for the equation $|5x^2 - y^2| = 4$

In a paper that I wrote as an undergraduate student, I conjectured that the only integer solutions to the equation $$|5x^2 - y^2| = 4$$ occur when $x$ is a Fibonacci number and $y$ is a Lucas number. ...
0
votes
2answers
197 views

find a general expression for the remainder when a prime divides a fibonacci.

I have primes of form $5k\pm1$. Consider the equation: $F_n=f(n)\pmod p$ where $F_n$ is the nth fibonacci number. Now given a c, how can i check whether or not there exists a solution for $f(n)=c ...
1
vote
4answers
32 views

Remainder of a high fibonacci number

I found a question in my assessment book: What is the remainder when the 1995th number of the fibonacci sequence is divided by 8? How to solve?
2
votes
3answers
46 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 ...
-7
votes
0answers
44 views

Possible hidden messages in Pi [duplicate]

Assume that a proof that pi is normal existed. Is it then possible that starting at some finite position x in pi, from there >on every p(n)'th digit is 0, where p(n) is the n'th prime? I know ...
1
vote
0answers
30 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 ...
6
votes
1answer
697 views

Proof by induction on Fibonacci numbers: show that $f_n\mid f_{2n}$

I was studying Mathematical Induction when I came across the following problem: The Fibonacci numbers are the sequence of numbers defined by the linear recurrence equation- $f_n = f_{n-1} + ...
2
votes
2answers
145 views

Fibonacci using proof by induction: $\sum_{i=1}^{n-2}F_i=F_n-2$

everyone. I have been assigned an induction problem which requires me to use induction with the Fibonacci sequence. The summation states: $$\sum_{i=1}^{n-2}F_i=F_n-2\;,$$ with $F_0=F_1=1$. I ...
5
votes
3answers
929 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: ...
3
votes
1answer
62 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 = ...
0
votes
2answers
59 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 ...
2
votes
1answer
38 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 ...
2
votes
0answers
37 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.
0
votes
1answer
38 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
47 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
49 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
141 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
62 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
28 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
80 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 ...
1
vote
2answers
90 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 ...
5
votes
4answers
644 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 $$ ...
0
votes
3answers
34 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 ...
9
votes
4answers
2k views

The generating function for the Fibonacci numbers

$$1+z+2z^2+3z^3+5z^4+8z^5+13z^6+...=\frac{1}{1-(z+z^2)}$$ The coefficients are Fibonacci numbers $\left\{1,1,3,5,8,13,21,...\right\}$. Please HELP. Thanks guys.
0
votes
2answers
62 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 ...
3
votes
1answer
100 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, ...
7
votes
4answers
2k views

Fibonacci modular results

Can any one give a generalization of the following properties in a single proof? I have checked the results, which I have given below by trial and error method. I am looking for a general proof, which ...
2
votes
2answers
49 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
35 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 ...
3
votes
2answers
2k views

Roulette betting system probability

The Fibonacci is a popular Roulette betting system that is based on a naturally occurring mathematical sequence. The sequence itself is cumulative. In other words, the next number is equal to the sum ...
0
votes
1answer
26 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
2answers
90 views

What is the asymptotical bound of this recurrence relation?

I have the recurrence relation, with two initial conditions $$T(n) = T(n-1) + T(n-2) + O(1)$$ $$T(0) = 1, \qquad T(1) = 1$$ With the help of Wolfram Alpha, I managed to get the result of ...
1
vote
1answer
34 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
27 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
35 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
53 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
0answers
32 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, ...
2
votes
2answers
53 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}) / ...
6
votes
4answers
80 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 ...
38
votes
5answers
3k 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 ...
-1
votes
2answers
68 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 ...
1
vote
4answers
879 views

how to find nth term in a fibonacci series or sum of a series of fibonacci numbers

A series is given as $1,6,7,13,20,33,.......$ and so on Find the sum of first 52 terms? what i know is The sum of the first n Fibonacci numbers is the [(n + 2)nd Fibonacci number - 1] . So the sum ...
0
votes
1answer
49 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
55 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 ...
1
vote
3answers
347 views

Show that $f_0 - f_1 + f_2 - \cdots - f_{2n-1} + f_{2n} = f_{2n-1} - 1$ when $n$ is a positive integer

Letting $f_n$ be the Fibonacci numbers, show that $f_0 - f_1 + f_2 - \cdots - f_{2n-1} + f_{2n} = f_{2n-1} - 1$ when $n$ is a positive integer. Just some homework help. Need to prove. Thank you in ...