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

2
votes
2answers
553 views

Proving that for Fibonacci numbers $a_n \lt (\frac {1 + \sqrt 5} 2)^n$ for $n \ge 1$

I'd like to prove that for Fibonacci numbers $a_n \lt \left(\frac {1 + \sqrt 5} 2\right)^n$ for $n \ge 1$. I suppose it needs induction so, after verifying the trivial case $n=1$, the inductive step ...
1
vote
3answers
144 views

Use induction to prove that $F_n \ge \sqrt 2 ^n$ for $n \ge 6$

The Fibonacci sequence $F_0, F_1, F_2,\dots$ is defined by the rule $F_0=0, \ F_1=1, \ F_n = F_{n−1} + F_{n−2}$. Use induction to prove that $F_n \ge \sqrt 2 ^n$ for $n \ge 6$. So for the base case: ...
0
votes
3answers
179 views

Prove $F(n) < 2^n$ [closed]

Consider the Fibonacci function $\large{F(n)}$, which is defined such that $F(1) = 1, F(2) = 1$, and $F(n) = F(n−2)+F(n−1)$ for $n > 2$ I know that I should do it using mathematical induction but ...
4
votes
1answer
78 views

Fibonacci Numbers, show $F_n \ge 2^{n/2}$ for $n \ge 6$. [duplicate]

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 ...
1
vote
2answers
92 views

Proof by mathematical induction - Fibonacci numbers and matrices

Using mathematical induction I am to prove: $ \left( \begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array} \right)^n $ = $ \left( \begin{array}{ccc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{...
1
vote
1answer
30 views

Prove that $F_n < 2^n$ for every $n \geq 0$ - Mathematical induction

The Fibonacci sequence $0$, $1$, $1$, $2$, $3$, $5$, $8$, $13$, ... is defined as a sequence whose two first terms are $F_0=0$, $F_1=1$ and each subsequent term is the sum of the two previous ones: $...
2
votes
2answers
416 views

The number $\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$ is always an integer

For each $n$ consider the expression $$\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$ I am trying to prove by induction that this is an ...
-1
votes
3answers
227 views

Fibonacci Sequence or Golden Ratio?

Using the polar coordinate system, $r$ increases directly with $\theta$. In other words, $r=k\theta$. Which of the following shapes is constructed? A) Fibonacci Sequence B) Golden Ratio C) ...
2
votes
0answers
35 views

$|x^2-xy-y^2|=1$ implies that $x=\pm F_{n+1},\; y=\pm F_n$

So I've proved that $ A= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \implies A^n= \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1} \end{pmatrix} $ for Fibonacci numbers $F_i$. I'm ...
2
votes
1answer
42 views

How to apply geometric series concepts into these numbers?

This is a basic level question and it is homework for someone that I am trying to help out. It is indicated as a Fibonacci puzzle. But I am not able to fit the numbers into a general geometric formula....
1
vote
1answer
53 views

Are any factors of Lucas numbers divisible by a Fibonacci number greater than three?

The congruence relation for Fibonacci and Lucas numbers is stated: If Fn > 3 is a Fibonacci number then no Lucas number is divisible by Fn. However, does this apply to the factors as well?
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.
2
votes
2answers
66 views

Proving a Fibonacci identity: $F_{2n} = F_n (F_{n+1} + F_{n-1})$

$$ F_{2n} = F_n (F_{n+1} + F_{n-1}) $$ I'm so stuck. I've used the definition of Fibonacci to change $F_{2n+2}$ into $F_{2n+1} + F_{2n}$. Can't use other properties, only the inductive hypothesis and ...
1
vote
1answer
49 views

Clarification on tribonacci numbers exercise

From what I know the Tribonacci sequence is given by: T(n) = T(n-1) + T(n-2) + T(n-3) My book says that "We can show by induction that for large enough n, the Fibonacci numbers satisfy the ...
1
vote
0answers
44 views

Fibonacci numbers notation

$F_{i}$ denotes the $i^{th}$ Fibonacci number, but what does it mean when there are 2 subscripts, $F_{ij}$? Context: show that $F_{i}$|$F_{ij}$ (where $i$ and $j$ are positive integers) Thanks
6
votes
1answer
85 views

Summation of a series involving powers of Fibonacci numbers.

I'm interested in this series: $$\mathcal S_p=\sum_{n=1}^\infty\frac{\left(F_n\right)^p}{2^{np}},\quad p\in\mathbb N,\tag1$$ where $F_n$ are the Fibonacci numbers, defined by the recurrence $$F_1=1,\...
21
votes
17answers
27k 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 ...
1
vote
1answer
31 views

Fibonacci clarification

As explained in Excursion 4.5, the Fibonacci numbers are defined by the rules: F(0) = 0, F(1) = 1, and for all n with n ≥ 2, F(n) = F(n-1) + F(n-2). Which of these claims about the Fibonacci numbers ...
11
votes
3answers
2k 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?
0
votes
2answers
61 views

Induction proof fibonacci numbers

