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

Proving that a Fibonacci number is divisible by integer a

I am working on a review problem and can't figure out how to go about getting to an answer. We are told to let $F_n$ be the $nth$ Fibonacci number (defined as $F_1=F_2=1,F_{n+1}=F_n+F_{n-1}$). Show ...
1
vote
0answers
63 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 ...
3
votes
1answer
62 views

Limit of A Fibonacci

Let $P(x)$ be an $n^{th}$ degree-polynomial which is defined below for some odd natural number $n$. And let us denote the set of roots of $P$ by $\{r_1,r_2,r_3,\dots, r_n \}$. $$\displaystyle P(x) = ...
1
vote
2answers
29 views

if d divides n then prove that fibonacci of d divides fibonacci of n

prove that if $d$ divides $n$ then prove that fibonacci of $d$ divides fibonacci of $n$. i have tried to write $F(n)$ as a multiple of $F(d)$ using the fact that $n = ad$ for some natural $a$ but got ...
7
votes
0answers
185 views

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

This is a curiosity question 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 ...
2
votes
1answer
68 views

Covering a rectangle of size $n\times1$ with dominos

A rectangle of size $n\times1$ is given. (a) In how many ways the rectangle can be covered with dominoes of size $1\times1$ and $2\times1$? (b) In how many ways the rectangle can be covered with ...
5
votes
0answers
76 views

Show that for a given $s$ there are a finite number of Fibonacci number of form $n^2+s$

