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

Find a formula for the nth Fibonacci Number [duplicate]

So I'm being asked to find a formula for the nth fibonacci number. I know the answer is $$x_{n}=\frac{(1+5^{1/2})^{n} -(1-5^{1/2})^n}{\sqrt{5}2^n}$$ However I don't really know how to get there. ...
5
votes
2answers
92 views

Prove function is Fibonacci sequence

Stuck on how to finish a question I'm working on. Have to find the number of bitstrings of length n with no odd length maximal runs of ones. For example, when n=3 there are three such bitsrings: 011, ...
16
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. ...
7
votes
3answers
174 views

Show that there are infinitely many integers such that $ \binom{m}{n-1} = \binom{m-1}{n} $

This question comes from the 1st Brazilian's IMO TST of 2004. I have found no solutions of it online, though I have developed one. After getting to $ mn = (m-n)(m-n+1) $, my solution relies on the ...
6
votes
3answers
218 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!!!
1
vote
1answer
37 views

Fibonacci Numbers, show $F_n$ $>=$ $2^{n/2}$ for n $>=$ 6.

I want to show that for the fibonacci numbers, $F_n$ $>=$ $2^{n/2}$ for n $>=$ 6. My thought was to prove this via induction. I showed the base case is true for $F_n$, n=6 and 7. I assumed ...
4
votes
2answers
87 views

Of fibonomials, pellonomials, and tribonomials, etc

I. Linear recurrence with order 2 Given the Fibonacci numbers $F_n$, we have $$\begin{aligned} &F_n+F_{n+1}-F_{n+2}=0\\[1mm] &F_n^2-2F_{n+1}^2-2F_{n+2}^2+F_{n+3}^2=0\\[1mm] ...
1
vote
1answer
51 views

Proving the Fibonacci identity $\sum_{i=1}^n f_i^2=f_nf_{n+1}$ by induction [duplicate]

I am having troubles with a proof question. Prove that for any $n\ge1$, $\sum_{i=1}^n f_i^2=f_nf_{n+1}$, where $f_n$ is the $n$'th Fibonacci number. I have the base case and the induction ...
1
vote
2answers
76 views

formula for logarithmic spiral on a linear level

I am trying to plot the contents of a circle, which include geometric elements and spirals, on a linear graph. For example, take a circle, take the beginning and the end and make it straight. What ...
2
votes
0answers
57 views

Generalizing the Fibonacci identity $F_{2n}=-F_{n-1}^2+F_{n+1}^2$

Using an integer relations algorithm, we get, $$F_{2n}=-F_{n-1}^2+F_{n+1}^2$$ $$6F_{4n}= -F_{n-2}^4-3F_{n-1}^4+3F_{n+1}^4+F_{n+2}^4$$ The pattern of the subscripts is clear. Expressing the ...
3
votes
2answers
54 views

Fibonacci recursive algorithm yields interesting result

After writing a program in Java to generate Fibonacci numbers using a recursive algorithm, I noticed the time increase in each iteration is approximately $\Phi$ times greater than the previous. ...
7
votes
4answers
755 views

Fibonacci numbers and golden ratio: $\Phi = \lim \sqrt[n]{F_n}$

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 $$ ...
10
votes
4answers
3k views

Interesting properties of Fibonacci-like sequences?

Everyone is familiar with the Fibonacci Sequence, [0] 1 1 2 3 5 8 ... and many of it's interesting properties. For example, as the sequence continues, the ratio of ...
2
votes
0answers
69 views

Transforming the cubic Pell-type equation for the tribonacci numbers

The Lucas and Fibonacci numbers solve the Pell equation, $$L_n^2-5F_n^2=4(-1)^n\tag1$$ The tribonacci numbers $z = T_n$ are positive integer solutions to the cubic Pell-type equation, $$27 x^3 - 36 ...
2
votes
2answers
1k views

Solve the recurrence of $T(n)= 3T(n-1)+1$ with$ T(0)=2$ by iteration of the recurrence

