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

1
vote
2answers
38 views

Finding the limit of the following series, wherever it is convergent

Let $ f(x) = \sum_{n=1}^{\infty}a_nx^n $ where $a_n$ is the nth Fibonacci number. Find the values for which the series is convergent, and find $f(x)$ for those values. (i.e - find the limit when ...
5
votes
1answer
65 views

Limit of a specific sequence involving Fibonacci numbers.

Let, $\left\{F_n\right\}_{n=1}^\infty$ be the Fibonacci sequence, i.e, $F_1=1, F_2=1~\&~ F_{n+2}=F_{n+1}+F_n~\forall ~n \in \mathbb{Z}_+$ Let, $P_1=0, P_2=1$. Divide the line segment ...
1
vote
2answers
47 views

Proof concerning Fibonacci and recursively defined sequences

The series $(a_n)_{n\in\mathbb{N}}$ is given through $$a_1=1,\quad a_2=\frac{1}{2},\quad a_{n+2}=a_na_{n+1} \quad\text{ for } n\geq1.$$ I want to show that $$a_n = 2^{-f_{n-1}}$$ whereas ...
1
vote
2answers
70 views

Seeking a combinatorial proof $F_{mn}$ always a multiple of $F_m$

I would appreciate if somebody could help me with the following problem Q: Let $F_n$ the sequence of Fibonacci numbers, given by $F_1 = 1, F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$ ...
6
votes
1answer
86 views

Integral representation for Fibonacci's numbers

We know that, for example, the Gamma function is a perfect integral representation for the factorial $n!$ for a natural number $n$. $$\Gamma[n] = \int_0^{+\infty} t^{n-1}e^{-t}\text{d}t = (n-1)!$$ ...
1
vote
0answers
134 views

Is there a proven way to calculate the entry point(first occurence) of a factor m, in the Fibonacci sequence?

I saw a comment at the OEIS website for the sequence of entry points, of Fibonacci factors. https://oeis.org/A001177 It referenced a paper by Mark Renault in 1996, with the quote from OEIS: ...
3
votes
2answers
53 views

Do I need induction here?

I am asked to prove, by using induction that $$\sum\limits_{i=1}^n F(2i-1) = F(2n)$$ for all real numbers n where the function F(i) gives the i:th fibonacci number. The series stars off with $F(0) ...
1
vote
4answers
133 views
3
votes
1answer
58 views

Convergence of Series Whose Terms are Defined Recursively

My recursively defined sequence $(a_n)_{n\in\mathbb{N}}$ is given trough $$a_1 = 1, \quad a_2=\frac{1}{2}\quad a_{n+2}=a_{n}a_{n+1}\quad \text{for } n\geq1$$ and I have to show that the series ...
0
votes
2answers
23 views

Closed form expression for zero of recurrence relation

Given the recurrence $d(i+1)=xFib(2i+1)-nFib(2i)$, where $Fib$ denotes the Fibonacci sequence (i.e. $Fib(0)=0, Fib(1)=1, Fib(2)=1, Fib(3)=2$, etc) and $n$ and $x$ are arbitrary integers, is it ...
0
votes
2answers
46 views

How to prove this sequence is null?

I am working on the fibonacci numbers series using the ratio. To prove convergence I want to show that the sequence of the series is going to 0. And then according to the Leibniz criterion the series ...
3
votes
0answers
37 views

Fibonacci numbers and binomial theroem [duplicate]

So I am trying to prove $$\sum_{i=0}^n{nCi×F_i} = F_{2n}$$ Such that $$nCi = \frac {n!}{i!×(n-i)!}$$ And $F_i$ is the ith value of the fibonacci sequence such that $F_0 = 1$ and $F_1 = 1$ I have ...
1
vote
1answer
57 views

Proof: Fibonacci Sequence (2 parts)

Part a) Prove or Disprove: There are only finitely many even Fibonacci numbers. I think I want to disprove this, as I know that every 3rd Fibonacci number is even, and thus there will be infinitely ...
0
votes
0answers
29 views

Divisibility of Fibonacci Sequence mod prime

I have to solve the following problem and I have a few questions: Consider the Fibonacci sequence defined as $F_n:=2F_{n-1}+F_{n-2}$ with $F_0=1$ and $F_1=1$. Now, I need to prove that for any odd ...
3
votes
3answers
107 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} ...
4
votes
1answer
339 views

Given Two Fibonacci numbers, predicting the median Fibonacci number

Wolfram Alpha gives the $100$th fibonacci number to be $354224848179261915075$ and the $104$th fibonacci number to be $2427893228399975082453$. Just from this, can we deduce what the $102$th fibonacci ...
1
vote
1answer
54 views

How many times can $p$ divide $F_n$?

Given a prime $p$ and a number $n$ (or perhaps just an upper bound $x$ with some unknown $n\le x$), trivially one has $$ \operatorname{ord}_p F_n\le\frac{\log F_n}{\log ...
2
votes
2answers
36 views

Sum of Squares for Odd Fibonacci Numbers

I am trying to prove the following theorem by induction: THEOREM: For the Fibonacci sequence $F_1$, $F_2$, ... , $F_n$ defined as, $F_1$ = $F_2$ = 1 $F_n$ = $F_{n-1}$ + $F_{n-2}$ for n >= 3, For ...
3
votes
1answer
99 views

Proving that every integer has a Fibonacci number multiple

Show that for any positive integer, there exists a Fibonacci number N such that N is divisible by the integer. I'm not really sure how to begin my approach to this problem, would really appreciate ...
1
vote
1answer
27 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
0answers
33 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
41 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 ...
2
votes
2answers
65 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
1answer
51 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?
1
vote
0answers
42 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
79 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 ...
1
vote
1answer
30 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 ...
0
votes
2answers
57 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) ...
3
votes
2answers
225 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 = ...
0
votes
2answers
50 views

Convergence of Binet's formula expression for Fibonacci

Let $\displaystyle \phi = \frac{1+\sqrt{5}}{2}$ and $\displaystyle \psi = \frac{1-\sqrt{5}}{2}$. Consider the Fibonacci sequence defined by: $$ \displaystyle a_n = \frac{\phi^n - \psi^n}{\sqrt{5}} $$ ...
3
votes
4answers
271 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
68 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
84 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 - ...
0
votes
1answer
55 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
35 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 ...
0
votes
2answers
33 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
70 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 ...
0
votes
1answer
48 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 ...
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 ...
7
votes
3answers
159 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 ...
2
votes
2answers
50 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
38 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
1answer
69 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
3answers
83 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 ...
2
votes
1answer
84 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
31 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
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.
0
votes
1answer
62 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 ...
0
votes
0answers
59 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 ...