It is well known that the last Fibonacci number $F_k$ such that $\exists \ n \in \Bbb{N} : F_k = n^2$ is $144$. Thus there are only $4$ perfect squares among the Fibonacci sequence (assuming you ...
6
votes
2answers
861 views

Is there among first $100000001$ Fibonacci numbers one that ends with $0000$?

This is a difficult problem from competition training: Is there among first $100000001$ Fibonacci numbers one that ends with $0000$? Trainer suggests using pigeonhole principle.
2
votes
2answers
71 views

Proving a Problem involving Fibonacci numbers

I'm working on proving the problem that states $\text {The sequence}$ {$F_n$} $\text {is defined by the} \ F_1=F_2=1, F_{n+2}=F_{n+1}+F_n \ \text {for} \ n \ge 1.$ $\text {For any natural number m, ...
1
vote
4answers
76 views

Why the $GCD$ of any two consecutive fibonnaci numbers is $1$?

Note: I've noticed that this answer was given in another question, but I merely want to know if the way I'm using could also give me a proof. I did the following: $$F_n=F_{n-1}+F_{n-2} \\ ...
5
votes
4answers
3k views

How to prove gcd of consecutive Fibonacci numbers is 1? [duplicate]

Possible Duplicate: Prove that two any consecutive terms of Fibonacci sequence are relatively prime How to prove it ? Can you help me ? Let $f_n$ be Fibonacci Sequence. ...
1
vote
1answer
93 views

How do I prove $F_{n+1}^2 - F_nF_{n+2} = (-1)^n$ using induction? [duplicate]

$F_n$ refers to the $n$ term of the Fibonacci Sequence. I think I'm supposed to prove this by induction. I already have the base case. I am at: $\text{F}_\text{k+1}^2 - F_k\text{F}_\text{k+2} + ...
4
votes
1answer
351 views

What is the next “Tribonacci-like” pseudoprime?

Given the three roots of $x^3=x^2+x+1$. Then we get the tribonacci-like sequence, $B_n = x_1^n+x_2^n+x_3^n = 3, 1, 3, 7, 11, 21, 39, 71, 131,\dots$ where $B_n = B_{n-1}+B_{n-2}+B_{n-3}$, and the ...
2
votes
1answer
598 views

Proof about lucas numbers.

Define the Lucas numbers to be $$l_n = l_{n-1} + l_{n-2} $$ if $n \ge 2$ with initial conditions $l_0 = 2$ and $l_1= 1$. I "proved" by induction that $l_n = f_{n-1} + f_{n+1}$ for $n \ge 1$ (by ...
1
vote
1answer
51 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$, where $ a_n $ is the Fibonnaci series. This sequence is known as the sequence of Lucas numbers. ...
3
votes
0answers
412 views

Fibonacci and Lucas numbers related identities

We know that $H_n$ = $L_n + mF_n$, where $n = 0$ or $n > 0$ is simply relation between Fibonacci sequence and generalized Fibonacci-Lucas sequence. Are there any methods to prove the following ...
1
vote
0answers
102 views

Closed formula for Lucas numbers [duplicate]

Possible Duplicate: Prove this formula for the Fibonacci Sequence How does one find a formula for the recurrence relation $a_{1}=1,a_{2}=3, a_{n+2}=a_{n+1}+a_{n}?$ How do I go about ...
1
vote
2answers
58 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
61 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 ...
1
vote
1answer
100 views

Prove relation between Lucas and Fibonacci numbers using tilings

I struggle a lot with combinatorial proofs and was hoping for some help. I need to prove by strong induction that $L_n = F_{n-2} + F_n$ and how this shows that $L_n$ counts the tilings of the circular ...
2
votes
2answers
155 views

Show that Fibonacci and Lucas numbers satisfy the following equality for all n ≥ 2.

Fibonacci numbers F1, F2, F3, . . . are defined by the rule: F1 = F2 = 1 and Fk = Fk−2 + Fk−1 for k > 2. Lucas numbers L1, L2, L3, . . . are defined in a similar way by the rule: L1 = 1, L2 = 3 and ...
6
votes
1answer
146 views

Product of consecutive Fibonacci numbers divisibility

Prove that the product of any $k$ consecutive Fibonacci numbers is divisible by the product of the first $k$ Fibonacci numbers. We can try to show that for every prime $p$, the power of $p$ appearing ...
7
votes
3answers
230 views

Is there a proof for this Fibonacci relationship?

I was looking at the decomposition of Fibonacci numbers using the definition of $F_n = F_{n-1} + F_{n-2}$, and noted the pattern in the coefficients of the terms were Fibonacci numbers. It appears to ...
8
votes
2answers
318 views

If $ab-1$, $bc-1$, $ca-1$, $ab-a-b+c$, $bc-b-c+a$, $ca-c-a+b$ are perfect squares, then are $ab+a+b-c$, $bc+b+c-a$, $ca+c+a-b$ also perfect squares?

About a month ago, a friend of mine taught me that there exist many sets of three positive integers $(a,b,c)$ where $a\not=b,b\not=c$ and $c\not=a$ such that each of $$ab-1,\ bc-1,\ ca-1,\ ab-a-b+c,\ ...
9
votes
2answers
203 views

A number $N$ is a $k$-nacci number if and only if …

For $k\ge 2\in\mathbb N$, one can define the $n$-th $k$-nacci number $f_k(n)\ (n=0,1,\cdots)$ as $$f_k(0)=f_k(1)=\cdots=f_{k}(k-2)=0,\ \ ...
4
votes
2answers
53 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
157 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
35 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 ...
2
votes
2answers
135 views

Applying Fibonacci Fast Doubling Identities

So I sort of understand of how these identities came about from reading this article. $F_{2n+1} = F_{n}^2 + F_{n+1}^2$ $F_{2n} = 2F_{n+1}F{n}-F_{n}^2 $ But I don't understand how to apply them. ...
0
votes
1answer
55 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$ ...
3
votes
3answers
188 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 ...
6
votes
2answers
812 views

Fibonacci and Lucas identity

By the trial and error method I have observed the following identity by taking some numerical values. Those are $F_m$|$L_n$ is valid only if one of the following holds. a) $m = 1$ or $m =2$ b) $m ...
1
vote
1answer
406 views

Proof by induction involving fibonacci numbers

The Fibonacci numbers are defined as follows: $f_0=0$, $f_1=1$, and $f_n=f_{n−1}+f_{n−2}$ for $n≥2$. Prove each of the following three claims: (i) For each $n≥0$, $f_{3n}$ is even. (ii) For each ...
0
votes
1answer
36 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?
1
vote
2answers
139 views

Prove that Binet's formula gives an integer, using the binomial theorem

I am given $$ F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}} $$ where, $\varphi = \frac{1 + \sqrt{5}}{2}$ and $\psi = \frac{1 - \sqrt{5}}{2}$. The textbook states that it's equal to the $n$-th Fibonacci ...
2
votes
2answers
61 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
52 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 ...
12
votes
2answers
346 views

Interpolated Fibonacci numbers - real or complex?

The common Binet-formula for the Fibonacci-numbers $$ f_n = {\varphi^n- (1-\varphi)^n \over \sqrt 5 } \small {\qquad \qquad \text{ where }\varphi={1+\sqrt 5\over 2}}$$ allows interpolation to ...
4
votes
0answers
99 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 ...
0
votes
0answers
52 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.
3
votes
2answers
67 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 ...
2
votes
1answer
115 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 ...
6
votes
1answer
126 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
56 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 ...
3
votes
2answers
465 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
65 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...$$ ...