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

3
votes
2answers
466 views

Fibonacci / Lucas Numbers Relationship: $F_{2n} = F_n L_n$

Prove the identity by induction: $$ F_{2n} = F_n L_n, $$ where $F_n$ and $L_n$ are the $n^{th}$ Fibonacci and Lucas number, respectively. I have an answer but am not happy with it since it doesn't ...
0
votes
1answer
48 views

Generalized Fibonacci Sequences with Modular Arithmetic

Consider the following generalized fibonacci sequence: For $m,p$ positive integers and $g_k =g_k (mod m)$, then for $n=1,2,3,...$ $g_{n+p}=g_{n+(p-1)}+g_{n+(p-2)}+...+g_{n+1}+g_n (modm)$ I need to ...
2
votes
1answer
85 views

Prove by induction that numbers of Fibonacci of the form $F_{3n}$ are even

I am not quite asking to solve this problem, but I am asking what they are asking me. This is the problem: The Fibonacci numbers $F_n$ for $n \in \mathbb{N}$ are defined by $F_0 = 0$, $F_1 = 1$, ...
0
votes
0answers
42 views

Problem about fibonacci sequence via quadratic roots in gelfand's algebra text.Need hints.

I have solved a preceding question proving that the common ratio of such a sequence is $ \frac {1+\sqrt{5}}{2} $ or $ \frac {1-\sqrt{5}}{2} $ (resolving a quadratic equation) . The present problem is ...
1
vote
0answers
66 views

Sum of Power of Two Fibonacci reciprocals

Evaluate $$\sum_{k=0}^{\infty} \frac{1}{F_{2^n}} \;.$$ I'm thinking of using a relation from a term to another.
2
votes
2answers
85 views

Sum of Fibonacci numbers

While trying to find find a formula to calculate the length of the golden spiral I came across the sum of the Fibonacci numbers. I noticed that $$\text{Fibonacci numbers: }1,1,2,3,5,8,13,21,34...$$ ...
0
votes
3answers
67 views

Fibonacci induction proof?

The Fibonacci Numbers $(f_n)$ are defined $f_1=f_2=1$, and $f_n=f_{n-1}+f_{n-2} ,\,\,\,\forall n \geq2$. Prove that for every integer $n \geq 1$, $$f_1 +f_2 +···+f_n =f_{n+2}−1$$
1
vote
2answers
51 views

Prove the following recurrence: $F_{2n+1}=3F_{2n-1}-F_{2n-3}$

Prove the following identity: $$F_{2n+1}=3F_{2n-1}-F_{2n-3}$$ So far I know that $F_n=F_{n-1}-F_{n-2}\implies F_{2n+1}=F_{2n}+F_{2n-1}$ Just not sure where to go from here to get to the conclusion. ...
0
votes
0answers
55 views

Identify fibonacci sequences from a set of data

Let there be a set of increasing order integer data ${a_1, a_2, a_3, a_4, ...}$. given the increasing infinite sequence of integers, how can we determine whether there is an infinite subsequence which ...
3
votes
4answers
1k views

Fibonacci Sequence, Golden Ratio

I've been asked to show that $x_n \rightarrow L$ as $n \rightarrow \infty$ where $x_n = F_{n+1}/F_{n}$ for $n \in \mathbb{Z}^+$, where $F_n$ denotes the $n^{th}$ Fibonacci number. I am supposed to use ...
1
vote
1answer
47 views

Hadamard's product of Fibonacci generating functions.

$F(s) = \frac{1}{1-s-s^2}=\sum_{n\geq0}F_ns^n$. I want to calculate $F(s) \circ F(s) = \sum_{n\geq0}F_{n}^2s^n$. I have tried using Binet"s formula, but problem remains unsolved.
2
votes
0answers
90 views

Proving $ F_{m}F_{n}=\dfrac{1}{5}(L_{m+n}-(-1)^{n}L_{m-n}) $ for Fibonacci numbers

How can I prove the following identity about the Fibonacci numbers by using matrices or determinants? $ F_{m}F_{n}=\dfrac{1}{5}(L_{m+n}-(-1)^{n}L_{m-n}) $
0
votes
1answer
43 views

Fibonacci Number Formula for nth term [duplicate]

Hey is there any known combinatorial formula for nth fibonacci number? (n+1)th fibonacci number is given by summation of r=0 to (round)n/2:C(n-r,r) Can someone verify the formula?Help!
6
votes
1answer
863 views

Finding the binary representation of the $n$th Fibonacci term

