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

11
votes
4answers
5k 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 ...
21
votes
4answers
12k views

The generating function for the Fibonacci numbers

Prove that $$1+z+2z^2+3z^3+5z^4+8z^5+13z^6+...=\frac{1}{1-(z+z^2)}$$ The coefficients are Fibonacci numbers, i.e., the sequence $\left\{1,1,2,3,5,8,13,21,...\right\}$.
7
votes
4answers
8k views

Prove this formula for the Fibonacci Sequence

This formula provides the $n$th term in the Fibonacci Sequence, and is defined using the recurrence formula: $u_n = u_{n − 1} + u_{n − 2}$, for $n > 1$, where $u_0 = 0$ and $u_1 = 1$. Show that ...
12
votes
8answers
2k views

Showing that an equation holds true with a Fibonacci sequence: $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$

Question: Let $F_n$ the sequence of Fibonacci numbers, given by $F_0 = 0, F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$. Show for $n, m \in \mathbb{N}$: $$F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$$ ...
8
votes
3answers
1k views

How to prove that $\lim \limits_{n\rightarrow \infty} \frac{F_{n+1}}{F_n}=\frac{\sqrt{5}+1}{2}$

How would one prove that $$\lim_{n\rightarrow \infty} \frac{F_{n+1}}{F_n}=\frac{\sqrt{5}+1}{2}=\varphi$$ where $F_n$ is the nth Fibonacci number and $\varphi$ is the Golden Ratio?
6
votes
5answers
4k views

How to show that this binomial sum satisfies the Fibonacci relation?

The binomial sum $$s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots$$ satisfies the Fibonacci relation. I failed to prove that $\binom{n-k+1}{k}=\binom{n-k}{k}+\binom{n-k-1}{k}$... Any ...
8
votes
3answers
834 views

Proof of this result related to Fibonacci numbers: $\begin{pmatrix}1&1\\1&0\end{pmatrix}^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}$?

$$\begin{pmatrix}1&1\\1&0\end{pmatrix}^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}$$ Somebody has any idea how to go about proving this result? I know a proof by ...
17
votes
2answers
1k 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. ...
8
votes
7answers
1k views

Prove the following equality: $\sum_{k=0}^n\binom {n-k }{k} = F_n$ [duplicate]

I need to prove that there is the following equality: $$ \sum\limits_{k=0}^n {n-k \choose k} = F_{n} $$ where $F_{n}$ is a n-th Fibonacci number. The problem seems easy but I can't find the way to ...
6
votes
2answers
2k views

Inductive proof of the closed formula for the Fibonacci sequence [duplicate]

