# Tagged Questions

76 views

### Proof by induction: $n$th Fibonacci number is at most $2^n$

I'm trying to find the proof by induction of the following claim: For all $n\in\mathbb N$, $\operatorname{fibonacci}(n) \le 2^n$ My Proof: Base case: $n = 1$ $\operatorname{fibonacci}(1) \le 2^ 1$ ...
121 views

### An analogue of Hensel's lifting for Fibonacci numbers

In this question Oleg567 conjectured the following interesting fact about Fibonacci numbers: $$k\mid F_n\quad\Longrightarrow\quad k^d\mid F_{k^{d-1}n}$$ that can be regarder as an analogue of the ...
68 views

### Fibonacci numbers $F_{n+3} + F_{n} = 2F_{n+2}$

Prove $F_{n+3} + F_{n} = 2F_{n+2}$ for any positive integer n. So What I did was this: fn+ fn+1 = fn+2 fn + fn+1 = fn+2 => fn+2 -fn+1 fn+1 + fn+2 = fn+3 then I subsituted into equation in ...
69 views

### How to establish this inequality without using induction?

Given the Fibonacci sequence $a_1 = 1$, $a_2 = 2$, $\ldots$, $a_{n+1} = a_n + a_{n-1}$ for $n \geq 2$, how to derive, without using induction, the inequality $$a_n < (\frac{1+\sqrt{5}}{2})^n$$ ...
91 views

### How do I apply the $\pm4$ part of the equation $5F_n^2\pm~4=L_n^2$ without knowing $n$?

I'm trying to test a great many numbers $a^3+b^3$ to see if any of them are Fibonacci using the formula $$a^3+b^3=F_n \iff 5(a^3+b^3)^2\pm~4=L_n^2$$ I want to make my search more efficient by having ...
32 views

### finding $n$ consecutive composite Fibonacci numbers.

For each $n$, How can we find $n$ consecutive composite Fibonacci numbers?
126 views

### how to find nth term of different fibonacci series with golden ratio [duplicate]

what i know : if i want to find $Nth$ term of a fibonacci series like : 1 1 2 3 5 8 13 21 ....... then to find $6th$ term we use golden ratio ...
4k views

### Does every prime divide some Fibonacci number?

I am tring to show that $\forall a \in \Bbb P\; \exists n\in\Bbb N : a|F_n$, where $F$ is the fibonacci sequence defined as $\{F_n\}:F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$ $(n=2,3,...)$. How can ...
101 views

### Proving that $fib(n) < (5/3)^n$ for $n \ge 1$ by induction

I know this has been shown before here but no post really answered my question. I had this problem given to me as an induction practice problem and I couldn't solve it without help. When I got the ...
29 views

### Converting Fibonacci number $F_{5n+3}$ to Lucas numbers $L_{n+k}$

I'm trying to prove that$F_{5n+3}\text{mod}10 = L_{n}\text{mod}10$. I rearranged it into a more solvable form of $F_{5n+3}-L_n = 10k$ (because if two numbers end in the same digit, their difference ...
221 views

### Proof that Fibonacci Sequence modulo m is periodic?

It's well known that the Fibonacci sequence modulo m (where m is any integer) is periodic. I have figured out a proof for this, but upon googling, I found proofs online that were far more complicated. ...
87 views

### Find all solution to $a^{2}\equiv -1 \pmod b$ and $b^{2}\equiv -1\pmod a$ (self-answer)

There was a question here just a moment ago but was deleted by the author. It is to find all solution to $a^{2}\equiv -1 \pmod b$ and $b^{2}\equiv -1 \pmod a$ with $a,b>1$. But I already typed up ...
2k views

### how to find nth term in a fibonacci series or sum of a series of fibonacci numbers

A series is given as $1,6,7,13,20,33,.......$ and so on Find the sum of first 52 terms? what i know is The sum of the first n Fibonacci numbers is the [(n + 2)nd Fibonacci number - 1] . So the sum ...
243 views

### Pisano periods of fibonacci mod

The wikipedia article on Pisano periods utilises the Binet's formula and quadratic residues to find $f(n)$ such that $F_n=f(n) \pmod{p}$ where $p$ is a prime number and $F_n$ is a Fibonacci number. ...
86 views

