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
66 views

are there infinitely many primes in Fibonacci sequence

There is one proof about infinitude of prime with following method, http://www.ams.org/mathscinet-getitem?mr=2271540 Also it is well know that any two consecutive Fibonacci numbers are mutually ...
2
votes
4answers
129 views

Prove that $p$ divides $F_{p-1}+F_{p+1}-1$ [duplicate]

Given the Fibonacci sequence $(F_n)$, defined by $F_0=0,F_1=1, F_{n+2}=F_{n+1}+F_n$, and $p$ an odd prime number, how to prove that $p$ divides $F_{p-1}+F_{p+1}-1$? Is induction a good idea here? ...
2
votes
2answers
77 views

Sum of squares of Fibonacci Numbers

$$ \sum_{i=0}^{n} (F_{2i+1})^2 = \;?$$ I know that sum of squares of first $n$ Fibonacci numbers is $F_{n} \times F_{n+1}$.
0
votes
2answers
57 views

Proving a slight variation of the fibonacci formula using complete induction

I learned this formula for the Fibonacci series, and its respective proof in one of my Computer Science classes. F(0) = 0; F(1) = 1; F(2) = 1 However, I am taking an abstract mathematics class and ...
1
vote
1answer
38 views

Counting the sequences of coin flips that end HH after $n$ flips (a more efficient method?)

I figured out that for any given $n$ the number of sequences of heads and tails that satisfy the condition that HH wasn't flipped consecutively until flips $n-1$ and $n$ is equal to the $(n-1)$th ...
1
vote
4answers
56 views

Fibonacci sequences and related series

Let $\{a_n\}$ be a sequence such that $a_1=a_2=1$ and $a_{n+1}=a_n+a_{n-1}$ for $n\geq 2$. Prove that $\displaystyle \sum_{n=1}^\infty \frac{1}{a_n}$ converges. My work: Let $b_n=\frac{1}{a_n}$. ...
0
votes
2answers
214 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 ...
1
vote
2answers
88 views

Divisibility of $987x^n − F_nx^{16} + F_{n−16}$

If $F_n$ is $n^{th}$ Fibonacci number, and polynomials $P_n(x)$ are defined as $987x^n − F_nx^{16} + F_{n−16}$, prove that for all $n ≥ 1$, $P_n(x)$ is divisible by $x^2−x−1$. This is from a ...
1
vote
2answers
68 views

Modulus of sum of sequence of Fibonacci numbers

What is the most efficient way to find the modulus of sum of sequence of fibinacci numbers. For example (F(N) + F(N + 1) + ... + F(M)) mod 1000000007.
20
votes
6answers
449 views

Why does every “fibonacci like” series converge to $\phi$?

It's is well known that the ratio of side-by-side fibonacci numbers converge to $\phi$. But it seems by my calculations, that if one starts with any pair of numbers one will also get a ratio that ...
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, ...
0
votes
1answer
59 views

Proofs Related to the Fibonacci Sequence

I need to prove several proofs related to the Fibonacci sequence and I don't have the faintest clue how to do so. Please help! Given that the Fibonacci sequence is defined as $f_n = f_{n-1} + ...
6
votes
2answers
489 views

Fibonacci identity: $f_{n-1}f_{n+1} - f_{n}^2 = (-1)^n$

Consider this Fibonacci equation: $$f_{n+1}^2 - f_nf_{n+2}$$ The problem asked to write a program with given n, output the the result of this equation. I could use ...
2
votes
4answers
73 views

Proving this $F_{n+1} \cdot F_{n-1} - F^2_n = (-1)^n$ by induction

Where $n \in \mathbb{N}$ and $$ F_n = \begin{cases} 0 & \text{ if } n = 0 \\ 1 & \text{ if } n = 1 \\ F_{n-1} + F_{n-2} & \text{ if } n > 1 ...
-1
votes
2answers
355 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 ...
3
votes
0answers
57 views

Proving generalized Cassini's identity using determinant?

Motivation It is not hard to show, by using the general solution, that Proposition. If $(a_{n})_{n\in\Bbb{Z}}$ satisfies the recursive formula $ a_{n+2} = pa_{n+1} + qa_{n}$, then for any $n, i, ...
4
votes
5answers
96 views

Prove that $F(1) + F(3) + F(5) + … + F(2n-1) = F(2n)$

(These are Fibonacci numbers; $f(1) = 0$, $f(3) = 1$, $f(5) = 5$, etc.) I'm having trouble proving this with induction, I know how to prove the base case and present the induction hypothesis but I'm ...
1
vote
1answer
49 views

Confusion on unberstanding the proof of induction regarding Fibonacci numbers

I am trying to understand the proof that "For all $n\geq 2, F_n^2-F_{n+1}F_{n-1}=(-1)^{n-1}$.Where $F_n$ stands for the Fibonacci number at $n$. I got this proof from a book and here is the proof. ...
0
votes
2answers
40 views

Understanding Fibonacci Proof