Fibonacci numbers $f(n)$ are defined recursively: $f(n) = f(n-1) +f(n-2)$ for $n > 2$ and $f(1) = 1$, $f(2) = 1$. They also admit a simple closed form: $$\sqrt 5 f( n ) = \left(\dfrac{1+ \sqrt ...
9
votes
4answers
3k views

Fibonacci sequence divisible by 7?

Make and prove a conjecture about when the Fibonacci sequence, $F_n$, is divisible by $7$. I've realized it's when $n$ is a multiple of $8$. I just don't know how to go about proving it.
8
votes
3answers
1k views

Prove by induction Fibonacci equality

[question:] Prove by induction that the i th Fibonacci number satisfies the equality $$F_i=\frac{\phi^i-\hat{\phi^i}}{\sqrt5}$$where $\phi$ is the golden ratio and $\hat{\phi}$ is its conjugate. ...
2
votes
2answers
535 views

Inductive proof of a formula for Fibonacci numbers

May someone help me? I am trying to use induction to prove that the formula for finding the $n$-th term of the Fibonacci sequence is: ...
2
votes
1answer
971 views

Causal Inverse Z-Transform of Fibonacci

Say the Fibonacci sequence is defined by: $y(n) = y(n-1) + y(n-2)$ initial conditions: $y(0)=0, y(1)=1$ I incorporate those initial conditions as: $y(n) = y(n-1) + y(n-2) + \delta(n-1)$ ...
21
votes
1answer
11k views

Prove that two any consecutive terms of Fibonacci sequence are relatively prime

Prove that two any consecutive terms of Fibonacci sequence are relatively prime My attempt: We have $f_1 = 1, f_2 = 1, f_3 = 2...$. So obviously $\gcd(f1, f2) = 1$. Suppose that $\gcd(f_n, ...
65
votes
4answers
4k views

Fibonacci number that ends with 2014 zeros?

This problem is giving me the hardest time: Prove or disprove that there is a Fibonacci number that ends with 2014 zeros. I tried mathematical induction (for stronger statement that claims that ...
33
votes
5answers
12k views

Checking if a number is a Fibonacci or not?

The standard way (other than generating up to $N$) is to check if $(5N^2 + 4)$ or $(5N^2 - 4)$ is a perfect square. What is the mathematical logic behind this? Also, is there any other way for ...
17
votes
3answers
990 views

How to prove the Fibonacci sum $\sum \limits_{n=0}^{\infty}\frac{F_n}{p^n} = \frac{p}{p^2-p-1}$

We are familiar with the nifty fact that given the Fibonacci series $F_n = 0, 1, 1, 2, 3, 5, 8,\dots$ then $0.0112358\dots\approx 1/89$. In fact, $$\sum_{n=0}^{\infty}\frac{F_n}{10^n} = ...
2
votes
1answer
1k views

Recurrence relation, Fibonacci numbers

$(a)$ Consider the recurrence relation $a_{n+2}a_n = a^2 _{n+1} + 2$ with $a_1 = a_2 = 1$. $(i)$ Assume that all $a_n$ are integers. Prove that they are all odd and the integers $a_n$ and $a_{n+1}$ ...
4
votes
2answers
2k views

Fibonacci, tribonacci and other similar sequences

I know the sequence called the Fibonacci sequence; it's defined like: $\begin{align*} F_0&=0\\ F_1&=1\\ F_2&=F_0+F_1\\ &\vdots\\ Fn&=F_{n-1} + F_{n-2}\end{align*}$ And we ...
2
votes
2answers
174 views

Question regarding the Fibonacci sequence

Given the Fibonacci sequence $(F_1, F_2,F_3, ...)$ how do I prove that if $m|n$ then $F_m|F_n$? Can this be proven with mathematical induction?
26
votes
3answers
1k 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 ...
5
votes
4answers
2k 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}$$
9
votes
3answers
680 views

Significance of starting the Fibonacci sequence 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 ...
6
votes
1answer
1k views

Sum of product of Fibonacci numbers

I want to calculate the sum of product of Fibonacci number for a given $n$. That is, for given $n$, say $$F_1 F_n + F_2 F_{n-1} + F_3 F_{n-2} + F_4 F_{n-3} + F_5 F_{n-4} + \cdots.$$ what should be ...
4
votes
4answers
14k views

Induction proof on Fibonacci sequence: $F(n-1) \cdot F(n+1) - F(n)^2 = (-1)^n$

I can't seem to solve this problem. It is: The Fibonacci numbers $F(0), F(1), F(2),\dots $ are defined as follows: \begin{align} F(0) &::= 0 \\ F(1) &::= 1 \\ F(n) &::= F(n-1) + ...
2
votes
4answers
604 views

Divisibility and the Fibonacci sequence

While studying the Fibonacci sequence I encountered this problem in the handout, and I can not understand how to do it. Show that if the Fibonacci sequence has a term divisible by a natural number ...
5
votes
4answers
4k views

Induction Proof: Fibonacci Numbers Identity with Sum of Two Squares

Using induction, how can I show the following identity about the fibonacci numbers? I'm having trouble with simplification when doing the induction step. Identity: $$f_n^2 + f_{n+1}^2 = f_{2n+1}$$ I ...
1
vote
2answers
962 views

Summation of series of product of Fibonacci numbers

What is the sum of following product of Fibonacci numbers $$\sum_{k=1}^{n-1} Fib(k)*Fib(n+3-k)$$ can anyone suggest only approach to find general term?
47
votes
5answers
5k 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 ...
12
votes
3answers
1k views

Infinite Series: Fibonacci/ $2^n$

I presented the following problem to some of my students recently (from Senior Mathematical Challenge- edited by Gardiner) In the Fibonacci sequence $1, 1, 2, 3, 5, 8, 13, 21, 34, 55,\ldots$ each ...
18
votes
1answer
2k views

Combinatorial proof of a Fibonacci identity: $n F_1 + (n-1)F_2 + \cdots + F_n = F_{n+4} - n - 3.$

Does anyone know a combinatorial proof of the following identity, where $F_n$ is the $n$th Fibonacci number? $$n F_1 + (n-1)F_2 + \cdots + F_n = F_{n+4} - n - 3$$ It's not in the place I thought it ...
7
votes
1answer
925 views

Another way to go about proving the limit of Fibonacci's sequence quotient.

It is not difficult to inductively prove that $$\eqalign{ & \phi = \phi + 0 \cr & {\phi ^2} = \phi + 1 \cr & {\phi ^3} = 2\phi + 1 \cr & {\phi ^4} = 3\phi + 2 ...
4
votes
5answers
487 views

Proof by induction: $n$th Fibonacci number is at most $ 2^n$

I'm trying to find the proof by induction of the following claim: For all $n\in\mathbb N$, $\operatorname{fibonacci}(n) \le 2^n$ My Proof: Base case: $n = 1$ $\operatorname{fibonacci}(1) \le 2^ 1$ ...
4
votes
4answers
2k views

For the Fibonacci numbers, show for all $n$: $F_1^2+F_2^2+\dots+F_n^2=F_nF_{n+1}$

The definition of a Fibonacci number is as follows: $$F_0=0\\F_1=1\\F_n=F_{n-1}+F_{n-2}\text{ for } n\geq 2$$ Prove the given property of the Fibonacci numbers for all n greater than or equal to 1. ...
9
votes
4answers
2k views

Proof by Induction: Alternating Sum of Fibonacci Numbers [duplicate]

Possible Duplicate: Show that $f_0 - f_1 + f_2 - \cdots - f_{2n-1} + f_{2n} = f_{2n-1} - 1$ when $n$ is a positive integer This is a homework question so I'm looking to just be nudged in ...
5
votes
2answers
223 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 ...
1
vote
3answers
71 views

Cesaro identity for Fibonacci numbers

I am stuck with the identity $$ F_{2n} = \sum_{k=1}^n \binom{n}{k} F_k, $$ which happens to be formula 80. I am using induction, but so far without too much result. $$ \sum_{k=1}^{n+1} ...
37
votes
5answers
909 views

Is ${F_{n}}^2 - 28$ always a composite number?

The problem is as follows: Prove or disprove that if ${F_{n}}$ is $n$-th Fibonacci number, and $n>5$, than $${F_{n}}^2 - 28$$ cannot be a prime. I came across this problem accidentally ...
21
votes
17answers
24k views

Applications of the Fibonacci sequence

The Fibonacci sequence is very well known, and is often explained with a story about how many rabbits there are after $n$ generations if they each produce a new pair every generation. Is there any ...
15
votes
5answers
3k views

Is it true that the Fibonacci sequence has the remainders when divided by 3 repeating?

About this Fibonacci sequence, is it true that the remainders when divided by three repeat along with the sequence like this: Fibonacci sequence: $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...
5
votes
1answer
183 views

conjectured new generating function of fibonacci numbers

I conjecture a new generating function for the fibonacci numbers $F_{n}$. Given,the following conjectured q-continued fraction ...
8
votes
2answers
5k views

How to prove Fibonacci sequence with matrices? [duplicate]

How do you prove that: $$ \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n\\ F_{n} & F_{n-1} \end{pmatrix}$$
6
votes
1answer
644 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 - ...
14
votes
2answers
603 views

Fibonacci[n]-1 is always composite for n>6. why?

In[11]:= Select[Table[Fibonacci[n], {n, 1, 10000}], PrimeQ[# - 1] &] Out[11]= {3, 8} Edit: Fibonacci[n]-1 is always composite for n>6. why? $$\sum\limits_{i = 0}^n {{F_i}} = {F_{n + 2}} - 1$$ ...
4
votes
1answer
3k views

Induction Proof: Formula for Sum of n Fibonacci Numbers

I am stuck though on the way to prove this statement of fibonacci numbers by induction : my steps: definition: $F_{0}:=0, F_{1}:=1 $ and $F_{n}:=F_{n-1}+F_{n-2}$ The Hypothesis is: $\sum_{i=0}^{n} ...
3
votes
2answers
263 views

Another Fibonacci identity

Here's a problem that is leading me in circles. Consider the Fibonacci number $F_n$ defined by $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for all $n \geq 2$. Prove that $F_{2n-1} = F_{n}^2 ...
5
votes
3answers
269 views

Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$

Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$; I was stuck with this question for a while... Help me please!!! Thanks!!!
3
votes
3answers
368 views

Another way to go about proving Binet's Formula

As I showed in another question of mine, it is easy to prove that $$\tag{1}\phi^{n+1} =F_{n+1} \phi+F_{n }$$ given $F_1=1$ , $F_2=1$ , $F_{n+1}=F_n+F_{n-1}\text{ ; }n\geq2$. Now, extending $(1)$ ...
2
votes
1answer
241 views

If $m$ and $n$ are positive integers, then $(F_m,F_n)=F_{(m,n)}$. [duplicate]

Edit: The $F$'s are Fibonacci numbers. I need an idea on how to show the following: If $m$ and $n$ are positive integers, then $(F_m,F_n)=F_{(m,n)}$. I believe that using the fact that ...