### Fibonacci sequense, problem od division

How to show that $7\mid F_m\Longrightarrow 8\mid m$ and $4\mid F_m\Longrightarrow 6\mid m$, knowing that (I) Two consecutive terms in the Fibonacci sequence are relatively prime. (II) In ...
1k views

### Strong Induction Proof: Fibonacci number even if and only if 3 divides index

The Fibonacci sequence is defined recursively by $F_1 = 1, F_2 = 1, \; \& \; F_n = F_{n−1} + F_{n−2} \; \text{ for } n ≥ 3.$ Prove that $2 \mid F_n \iff 3 \mid n.$ Proof by Strong Induction : ...
89 views

### How to prove that the Fibonacci sequence $7\mid U_m\Longrightarrow 8\mid m$ and $4\mid U_m\Longrightarrow 6\mid m$

How to prove that the Fibonacci sequence $$7\mid U_m\Longrightarrow 8\mid m$$ and $$4\mid U_m\Longrightarrow 6\mid m$$I was confused because there $\{ 4,7 \}$ in Fibonacci sequece
268 views

### Divisibility and the Fibonacci sequence

While studying the Fibonacci sequence I encountered this problem in the handout, and I can not understand how to do it. Show that if the Fibonacci sequence has a term divisible by a natural number ...
94 views

### Two issues of Number Theory

Knowing in Fibonacci sequence$$u_n\mid u_m\Longleftrightarrow n\mid m$$ Question 1: In Fibonacci sequence, show that $$5\mid u_m\Longleftrightarrow 5\mid m$$ Show: $\Longrightarrow$ In ...
142 views

### Statement on the Fibonacci sequence

Question: Let $n,m,\in\mathbb{N^*}$ with $n>1$ and let $u_n$ denote the $n$-th term of the Fibonacci sequence, then $$u_{n+m}=u_{n-1}u_m+u_nu_{m+1}$$ I know these theorems: Two consecutive ...
112 views

### Is Fibonacci sequence the minimum of unique pairwise sum sequence?

Let $(a_n)_{n=1}^\infty$ be a strictly increasing (condition added per earlier answer of Amitesh Datta) sequence of natural numbers where all pairwise element sums are unique. Can anyone prove or ...
119 views

### Sums and products involving Fibonacci

In summary, if $\phi$ is the golden ratio, I want to show: \begin{align} \sum_{n=1}^\infty \frac1{F_n} &= 4-\phi \\ \sum_{n=1}^\infty \dfrac{(-1)^{n+1}}{F_nF_{n+1}} &= \phi-1 \\ ...
238 views

### Fibonacci Cubes: $F_n^3 + F_{n+1}^3 - F_{n-1}^3 =F_{3n}$

Prove $$F_n^3 + F_{n+1}^3 - F_{n-1}^3 =F_{3n}$$ I've tried induction, either its just very long or a neat trick is required in the inductive step but for some odd reason its not working out. ...
389 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 ...
612 views

### What are the first 3 digits of the product of the first 1000 fibonacci numbers

What are the first 3 digits of the product of the first 1000 Fibonacci numbers? Could anyone give me hints on how to start this problem? I haven't done a problem like this before and I am curious ...
338 views

### Computing first digits of Fibonacci numbers

How would you compute the first $k$ digits of the first $n$th Fibonacci numbers (say, calculate the first 10 digits of the first 10000 Fibonacci numbers) without computing (storing) the whole numbers ...
95 views

### Fibonacci series in 0-Even-Odd-Even-Odd-N series up to N

Another question from the test for the Normale of Pisa: Consider the series $S_n$ of integer numbers repeteandly even - odd - even - odd that start with 0 and finish with n, so with n = 3 we get 2 ...
157 views

### $n +1$th Fibonacci number modulo $n$

The Pisano period studies the $n$th Fibonacci number $F_{n}$ modulo $n$. Is there anything about $F_{n + 1} \pmod n$?
139 views

### Proving that $\alpha^{n-2}\leq F_n\leq \alpha^{n-1}$ for all $n\geq 1$, where $\alpha$ is the golden ratio

