-1
votes
2answers
64 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 ...
0
votes
0answers
21 views

Fibonacci number “alpha-beta” induction proof [duplicate]

The Question: Use mathematical induction to prove the following: let n be a positive integer and let alpha = [1+sqrt(5)]/2 and beta = [1-sqrt(5)]/2. Then the nth Fibonacci number f_n is given by ...
0
votes
2answers
82 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 ...
1
vote
1answer
26 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 ...
7
votes
1answer
164 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. ...
1
vote
1answer
77 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 ...
1
vote
4answers
852 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 ...
1
vote
1answer
197 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. ...
0
votes
0answers
70 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 ...
5
votes
3answers
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 : ...
0
votes
2answers
86 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
1
vote
4answers
196 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 ...
0
votes
1answer
90 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 ...
2
votes
3answers
132 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 ...
2
votes
2answers
106 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 ...
1
vote
1answer
93 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 \\ ...
9
votes
4answers
224 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. ...
8
votes
7answers
348 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 ...
-1
votes
3answers
601 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 ...
3
votes
2answers
234 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 ...
1
vote
3answers
88 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 ...
4
votes
2answers
154 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$?
1
vote
4answers
138 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: ...
2
votes
1answer
184 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 ...
7
votes
2answers
368 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 ...
3
votes
4answers
1k 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. ...
1
vote
1answer
127 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 ...
6
votes
2answers
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
1
vote
1answer
101 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 ...
1
vote
1answer
151 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 ...
1
vote
0answers
186 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 ...
2
votes
1answer
154 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, ...
4
votes
1answer
290 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
180 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 ...
4
votes
5answers
422 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 ...
3
votes
3answers
163 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.
1
vote
1answer
266 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 ...
33
votes
7answers
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 ...
3
votes
2answers
530 views

$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 ...
8
votes
1answer
5k views

Prove that two any consecutive terms of Fibonacci sequence are relatively prime

Prove that two any consecutive terms of Fibonacci sequence are relatively prime My attempt: We have $f_1 = 1, f_2 = 1, f_3 = 2...$. So obviously $\gcd(f1, f2) = 1$. Suppose that $\gcd(f_n, ...
4
votes
1answer
121 views

Prove that If $f_n$ where $n>3$ is prime, then $n$ is prime for a Fibonacci series where $f_1$=$f_2$=1

This problem came up in my conversation with a friend—not sure how basic it is, but it seems quite interesting: Prove that if $f_n$ where $n>3$ is prime, then $n$ is prime for a Fibonacci sequence ...
5
votes
3answers
406 views

Fibonacci identity

Consider this Fibonacci equation: $$f_{n+1}^2 - f_nf_{n+2}$$ The problem asked to write a program with given n, output the the result of this equation. I could use ...
7
votes
1answer
260 views

Prove: the intersection of Fibonacci sequence and Mersenne sequence is just $\{1,3\}$

$$\frac{{{\varphi ^n} - {{(1 - \varphi )}^n}}}{{\sqrt 5 }} = {2^m} - 1 .$$ Here $\varphi = \frac{{1 + \sqrt 5 }}{2}$ . This integer equation has no solution for $n>3$ and $m>2$. How to prove?