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
0answers
34 views

What are the next few “tetranacci-like” pseudoprimes?

Starting with $n=0$: $k=2$ Given the roots $x_i$ of $x^2-x-1=0$. Then, we have the Lucas numbers, $$A_n = x_1^n+x_2^n = 2, 1, 3, 4, 7, 11, 18,\dots$$ The $n$ that divides $A_n-1$ are all the ...
1
vote
2answers
41 views

Prove that the sum of the first $n$ even terms of the Fibonacci sequence is given by $(F_{3n} + F_{3n + 3} - 2) / 4$ not using induction?

each even term in the Fibonacci sequence has a position index which is a multiple of 3, therefore the even term is $F_{3n}$: $F_{3 (0)} = 0$ $F_{3 (1)} = 2$ $F_{3 (2)} = 8$ $F_{3 (3)} = 34$ $F_{3 ...
1
vote
1answer
57 views

Show that exist $i>0$ such that the Fibonacci number $F_{i}$ is divisible by 2015

This is a problem that has haunted me for more than a month. Not all the time - but from time to time, and always on windy or rainy days, it suddenly reappears in my mind: Assume that the sequence ...
4
votes
2answers
46 views

Proving that $F_{kn}$ is a multiple of $F_n$ by induction on $n$ (Fibonacci numbers)

Question: I want to prove that $F_{kn}$ is a multiple of $F_n$. Approach: I have to deduce this result from the following results: $$F_{n+k} = F_{k}F_{n+1} + F_{k-1}F_{n}$$ I have shown the ...
0
votes
2answers
43 views

Sum of odd Fibonacci Numbers

Trying to prove that the sum of odd-index consecutive Fibonacci numbers is the next even-index Fibonacci number. I have a gap in my proof that I cannot figure out. I know that induction would be ...
0
votes
1answer
27 views

Prove or disprove this relation between one root of the quadratic and the cubic equation of a certain form, and linear recurrences.

It is well known that the n-anacci (higher degree Fibonacci, that is Tribonacci and so on) numbers can be computed in closed form from roots of polynomials in the way Eric Weisstein at Mathworld ...
0
votes
1answer
40 views

Discrete Mathematics Fibonacci Sequence

I am studying for the final exam in my Discrete Mathematics class and came upon the following problem on the study guide we were given. Given the following algorithm: If $n = 0$, then $f(n) = 0$ ...
0
votes
1answer
34 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
42 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
49 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
38 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
31 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
104 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
47 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
34 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
110 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
34 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
57 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
65 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
40 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
65 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
65 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
50 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
39 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
35 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
21 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
86 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
25 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
44 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
45 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
32 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
2answers
40 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
55 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
95 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
35 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
85 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
82 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
33 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
155 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
51 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
71 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
33 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
143 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 ...