I got stuck on this exercise. It is Theorem 1.15 on page 14 of Robbins' Beginning Number Theory, 2nd edition. Theorem 1.15. $\alpha^{n-2}\leq F_n\leq \alpha^{n-1}$ for all $n\geq 1$. Proof: ...
209 views

### Simple Fibonacci / Lucas Numbers Relationship

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 ...
393 views

### Fibonacci numbers divisible by $9$

The $n$th Fibonacci number $F_n$ is defined as follows,$$F_1=F_2=1\mbox{ and } F_{n+2}=F_{n+1}+F_{n}\mbox{ for } n\geq 1$$ I want to know how many of the first $1000$ Fibonacci numbers are divisible ...
2k 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 proof it ? Can you help me ? Let $f_n$ be Fibonacci Sequence. ...
134 views

### How to solve for the $n$-th Fibonacci number that is greater than or equal to $N$?

The general formula for the $n$-th Fibonacci number is: $$\frac{\phi^n - (1 - \phi)^n}{\sqrt{5}}$$ where $$\phi = \frac{1 + \sqrt{5}}{2}$$ Given $N$, is there a way to solve for $n$ in this ...
2k views

### Every natural number can be written as the sum of distinct Fibonacci numbers?

Can anyone hint me to prove: $\forall n\in \mathbb{N}: \exists$ Fibonacci numbers $F_{i_1},\ldots,F_{i_k}$ such that: $$\sum F_{i_k}=n$$ Note: Every Fibonacci number can appear only once. Thanks
111 views

### Power Variant of Fibonacci sequence

I was trying to simplify the following sequence, such that I can calculate the $n$th term in $\log n$ time. This can be done, if we can express the $n$th in terms of combinations of Fibonacci like ...
171 views

### Need formula for sequence related to Lucas/Fibonacci numbers

I am trying to get a formula for the nth term of the following sequence: 2, 14, 22, 58, 266, 398, 1042, 4774, 7142, 18698, 85666, 128158, 335522,... It's not in OEIS and as far as I can tell ...
206 views

### Fibonacci and Lucas relations

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 ...
163 views

### Fibonacci numbers moduli

I have made some observation on very interesting material on Fibonacci series. I need some help in proving them mathematically. We can observe that the periodicity of Fibonacci numbers modulo m, ...
297 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 ...
184 views

### If $m$ and $n$ are positive integers, then $(F_m,F_n)=F_{(m,n)}$.

Edit: The $F$'s are Fibonacci numbers. I need an idea on how to show the following: If $m$ and $n$ are positive integers, then $(F_m,F_n)=F_{(m,n)}$. I believe that using the fact that ...
458 views

### Showing that $f_{2n+1}=f_{n+1}^2+f_n^2$.

I am trying to solve the following exercise: Let $f_1=1$, $f_2=1$, $f_{n+1}=f_n+f_{n-1}$, where $n\in\mathbb{N}$. Show that $f_{2n+1}=f_{n+1}^2+f_n^2$. I have not had much progress, but this is ...
164 views

### Prove for Fibonacci numbers: $3\mid f(n) \iff 4\mid n$

Let $f(n)$ be the $n$th Fibonacci number. Prove that $$3\mid f(n) \iff 4\mid n$$ I tried to use induction to prove it but I couldn't continue when I reached $n+1$ case.
280 views

### Modular Fibonacci series

My second observation is the following. Let $p$ be a prime not equal to $5$. Then $5$ is a quadratic residue modulo $p$ if and only if $p\equiv\pm1\pmod5$. And $5$ is not a quadratic residue modulo ...
3k views

### Project Euler, Problem #25

Problem #25 from Project Euler asks: What is the first term in the Fibonacci sequence to contain 1000 digits? The brute force way of solving this is by simply telling the computer to generate ...
### $f_n$ is divisible by $4$ if and only if $n$ is divisible by $6$
I thought I had this question down, but while looking over my solution, I think I'm missing a step. I want to show for $f_n$ the nth fibonacci number, that $f_n$ is divisible by $4$ if and only if ...