I need to prove the following with induction: n∑i=1 F(2i-1) = F(2n) for all n >= 1 I am stuck in my inductive step: n∑i=1 F(2i-1) = n∑i=1 F(2i-1) + F(2(n + 1) -1) = F(2n) + F(2(n + 1)-1) =...
9
votes
3answers
1k 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 ...
3
votes
2answers
232 views

Fibonacci and Matrices [duplicate]

Consider Matrix $$ A = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix} $$ Investigate the sequence of powers of $A$ (i.e. $A^n$ for $n = 1, 2, 3, 4,\ldots$. Verify that $$A^n = \begin{pmatrix}F_{...
0
votes
3answers
155 views

Finding $a \bmod b$ where $a,b$ are large Fibonacci numbers

For moderately large values of $b$ we can use Chinese Remainder Theorem, by factorizing $b$. But for very large values of $b$, (for example $b$ is the 1000th Fibonacci number) factorization will take ...
13
votes
2answers
176 views

Remainders of Fibonacci numbers

Let $a>b$ be positive integers. Is there a Fibonacci number that is $b$ modulo $a$? We know that the Fibonacci numbers are periodic modulo $a$. Indeed, consider pairs $(F_i,F_{i+1})$ modulo $a$. ...
0
votes
1answer
64 views

Is there a formula to calculate factors of the smallest integer u, for which n, divides a Fibonacci number?

I have read that a conjecture for Fibonacci entry points, by Paul Bruckman and Peter Anderson has been proven for prime p, that uses the Galois theory and the Chebotarev density theorem to compute the ...
1
vote
2answers
148 views

Inductive proof of the identity $\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$ [duplicate]

I'm trying to prove the following identity: $$\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$$ I need to prove it using induction (not a counting argument), I ...
3
votes
4answers
308 views

Fibonacci sequence divisible by 3?

I have a recursion question for my combinatorial class. I'm looking at the Fibonacci sequence $f(n)=f(n-1)+f(n-2)$ for $n \geq 3$ with $f(1)=f(2)=1$. I'm trying to prove that $f(n)$ is divisible by 3 ...
1
vote
2answers
81 views

Source and/or combinatorial interpretation for $F_{n+k} = \sum_{i=0}^{k} \binom{k}{i}F_{n-i}$

Through some fussing with Taylor's Theorem in the discrete calculus described here (among other places), I found what I believe to be an identity: $$F_{n+k} = \sum_{i=0}^{k} \binom{k}{i}F_{n-i}$$ ...
7
votes
1answer
85 views

Is there a non-constant function $f$ such that $f'(x) = f(x - 1)$?

In discrete calculus, where the difference operator $\Delta f = f(x + 1) - f(x)$ takes the place of $\frac{d}{dx}$, Fibonacci sequences are given by the functions satisfying: $$ \Delta f(x) = f(x - 1)...
0
votes
1answer
56 views

Sum of $i$ times $(i-1)^\text{th}$ Fibonacci Number [closed]

Consider the expression $$\sum\limits_{i=1}^n i \cdot F_{i-1}$$, where $F_{0}=0, F_{1}=1, F_{2}=1, F{3}=2,$ etc. Is there a closed formula for this? If so, find it.
0
votes
0answers
41 views

Finding the n-th Pisano Period (for small n)

From Wikipedia: [...] the $n$th Pisano period, written $\pi(n)$, is the period with which the sequence of Fibonacci numbers taken modulo $n$ repeats. For example, the Fibonacci numbers modulo 3 ...
7
votes
3answers
160 views

Prove that $2^{n-1}$ divides $\binom{n}{1} + \binom{n}{3}5 + \binom{n}{5}25 + \binom{n}{7}125 + \cdots$ for $n \geqslant 1$.

Prove that $2^{n-1}$ divides $\binom{n}{1} + \binom{n}{3}5 + \binom{n}{5}25 + \binom{n}{7}125 + \cdots$ for $n \geqslant 1$. Assume $\binom{n}{k} = 0$ if $k>n$. Does anyone know an elementary ...
0
votes
2answers
34 views

Proving an identity of Fibonacci Numbers by induction

Say we know this as a given: $$E_0 = A$$ $$E_1 = B$$ $$E_2 = A + B$$ $$E_3 = A + 2B$$ $$E_4 = 2A + 3B$$ $$E_5 = 3A + 5B$$ $E_{n+1}$ is defined as: $$E_{n+1} = E_n + E_{n-1}$$ You can start to see ...
0
votes
1answer
49 views

Prove that for all $n \in Z^+$, Euclid’s algorithm applied to the pair $(f_{n+1}, f_{n+2})$, takes $n$ steps.

Prove that for all $n \in Z^+$, Euclid’s algorithm applied to the pair $(f_{n+1}, f_{n+2})$, takes $n$ steps. (Here, as previously, $f_n$ denotes the nth Fibonacci number.) I don't understand how to ...
0
votes
1answer
72 views

Prove that if Euclid's algorithm applied to the pair $(u,v)$ takes $n$ steps, then $u \geq f_{n+2}$ and $v \geq f_{n+1}$

Let $u, v \in Z^+$ satisfy $u > v$. Prove that if Euclid's algorithm applied to the pair $(u,v)$ takes $n$ steps, then $u \geq f_{n+2}$ and $v \geq f_{n+1}$. Where the $f_n$ values refer to the ...
1
vote
0answers
34 views

Periods of Fibonacci numbers in mod. Number Theory

Work out the periods $π(n)$ of the $\mod n$ such that $$f_k ≡ f_{k+π(n)} \mod n$$ I got $π(2)=3$,$π(3)=8$,$π(4)=6$ by computing it and looking at the periods. Now Part 2 Prove that for all ...
2
votes
2answers
51 views

Using induction to prove a formula for the Fibonacci sequence involving the solutions of $x^2=x+1$

Let $\{f(n)\}_{n=1}^{\infty}$ denote the Fibonacci sequence defined by $f(1)=1, f(2)=1$, and $f(n)=f(n-1)+ f(n-2)$ for all $n\geq 3$. Let $α=\dfrac{1+\sqrt{5}}{2}$ and $β=\dfrac{1-\sqrt{5}}{2}.$ ...
0
votes
1answer
72 views

Mathematical induction proof of $\sum_{i = 1}^{n} F_{2i} = F_{2n + 1} - 1$

Use Mathematical Induction to show that $$\sum\limits_{i=1}^n F_{2i}=F_{2n+1}-1$$ for all integer $n\geq1$. My answer: Base case: for n = 1 $$\sum_{i = 1}^{n} F_{2i} = \sum_{i = 1}^{1} F_{2i} = ...
0
votes
1answer
42 views

Proving Fibonacci sequence with mathematical induction

Okay, so I have the following thing: $$\sum_{i=1}^a F_{2i}=F_{2a+1}-1 $$ It's to do with Fibonacci sequence. I can do the basis step of MI fine (proving for $a = 1$) However the inductive step has ...
0
votes
3answers
85 views

Proof on Fibonacci sequence: $F(1) + F(3) + \cdots + F(2n-1) = F(2n)$ using induction and recursion

The problem is: Use induction and the recursive formula to prove that: $$F(1) + F(3) + \cdots + F(2n-1) = F(2n)$$ For the base case I let $n=1$ which gave $$F(1) = F(2(1))$$ $$1=1$$ Which is ...
0
votes
0answers
61 views

Does the p-adic valuation of n, apply to Fibonacci numbers and Fibonacci-Wieferich primes?

Does the p-adic valuation of n, apply to Fibonacci-Wieferich primes in the following way? Let Fup be the smallest Fibonacci number divisible by a prime p > 5, then Vp(Fupk) = Vp(Fup) + Vp(k). The ...
3
votes
3answers
207 views

Combinatorics — Fibonacci: formula for $F_1+F_3+ \cdots +F_{2n+1} $

For the following expression, find a simple formula which only involves one Fibonacci number. Then prove it by induction. $$F_1+F_3+ \cdots +F_{2n+1} $$ I'm be appreciated for any help. I have no ...
1
vote
5answers
63 views

Proof about specific sum of Fibonacci numbers

Let $F_k$ denote the $k$-th Fibonacci number. Find a formula for and prove by induction that your formula is correct for all $n > 0$. $$ (-1)^0 F_0+(-1)^1 F_1+(-1)^2 F_2+\cdots+(-1)^n F_n=\ ? $$ I ...
2
votes
1answer
88 views

How to find pythagoras triplet using the fibonacci sequence?

I'm using the Fibonacci sequence to generate some Pythagorean triples $(3, 4, 5,$ etc$)$ based off this page:Formulas for generating Pythagorean triples starting at "Generalized Fibonacci Sequence". ...
0
votes
1answer
33 views

Fibonacci Sequence Squared

I have been learning about the Fibonacci Numbers and I have been given the task to research on it. I have been assigned to decribe the relationship between the photo (attached below). I know that the ...
0
votes
1answer
1k views

Base case in the Binet formula (Proof by strong induction)

I don't understand why the author says that the inductive formula does not apply until $u_3$. The formula does not depend on other terms in the Fibonacci sequence, so I thought I could just prove it ...
0
votes
1answer
76 views

Consider a recursive sequence. Find all values of x for which this sequence is bounded

Consider a recursive sequence $a_{n+1} = a_n + a_{n-1}$ for all $n \geq 2$ with $a_{1} = 1$ and $a_2 = x$. Find all values of $x$ for which this sequence is bounded.
4
votes
2answers
58 views

Calculating number of tile sequences

My daughter (aged 12) came to me with the problem below. I was able to help her to some extent but I could not see an age-appropriate solution. That is, I could imagine solutions involving factorials /...
1
vote
1answer
53 views

Are Fibonacci numbers with a square prime index always divisible by $F_p$?

I am doing some research on sequences and I need some help. The sequence of $F_{p^2}$ seems sort of different. It seems that because the index only has one distinct prime factor, as a result the only ...
1
vote
1answer
59 views

Showing $P_n = {F_n \over {2^n}}$

Let $P_n$ be the probability that, if you flip a fair coin $n$ times, there are no consecutive heads. Also, let $F_n$ be the $n^{th}$ Fibonacci number, normalized by $F_1 = 1$ and $F_2 = 2$ and $F_n = ...