Solve the recurrence of $T(n)= 3T(n-1)+1$ with $T(0)=2$ by iteration of the recurrence. (I was told that there is no need to prove it by induction) I googled "iteration of the recurrence." I did not ...
1
vote
2answers
105 views

Need help understanding Fibonacci Fast Doubling Proof

From this website, http://www.nayuki.io/page/fast-fibonacci-algorithms (fast doubling proof close to the bottom of the page). I have understood the proof for the most part but I am struggling to see ...
36
votes
1answer
1k views

Why does this test for Fibonacci work?

In order to test if a number $A$ is Fibonacci, all we need to do is compute $5A^2 + 4$ and $5A^2 -4$. If either of them is a perfect square, the number is Fibonacci, otherwise not. Why does this test ...
2
votes
1answer
31 views

How to show that $(L_n,F_n) < 3$ (Lucas numbers and Fibonacci numbers)

While following the proof that no Fibonacci number is a perfect square larger than 144 (https://math.la.asu.edu/~checkman/SquareFibonacci.html) I stumbled in proving two of the elementary facts about ...
0
votes
0answers
70 views

An identity for the Fibonacci number $F_{n^2}$

I was manipulating Fibonacci numbers defined by : $F_0=0$ and $F_1=1$ $ \forall n\in \mathbb{N}$ $F_{n+2}=F_{n+1}+F_n$ Until I obtain this equation (which I proved) $\forall n\in \mathbb{N^*}$: ...
1
vote
1answer
69 views

Calculating the hitting probability using the strong markov property

** This problem is from Markov Chains by Norris, exercise 1.5.4.** A random sequence of non-negative integers $(F)n)_{n\ge0}$ is obtained by setting $F_0=0$ and $F_1=1$ and, once $F_0,\ldots,F_n$ are ...
1
vote
0answers
49 views

Proving an equation dealing with Fibonacci numbers

Prove that: $f(2 \cdot k) = f(k) \cdot  f(k + 1) + f(k - 1)  \cdot f(k) $ Where $f(k)$ is the kth Fibonacci number. Also prove that: $f(2 \cdot  k + 1) = f(k) \cdot f(k) + f(k + 1) \cdot f(k + 1) ...
3
votes
4answers
179 views

A calculus proof for the general term of the Fibonacci sequence [duplicate]

