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

2
votes
1answer
34 views

How many Fibonacci Numbers are in the sequence

I have $I_n = \{2^n + 1, 2^n + 2, 2^n + 3, \dots , 2^{n+1}\}$ and I am trying to prove using induction how many Fibonacci numbers are there. First, the length of $I_n$ is $|I_n| = 2^n$ then for $F_0 ...
36
votes
5answers
781 views

Is ${F_{n}}^2 - 28$ always a composite number?

The problem is as follows: Prove or disprove that if ${F_{n}}$ is $n$-th Fibonacci number, and $n>5$, than $${F_{n}}^2 - 28$$ cannot be a prime. I came across this problem accidentally ...
0
votes
1answer
22 views

Proving $F_n \ge (\frac{1}{2}(1+\sqrt{5}))^{n-2}$ for $n \in \mathbb{N}_{>1}$ when $F_n$ is the nth Fibonacci number

Let $F_n$ be defined as the nth Fibonacci number. Prove that $F_n \ge (\frac{1}{2}(1+\sqrt{5}))^{n-2}$ with $n \in \mathbb{N}_{>1}$ My approach thus far was to use induction over $n$. ...
0
votes
3answers
39 views

Prove $F(n) < 2^n$ [on hold]

Consider the Fibonacci function $\large{F(n)}$, which is defined such that $F(1) = 1, F(2) = 1$, and $F(n) = F(n−2)+F(n−1)$ for $n > 2$ I know that I should do it using mathematical induction but ...
1
vote
4answers
176 views

Proof the golden ratio with the limit of Fibonacci sequence [duplicate]

Let $F_n=F_{n-1}+F_{n-2}$ the Fibonacci numbers, and $\phi=\frac{1+\sqrt5}{2}$ The exercise asks me to prove that: $\lim\limits_{n \to \infty}\frac{F_{n+1}}{F_n}=\phi$. Sorry as can be proceed??
13
votes
6answers
201 views

show that $\frac{1}{F_{1}}+\frac{2}{F_{2}}+\cdots+\frac{n}{F_{n}}<13$

Let $F_{n}$ is Fibonacci number,ie.($F_{n}=F_{n-1}+F_{n-2},F_{1}=F_{2}=1$) show that $$\dfrac{1}{F_{1}}+\dfrac{2}{F_{2}}+\cdots+\dfrac{n}{F_{n}}<13$$ if we use Closed-form expression ...
1
vote
1answer
27 views

An equation to prove with terms of Fibonacci sequence

I would like to prove an equation but I have stuck. The equation that is to prove is the below: $f(n)^2 + (-1)^{n+1} = f(n+1)f(n-1) , n \ge 2$. I'm trying to do an inductive proof of this equation. ...
1
vote
0answers
33 views

Fibonacci Sequence (conceptual/mechanical)

I'm in Calc II and have my exam on series/sequences tomorrow. There will be an extra credit question related to Fibonacci and am trying to gather as much info on the sequence as possible. -If the ...
-2
votes
0answers
25 views

Fibonacci Sequence $f_{2n+1} = f^2_n + f^2_{n+1}$ Strong Induction Proof [closed]

With the Fibonacci sequence $f_n$ defined as $f_n = f_{n-1} + f_{n-2}$ for $n\ge2$ with $f_0 = 0$ and $f_1 = 1$, prove the following using strong induction for any $n\in N$: $$ f_{2n+1} = f^2_n + ...
4
votes
0answers
102 views

A Fibonacci like Stochastic process

Let $X_0, X_1$ and $\{a_n,n\geq0\}$ are i.i.d. $\sim $Bernoulli$(1/2)$ taking values in $\{0,2\}$. Let us define $X_n$ for $n>1$ as below$$X_{n+1}=a_nX_n+a_{n-1}X_{n-1},\ n\geq1 $$ Then it follows ...
2
votes
2answers
71 views

Proof by induction of a Fibonacci relation [duplicate]

We know: $F_0 = 0$ $F_1 = 1$ $F_i = F_{i-1} + F_{i-2}$ for $i \geq 2$ Prove by induction: $F_i = \dfrac{\phi^i-{\phi^{*}}^i}{\sqrt{5}}$ where $\phi = (1+\sqrt{5}) / 2$ and $\phi = (1-\sqrt{5}) / ...
4
votes
2answers
58 views

Conjecture: only one even Fibonacci term divided by two gives a prime: $F(9) = 34 = 2 \times 17$

Every Fibonacci term $F(3n)$ is divisible by two $F(3) = 2$ $F(6) = 8$ $F(9) = 34$ $...$ After seeking Fibonacci tables factorization until $F(10000)$, for every term $\frac{F(3n)}{2}$, it ...
2
votes
1answer
58 views

Are there 3D geometric proofs of Fibonacci identities?

There is a significant number of identities involving Fibonacci numbers that can be proven in a sort of geometric way, as it is shown in the following picture: However, I couldn't find any such ...
0
votes
2answers
24 views

How does one arrive at a certain expression for the Fibonacci Zeta function?

In this paper by L. Navas, it is described how one can obtain a analytic continuation of the Fibonacci Dirichlet series (though I'm not sure it's actually a Dirichlet Series). First, the following ...
1
vote
0answers
75 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
53 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
55 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
28 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 ...
6
votes
0answers
160 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
58 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
63 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
850 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.
49
votes
3answers
561 views

Closed form solution for $\sum_{n=1}^\infty\frac{1}{1+\frac{n^2}{1+\frac{1}{\stackrel{\ddots}{1+\frac{1}{1+n^2}}}}}$.

Using a symbolic computation software (Mathematica), I got the following interesting results: $$ \begin{align} \sum_{n=1}^\infty\frac{1}{1+\frac{n^2}{1+\frac{1}{1+\frac{1}{1+n^2}}}} &= ...
2
votes
2answers
66 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
59 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
92 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
344 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
579 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
44 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. ...
2
votes
0answers
336 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
94 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
47 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
59 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
95 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
143 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 ...
5
votes
1answer
121 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
226 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
305 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
183 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
47 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
30 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
120 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
44 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
2answers
155 views

Fibonacci series, which is most pure mathematically? [closed]

This question drew conclusions from comparing three definitions of the fibonarchi series, however I made a mistake in the 2nd that means that it can not be used at all, the question has been adjusted ...
3
votes
3answers
187 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
740 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
383 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
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?