I'm trying to show that $$F^2_{k+1} - F^2_k = F_{k-1} * F_{k+2} ∀ ≥1$$ where $$F_k = F_{k-1} + F_{k-2}$$ with $$F_0 = F_1 = 1$$ Let P(n) = $$F^2_{k+1} - F^2_k = F_{k-1} * F_{k+2}$$ Basic Step: ...
1
vote
1answer
99 views

What does $F^2_n$ mean?

In this Wikipedia entry on Cassini's identity, I saw this equation: $F_{n-1}F_{n+1}-F^2_n=(-1)^n$ $F^2_n$, what does that mean? Is it a summation signs for n to 2? I don't know what it means.
0
votes
3answers
84 views

Matrices, determinants, and applications to identities involving Fibonacci numbers

Preamble It is well known that since: $$ \begin{pmatrix} F_{n+1} \\ F_n \\ \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} F_n & F_{n-1} ...
1
vote
0answers
23 views

Fibonacci, prove that $F_{n}\cdot F_{n+2}-({F_{n+1}})^2=(-1)^n$ with induction [duplicate]

I need to prove by induction that: $$F_{n}\cdot F_{n+2}-({F_{n+1}})^2=(-1)^n$$ I did the following: Check if the statement holds for $n=1$: $$1\cdot 3-(2)^2=(-1)^1$$ Check if the statement ...
2
votes
2answers
68 views

Seven expressions involving $F_n$ an $L_n$ that are always composite

Prove that if $F_n$ an $L_n$ are Fibonacci and Lucas numbers respectively, and $n>2$, then $$F_{n-2}\times F_{n-1}\times F_{n+1}\times F_{n+2}-15$$ $$F_{n-2}\times F_{n-1}\times ...
0
votes
0answers
44 views

Induction: Fibonacci / Lucas Numbers [duplicate]

From Andrews' Number Theory, Chapter 1, Section 1, Problem 15: Prove, by induction, that $F_{2n} = F_nL_n$ where $F_n$ denotes the nth Fibonacci number and $L_n$ denotes the nth Lucas ...
6
votes
1answer
105 views

Prove or disprove that ${F_{n}^2} + 43$ is always a composite

This is a kind of follow-up to another question, but in order not to burden that question and its answers with new comments, I decided to create this separate question. Also, it looks this problem is ...
6
votes
1answer
121 views

Prove or disprove that ${F_{n}}^2 + 41$ is always a composite

The problem: Prove or disprove: If $F_{n}$ is the $n^{th}$ Fibonacci number then $${F_{n}}^2 + 41$$ is always a composite number. It looks that if $n$ is not multiple of 12, ${F_{n}}^2 + 41$ ...
6
votes
1answer
474 views

Flaw in induction proof that the Fibonacci sequence is bounded by $(5/3)^n$

The Fibonacci sequence is defined by $a_1 = 1, a_2 = 1$ and for all $n \ge 2, a_{n+1} = a_n + a_{n-1}$. Thus the sequence begins $$1,1,2,3,5,8,13,21,...$$ Prove that for all $n \ge 1, a_n ...
3
votes
4answers
9k 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
3answers
278 views

Induction proof $F(n)^2 = F(n-1)F(n+1)+(-1)^{n-1}$ for n $\ge$ 2 where n is the Fibonacci sequence [duplicate]

Prove that $F{_n}^2 = F_{n-1}F_{n+1}+(-1)^{n-1}$ for n $\ge$ 2 where n is the Fibonacci sequence F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8 and so on. Initial case n = 2: $$F(2)=1*2+-1=1$$ It is true. ...
2
votes
0answers
90 views

Who First Considered This Generalization of the Fibonacci Numbers?

I am looking for the author who originally researched a generalization of the Fibonacci numbers, which Koshy, in Chapter 7 his book Fibonacci and Lucas Numbers with Application refers to as the ...
6
votes
5answers
3k 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 ...
11
votes
5answers
246 views

Binomial Sum Related to Fibonacci: $\sum\binom{n-i}j\binom{n-j}i=F_{2n+1}$

How would I prove $$ \sum\limits_{\vphantom{\large A}i\,,\,j\ \geq\ 0}{n-i \choose j} {n-j \choose i} =F_{2n+1} $$ where $n$ is a nonnegative integer and $\{F_n\}_{n\ge 0}$ is a sequence of ...
9
votes
1answer
357 views

Construction of generating function from identity