Let $a_0=1$,$a_1=1$ and $a_n=a_{n-1} + a_{n-2}$ for $n \geq 2$, I would like to prove: $$a_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n + 1}- \left(\frac{1-\sqrt{5}}{2}\right)^{n + ...
2
votes
4answers
115 views

Fibonacci proof question: $f_{n+1}f_{n-1}-f_n^2=(-1)^n$ [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
0answers
117 views

using induction to prove that the formula for finding the n-th term of the Fibonacci sequence is: [duplicate]

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
2answers
255 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
3answers
216 views

Statement on the Fibonacci sequence

Question: Let $n,m,\in\mathbb{N^*}$ with $n>1$ and let $u_n$ denote the $n$-th term of the Fibonacci sequence, then $$u_{n+m}=u_{n-1}u_m+u_nu_{m+1}$$ I know these theorems: Two consecutive ...
0
votes
1answer
102 views

Two issues of Number Theory

Knowing in Fibonacci sequence$$u_n\mid u_m\Longleftrightarrow n\mid m$$ Question 1: In Fibonacci sequence, show that $$5\mid u_m\Longleftrightarrow 5\mid m$$ Show: $\Longrightarrow$ In ...
0
votes
2answers
97 views

How to prove that the Fibonacci sequence $7\mid U_m\Longrightarrow 8\mid m$ and $4\mid U_m\Longrightarrow 6\mid m$

How to prove that the Fibonacci sequence $$7\mid U_m\Longrightarrow 8\mid m$$ and $$4\mid U_m\Longrightarrow 6\mid m$$I was confused because there $\{ 4,7 \}$ in Fibonacci sequece
4
votes
1answer
58 views

Closed form as sum and combinatorial of Fibonacci numbers

How can I prove that the Fibonacci numbers that are defined as $F_n=F_{n-1}+F_{n-2}, \; n \geq 2$ and $F_0=0,\ F_1=1,\ F_2=1$ have the form: $$F_n=\sum_{k=0}^{n-1} \binom{n-1-k}{k}, \; n\ge 2 $$ I ...
10
votes
4answers
279 views

Linear Combinations of Fibonacci Numbers (integer coefficients)

While working on problem #2 on Project Euler, I came across the need to express $F_n$ as a linear combination of $F_{n-3}$ and $F_{n-6}$. This is relatively simple to do: $$\begin{align} F_n &= ...
0
votes
2answers
68 views

Help with a proof involving Fibonacci numbers.

I'm working through SICP MIT course, and I'm a little lost on how to prove the following statement. I think I'm able to demonstrate it, but have no idea how to prove this statement. I may ...
7
votes
3answers
581 views

Fibonacci numbers divisible by $9$

The $n$th Fibonacci number $F_n$ is defined as follows,$$F_1=F_2=1\mbox{ and } F_{n+2}=F_{n+1}+F_{n}\mbox{ for } n\geq 1$$ I want to know how many of the first $1000$ Fibonacci numbers are divisible ...
32
votes
6answers
5k views

Proof the Fibonacci numbers are not a polynomial.

I was asked a while ago to prove there is no polynomial $P$ in $\mathbb R$ such that $P(i)=f_i$ for all $i\geq0$. I tried to get a proof as slick as possible and here's what I got. Let ...
7
votes
1answer
325 views

Irrationality of reciprocal Fibonacci constant

I read that it was proved that reciprocal Fibonacci constant $$\sum_{n} \frac{1}{F_n} = \frac{1}{1} + \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{8} + \frac{1}{13} + \frac{1}{21} ...
3
votes
0answers
148 views

What is a better comparision series for $\sum \frac {1}{F_n}$ than $\sum_0^\infty2^{-k}$?

What is a better comparision series for $\sum \frac {1}{F_n}$ than $\sum_0^\infty2^{-k}$? By better comparison series than $\sum_0^\infty2^{-k}$ we mean a series $\sum c_k$ s.t. ...
6
votes
1answer
260 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 ...
2
votes
4answers
909 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 ...
1
vote
1answer
70 views

What is wrong with the following argument involving Fibonacci and Lucas numbers?

The Lucas numbers $L_n$ are defined by the equations $L_1 = 1$, and $L_n = F_{n+1} + F_{n-1}$ for each $n \geq 2$. What is wrong with the following argument? Assuming $L_n = F_n$ for $n = ...
5
votes
5answers
284 views

Fibonacci Proof

Prove that: $$F_1F_2+F_2F_3+F_3F_4+\cdots+F_{2n-1}F_{2n}=F_{2n}^2$$ I set it up so: $$F^2(2k) + F(2k+1)F(2k+2) = F^2(2k+2)$$ I've tried: $$F(2k)^2 + F(2k+1)*F(2k+2) = ...
3
votes
4answers
46 views

Prove $F^2_{n+1} - F_nF_{n+2} = (-1)^n$

This is a question about Fibonacci sequences, a sequence in which the previous terms build up upon the current term (e.g. $F_1 + F_2 = F_3$ where $F_1 = F_2 = 1$). How would I go about proving ...
21
votes
1answer
412 views

Fibonacci-related sum

Related to this question Find a solution for f(1/x)+f(1+x)=x, what is this sum: $$\sum_{n=1}^{\infty}(-1)^n\left(\frac{F_n}{F_{n+1}}-\frac1{\phi}\right)$$ where $F_n$ is the $n$th Fibonacci number and ...
0
votes
1answer
77 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
132 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
83 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
67 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
39 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
57 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
216 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
91 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.