Objective: To find the binary representation ( or no. of 1's in binary representation) of nth term in Fibonacci sequence where n is of the order 10^6. My current approach: Find nth term (in decimal) ...
2
votes
1answer
41 views

Help with how to prepare the inductive step of a strong induction exercise.

I have the following exercise: "Use strong induction to prove that $f_1^2 + f_2^2 + \cdots + f_n^2 = (f_n)(f_{n+1})$ where $f_n$ in the nth Fibonacci number." This is what I have done: Fibonacci ...
0
votes
0answers
28 views

Can't find ANY golden ratio in the schroder house…

The Schroder House (The Netherlands) is supposed to be designed using the "golden ratio". I'm having trouble finding these golden ratio's. A lot of rectangles, windows, house sections, etc. appear to ...
0
votes
0answers
28 views

Prove that for any power function $f_n = c^{n}$, the number of decimal digits of $ f_{10^n}$ is given by $10^{n}log_{10}c$

I am reading this page about some interesting properties of the Fibonacci numbers: http://mathworld.wolfram.com/FibonacciNumber.html The following is said: The numbers of Fibonacci numbers less ...
0
votes
0answers
40 views

Fibonacci polynomial summation

The $n^{th}$ value of a polynomial ($S_n$) of order $k$ is a polynomial in $x$ is given by : $\left(\frac{S_n}{x^n}\right)$= $\sum_{j=0}^n \left(\frac{{F_j}^k}{x^j}\right)$ Where ${F_j}$ is the ...
0
votes
1answer
21 views

Show that $\forall n \in \mathbb{N}: n$ can be written as $F_{n+1}$ different sums of ones and twos

Show that $\forall n \in \mathbb{N}: n$ can be written as $F_{n+1}$ different sums of ones and twos where the order matter. Presumably, mathematical induction can be leveraged here. Step 1: Show ...
9
votes
3answers
2k 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
8answers
580 views

Why is the Fibonacci ratio though a decreasing function, it is alternating and decreasing?

I tried to find the ratio of consecutive terms of the Fibonacci series and found that it is a decreasing function and it converges . I tried it though a small code piece in python so that I can have a ...
2
votes
4answers
102 views

Relationship between Fibonacci's secuence and $x^2 - x - 1$.

On the end of Apostol's Mathematical Analysis' first chapter, one can find the following exercise (and I paraphrase): Prove that the $n$-th term of the Fibonacci sequence is given by $$x_n = ...
0
votes
2answers
48 views

Applying the mean value theorem to the closed form of the Fibonacci sequence?

Is it possible to apply the mean value theorem to the closed form of the Fibonacci sequence for the 7 numbers starting at 1 and ending with 13 (inclusive)? It's been a LONG time since I studied ...
0
votes
1answer
98 views

Hyper sum of Fibonacci numbers

Let $F(n)$ be the $n$-th Fibonacci number. That is, $F(n)$ satisfies $F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2) (if n≥2).$ Let $f_k(n)$ be the function such that $f_0(n) = F(n)$, $f_k(n) = ...
2
votes
1answer
349 views

Cycles in the Generalized Fibonacci Sequence modulo a Prime

Suppose I have a fibonacci sequence 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 Now if I have a modulo 5 fibonacci sequence,it will look like ...
0
votes
1answer
50 views

Deduce a series formula for product of Fibonacci numbers.

Start with the arbitrary pair of Fibonacci numbers $F_{n+1}$, $F_n$ and apply the Euclidean Algorithm to it. Deduce a series formula for the product $F_{n+1}F_n$. I use the formula, $F_{n+1} = F_n + ...
0
votes
1answer
59 views

Proving a function by induction [duplicate]

Let $f(n)$ be the function defined by $$ f(n) = \frac 1{\sqrt{5}} \left[ \left(1+\sqrt{5}\over2\right)^n- \left(1-\sqrt{5}\over2\right)^n \right] $$ How do you prove that $f(n) = f(n+2) - f(n+1)$ ...
0
votes
2answers
184 views

Fibonacci even numbers formula

i found a general formula in any given set of Fibonacci numbers ,to find the next given even number we can use the formula E*4 + Eo where E is the given even number Eo is the even number ...
0
votes
3answers
93 views

Lucas numbers and fibonacci

This is a question straight from the Applied Combinatorics book. Suppose that chairs are arranged in a circle. Let $L_n$ count the number of subsets of $n$ chairs which don't contain consecutive ...
2
votes
4answers
1k views

Strong inductive proof for this inequality using the Fibonacci sequence.

Problem I need to determine for what natural numbers is $2n < F_n$, where $F_n$ is the $n^{th}$ Fibonacci number determined by $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n-1}+F_{n-2}$. I then need to ...
3
votes
2answers
163 views