I am trying to solve identity involving binomials and Fibonacci numbers by using generating functions: $$\sum_{k=0}^n{n \choose k}{n+k\choose k}f_{k+1}=\sum_{k=0}^n{n \choose k}{n+k\choose ...
2
votes
1answer
31 views

How can we be sure of periodicity by testing some terms?

A mod $n$ Fibonacci sequence is simply defined as the Fibonacci sequence, except all terms are in mod $n$. Now to determine periodicity, the worked solutions computed the first 20 or so terms and ...
1
vote
1answer
96 views

Function relating Euler's constant and the golden ratio

Okay, I was messing around on Excel with some coefficients and I stumbled onto this. Not sure if it converges but it gets pretty damn close around the 1024th term mark. Was wondering if somebody could ...
1
vote
2answers
142 views

Remarkable relation between Fibonacci numbers and its squares!

There is a remarkable relation between Fibonacci numbers and its squares: $F^{2}_{n} +F^{2}_{n+1}=F_{2n+1}$. I know how to prove it using $F_{n}=\frac{\sqrt{5}}{5}((\frac{1+\sqrt{5}}{2})^n ...
6
votes
4answers
5k 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 ...
5
votes
1answer
163 views

Prove Divisibility In Fibonacci Sequence Over A Prime Number

In The Fibonacci sequence which is defined as: Lets say we have the number $p$ which is an odd prime. Prove that: $F_{p-1} + F_{p+1} -1$ Is divisible by $p$. Prove that for any given $n$ real ...
4
votes
1answer
76 views

Summation of a multiple series involving Fibonacci numbers

Compute the sum $$\sum_{a_{2015} = 0}^{\infty} \sum_{a_{2014} = 0}^{a_{2015}} \sum_{a_{2013} = 0}^{a_{2014}} \cdots \sum_{a_{1} = 0}^{a_2} \sum_{k=0}^{a_1} \frac{F_{k}}{2^{a_{2015}}} $$ where $F_k$ ...
6
votes
3answers
77 views

If $f_{n-1}^2=(f_n/2)^2+h^2$ then $n=6$

How can I prove that if $f_n$ is a term of the Fibonacci sequence divisible by $4$ and if $$f_{n-1}^2=(f_n/2)^2+h^2,$$ $h\in\Bbb Z^+$ then $n=6$? I know that since $\gcd(f_k,f_{k+1})=1$ for every ...
1
vote
2answers
120 views

Prove that $F_n={n-1 \choose 0 }+{n-2 \choose 1 }+{n-3 \choose 2 }+\ldots$ where $F(n)$ is the $n$-th fibonacci number [duplicate]

If $F_n$ is the $n$-th fibonacci number, then prove that, $$F_n={n-1 \choose 0 }+{n-2 \choose 1 }+{n-3 \choose 2 }+\ldots$$ I tried the idea of using Pascal's triangle, but it seems to need some ...
1
vote
2answers
73 views

A series for Fibonacci numbers.

How can I prove The Fibonacci sequence is encoded in the number $1/89$ i.e. $( 1/89 = 0.01 + 0.001 + 0.0002 + 0.00003 + 0.000005 + 0.0000008 + 0.00000013 + 0.000000021 + 0.0000000034 \ldots)$
1
vote
2answers
45 views

Relation between series and equations

There is following quotes from wiki on Plastic number: The powers of the plastic number $A(n) = ρ^n$ satisfy the recurrence relation $A(n) = A(n − 2) + A(n − 3)$ for $n > 2$. And 2nd is that ...
4
votes
3answers
219 views

Inequality of the Fibonacci sequence and the golden ratio

How can I prove that for each $n\in\Bbb Z^+$ $$\frac{f_{2n}}{f_{2n-1}}\leq\frac{1+\sqrt{5}}{2}$$ where each $f_i$ is a term of the Fibonacci sequence. Any help is really appreciated
1
vote
2answers
54 views

Find $x$ as the given $n$th term in the Fibonacci sequence?

With a given $n$ and I am trying to find the value of $x$, as in: $$Fib(x)=n$$ Using the formula for Fibonacci sequence, where $\varphi$ is the Golden Ration ($\approx1.61803399\ldots$) $$Fib(z) = ...
2
votes
3answers
74 views

Writing $1+3x^2+8x^4+21x^6+\cdots$ as a power series representation

How would I write the power series $$1+3x^2+8x^4+21x^6+\cdots$$ as a power series representation (something neat similar to $\frac{1}{1-x}$)? This reminds me of the power series ...
1
vote
4answers
61 views

How to prove this equation by induction?

I am trying to prove this equation by mathematical induction $$f_{n+1}f_{n-1} = f_{n}^{2}+(-1)^n$$ is true where $f_{n} = $ the nth number in the Fibonacci sequence. I don't quite get how to do this ...
0
votes
2answers
36 views

Problem on deriving binet formula

I'm trying to understand binet formula. I got a good explanation here. Please look at the link. Everything just fine but one thing. It said that $A_n = A_{n-1} + A_{n-2}$, which is fibonacci. But why ...
2
votes
3answers
86 views

Showing convergence of recursive sequence $A_{n+1}=\frac 1 {1+A_n}$

Given : $\forall n\in\Bbb N,\quad A_{n+1} = \frac 1 {1+A_n}$ and $A_1 = 0$ Show the sequence converges and find its limit. Briefly what I did was to create two sub-sequences with an index ...
0
votes
1answer
60 views

Looking for $\sum_{n=1}^{\infty}\frac{1}{F_{n}F_{n+2}}$

I am looking for the sum of the series: $$\sum_{n=1}^{\infty}\frac{1}{F_{n}F_{n+2}}$$ where $F_{n}$ is the $n$-th Fibonacci number. I was thinking about splitting the fraction into 2 like in the ...