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

Why do I get the Fibonacci sequence when I start with 1 and keep using the + sign?

I played with this on a calculator and when I entered 1 and kept hitting the + button, I got the noticeable Fibonacci sequence! Can someone explain to me why this happens?
2
votes
2answers
39 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 ...
2
votes
4answers
45 views

Finding growth bounds on Fibonacci Sequence

I've been working on this following problem: Find a constant $c< 1$ such that $F_n \leq 2^{cn}$ for all $n \geq 0$. I honestly have no idea where to begin on this. I've done plenty of proofs ...
0
votes
0answers
47 views

How to prove a claim about Fibonacci sequence

I have to prove that for any natural number $n$ there exists $i>0$ such that $n\mid F_i$, where $F_i$ is the $i$-th Fibonacci number.
0
votes
1answer
35 views

Generalized Fibonacci Sequence with Modular Arithmetic

Consider the following generalized Fibonacci sequence: Given $a$ and $b$ positive integers, and the known values $g_1, g_2, ...g_b$ where $g_k = g_k$ (mod $a$), then for ...
0
votes
0answers
28 views

Generalized Fibonacci Sequences G_{n+p}

I have been given the following generalized fibonacci sequences: For some positive integer $m,p$, $g_{n+p}=g_{n+p-1}+g_{n+p-2}+...+g_{n+1}+g_n (mod m)$ I have been given two problems: (1) For $m=2$ ...
3
votes
2answers
54 views

Is fibonacci sequence a member of more broad family of sequences?

Yesterday, I was pondering on the Fibonacci sequence and I started to discover some features of it that were previously unknown to me. Such as, 1, 1, 2, 3, 5, 8, 13, 21, 34 .... 1 ) The nth element ...
6
votes
1answer
100 views

The totient of Fibonacci numbers is divisible by $4$

Let $\{f_i\}_{i\in\mathbb N}$ be the sequence of Fibonacci numbers, i.e. $1,2,3,5,8,13,21,34,55,\cdots$, For every integer $n\gt3$ prove that $$4\mid\phi(f_n)$$ where $\phi$ is Euler's totient ...
2
votes
1answer
42 views

Showing that this sum is equal to the fibonacci numbers

How do I show that the following sum is equal to the fibonacci numbers? Atleast numerical evaluation suggests it is $$ \sum_{k=0}^{\lceil n/2\rceil}\binom{n+1-k}{n+1-2k} $$ The image below shows how ...
0
votes
1answer
33 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
109 views

How do I choose first terms of a Fibonacci sequence?

Let $f(0)=a$ and $f(1)=b$ be the first two terms of a Fibonacci sequence. We know that this sequence is periodic in $\mod{p}$, where $p$ is a prime number, and the period of the sequence is $p-1$. I ...
0
votes
0answers
28 views

A binary plot of the Catalan numbers and the pseudo-Fibonacci series that can be found inside. Why do they appear?

I was trying to find in Internet a binary plot of the Catalan numbers, and I did not find anyone... so I did it by myself and here it is (about 2000 elements): There are not clear patterns inside ...
1
vote
0answers
54 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
63 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
0answers
39 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 ...
2
votes
1answer
62 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
3answers
61 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
48 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. ...
1
vote
1answer
37 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.
0
votes
1answer
34 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!
2
votes
1answer
38 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
19 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 ...
2
votes
0answers
84 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
0answers
23 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
2answers
42 views

Given that fib(n)=fib(n-1)+fib(n-2) for n>1 and given that fib(0)=a, fib(1)=b (some a, b >0)

Given that fib(n)=fib(n-1)+fib(n-2) for n>1 and given that fib(0)=a, fib(1)=b (some a, b >0) which of the following is true? fib(n) is : Select one or more: a. O(n) b. O(n^2) c. O(2^n) d. ...
0
votes
0answers
43 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 ...
0
votes
0answers
31 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
20 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 ...
0
votes
4answers
377 views

Why do Fibonacci numbers appear in stock market tick charts? [closed]

I've been reading about stocks trading and noticed Fibonacci numbers are preferred as the time frames for tick charts. I was immediately very curious about why that happens. Does anyone know? Thanks! ...
0
votes
2answers
39 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
45 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
54 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)$ ...
2
votes
4answers
88 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
33 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
80 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 ...
4
votes
0answers
81 views

Are there infinite Fibonacci primes if and only if there are infinite Fibonacci numbers that are Fibonacci pseudoprimes?

One of the open questions about the Fibonacci numbers is if there are infinite prime numbers inside the Fibonacci sequence. I wonder if a good approach would be trying to know first if there are ...
2
votes
2answers
32 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
147 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
1answer
49 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
20 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
65 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 ...
0
votes
1answer
32 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
43 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 ...
4
votes
0answers
139 views

when $F_n^2+F_m^2$ is a square for fibonacci numbers

I'm trying to solve a Diophantine equation and I need some results about fibonnacci numbers, I encountered this problem: For which couple of integers $(n,m)$ the number $F_n^2+F_m^2$ is a square ...
3
votes
3answers
206 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
66 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 ...
0
votes
2answers
87 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. ...
1
vote
2answers
48 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 ...
5
votes
2answers
91 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, ...
0
votes
1answer
34 views

Lucas Number Sequence

Can anyone help me in this question: Define $ (b_n)$ as $b_1= 1,b_n=a_{n+1} - a_n $ for $ n\ge 2 $is known as the sequence of lucas numbers. where $ a_n $ is the fibonnaci series. Prove: ...