Fibonacci combinatorial identity

Can someone explain how to prove the following identity involving Fibonacci sequence $F_n$ $F_{2n} = {n \choose 0} F_0 + {n\choose 1} F_1 + ... {n\choose n} F_n$ ?
8
votes
2answers
837 views

Proof by induction on Fibonacci numbers: show that $f_n\mid f_{2n}$

I was studying Mathematical Induction when I came across the following problem: The Fibonacci numbers are the sequence of numbers defined by the linear recurrence equation- $f_n = f_{n-1} + ...
2
votes
2answers
42 views

Prove the sum of the even Fibonacci numbers

Let $f_n$ denote the $nth$ Fibonacci number. Prove that $f_2\:+\:f_4\:+...+f_{2n}=f_{2n+1}-1$ I am having trouble proving this. I thought to use induction as well as Binet's formula where, ...
2
votes
0answers
186 views

LCM of Fibonacci numbers

$\newcommand{\lcm}{\operatorname{lcm}}$There is a nice property of Fibonacci numbers which says that: $$\gcd(F_{a_1}, \ldots, F_{a_n}) = F_{\gcd(a_1, \ldots, a_n)}$$ I am curious is there anything ...
3
votes
2answers
204 views

Prove the $n$th Fibonacci number is the integer closest to $\frac{1}{\sqrt{5}}\left( \frac{1 + \sqrt{5}}{2} \right)^n$

Prove that the $n$th Fibonacci number $f_n$ is the integer that is closest to the number $$\frac{1}{\sqrt{5}}\left( \frac{1 + \sqrt{5}}{2} \right)^n.$$ Hi everyone, I don't really understand the ...
3
votes
1answer
54 views

Showing that $f_n$ is the number closest to $\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n$ [duplicate]

I want to prove that the the $n$th Fibonacci number $f_n$ is the integer closest to $\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n$. What would be a rigorous way to go about this? I assume I'll have to ...
1
vote
0answers
26 views

Hankel determinant involving Fibonacci numbers

Let $F_n$ denote the nth Fibonacci number, with $F_1 = F_2 = 1$. Denote by M(n) the nxn Hankel matrix with $i,j $ entry $F_{i+j-1}^{n-1}$, where i and j range from 1 through n. Finally, let d(n) = ...
5
votes
1answer
107 views

Connection between Euler's totient function and Fibonacci numbers

For a sequence $(a_n)$ of natural numbers define $\alpha(n):=\min\{m\in\mathbb{N}:n|a_m\}$ whenever it exists. Thus $\alpha(n)$ is the first index $m$ such that $n$ divides $a_m$. Now define the ...
2
votes
2answers
56 views

Fibonacci divisibility

Prove that the following holds: $3|F_n$ if and only if $4|n$ Base case for $n=1$: $F_1$=1, so $F_1$ is not divisible by 3 and 1 is not divisble by 4. So the proposition holds for $k=1$ Continue ...
0
votes
1answer
45 views

Convergence of fibonacci quotient $\frac{f_n}{f_{n+1}}$

I know that $\frac{f_{n+1}}{f_{n}}$ converges against $\phi = \frac{1+\sqrt{5}}{2}$. The question i want to to ask you is if the following conclusion is correct, I mean i know that if we have two ...
-1
votes
1answer
46 views

What is the probability that a given a positive number, will be found in the space of shifted fibonacci sequences?

We are given a space of shifted Fibonacci sequences, Fk, Fk+1, Fk+2, Fk+3, Fk+6, Fk+8, Fk+9, Fk+10, Fk+10, Fk+11….. Given a number,n, what is the probability of this number within this space? And ...
3
votes
3answers
218 views

How many times a positive number can be found in shifted Fibonacci Sequences?

Given a positive number, how many times can this number be found in shifted fibonacci sequences? ...For example...Number 11, can be present seven times in total, in Fn+3, Fn+6, Fn+8, Fn+9, Fn+10, ...
3
votes
2answers
75 views

How to find a Fibonacci number that is divisible by $x$?

I'm looking for an algorithm that is better than just checking every number in the Fib Sequence for divisibility. Example: Find the first Fib number that is divisible by $x=223321$, with no ...
1
vote
2answers
56 views

Seeking combinatorial proof for $F_{n+1} -1=\sum\limits_{k=0}^{n-1} F_k$

In order to give a combinatorial proof for this equation, we need to find what these two count for. But I don't know what they count for and how I can pivot the RHS to show that it actually counts ...
0
votes
2answers
112 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. ...
6
votes
2answers
94 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
178 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
219 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 ...