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

3
votes
1answer
31 views

Why Fibonacci(prime-1) or Fibonacci(prime+1) is divisible by that prime?

Why Fibonacci(prime-1) or Fibonacci(prime+1) is divisible by that prime and Fibonacci(nonprime-1) or Fibonacci(nonprime+1) is not divisible by that nonprime? Is there any elegant proof of that?
22
votes
2answers
12k 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, ...
1
vote
1answer
52 views

What is the Fibonacci-like sequence called where one sums the last 3 numbers

The Fibonacci-sequence is defined like. $F_{x+1} = F_{x} + F_{x-1}; F_0 = 0, F_1=1, x \in {\Bbb N}$ Is there a special name for this sequence: $F_{x+1} = F_{x} + F_{x-1} + F_{x-2}$ ? Which?
5
votes
1answer
49 views

Fibonorial of a fractional or complex argument

Let $F(n)$ denote the $n^{\text{th}}$ Fibonacci number$^{[1]}$$\!^{[2]}$$\!^{[3]}$. The Fibonacci numbers have a natural generalization to an analytic function of a complex argument: ...
34
votes
5answers
13k views

Checking if a number is a Fibonacci or not?

The standard way (other than generating up to $N$) is to check if $(5N^2 + 4)$ or $(5N^2 - 4)$ is a perfect square. What is the mathematical logic behind this? Also, is there any other way for ...
1
vote
1answer
66 views

What is the best way to inscribe a golden rectangle into a pentagon? Do more golden ratios emerge?

Below I drew a golden rectangle in a pentagon in Adobe Illustrator. What would be the best way to inscribe a golden rectangle into a pentagon as shown in the figure below in a mathematical manner? ...
0
votes
2answers
38 views

What Does a Subscript Do to a Number? [closed]

So I had a math question that had a formula for that said Tn= arn-1 Where a is the first sequence and r is the common ratio. For example, in the sequence 10,40,160,640,..., a=10, and ...
0
votes
3answers
129 views

Help on require answer $\int_0^1\frac{2}{[1+x+(-\phi)^{-n}(1-x)]^2}dx=\frac{1}{-{\phi}F_n+F_{n+1}+1}$

$\phi=\frac{1+\sqrt5}{2}$ $F_0=0$, $F_1=1$ ;$F_{n+1}=F_n+F_{n-1}$ ; Fibonacci numbers (0,1,1,2,3,5,...) Show that, $$\int_0^1\frac{2}{[1+x+(-\phi)^{-n}(1-x)]^2}dx=\frac{1}{-{\phi}F_n+F_{n+1}+1}$$ ...
0
votes
0answers
241 views

Number of ways to express a Fibonacci number as the sum of N other Fibonacci Numbers.

How do I find the number of ways to express a Fibonacci number as the sum of N other Fibonacci Numbers? There can be repetitions. Consecutive Fibs are allowed.
1
vote
1answer
47 views

Induction proof for Fibonacci sum different notation

This question was asked but using sum notation and I am trying to relate it to what I am doing. I am trying to prove by induction that for the Fibonacci series, $a_1+a_2+...+a_n=a_{n+2}-1$ is true. ...
-3
votes
0answers
111 views

Find coefficient of $x^k$ in a given polynomial [closed]

Assume a polynomial: $$ (x^a + x^b + x^c + x^d + \cdots )^n $$ where $a,b,c,d,\ldots$ are Fibonacci numbers, starting from $1, 2, 3, 5, 8, 13,\ldots$. Find the coefficient of $x^k$ in it. ...
2
votes
1answer
72 views

Golden Ratio & Fibonacci - Charles de Gaulle 13-unit two-beamed cross problem.

Here is the question: The two-beamed cross, made popular by Charles de Gaulle, is formed from 13 unit squares as shown below. A straight line $BC$ drawn through point $A$ divides the cross in such ...
8
votes
4answers
796 views

Sum of cubes of first n fibonacci numbers

Let $\{f_k\}$ be the sequence of fibonacci numbers. It is well-known that $\sum_{k=1}^n f_k=f_{n+2}-1$ and $\sum_{k=1}^n f_k^2=f_n f_{n+1}$ . Is there a formula for $\sum_{k=1}^n f_k^3$ ?
3
votes
2answers
65 views

Proof of $1^3+1^3+2^3+3^3+5^3+\cdots +F_n^3=\frac{F_nF_{n+1}^2+(-1)^{n+1}[F_{n-1}+(-1)^{n+1}]}{2}$

Fibonacci series $F_0=0$, $F_1=1$; $F_{n+1}=F_n+F_{n-1}$ This is a well known identity $1^2+1^2+2^2+3^2+5^2+\cdots +F_n^2=F_nF_{n+1}$ I was curious and look every websites for a closed form of ...
-1
votes
0answers
21 views

Fibonacci sequence algorithm function calls

Given the following pseudo code which is used to calculate Fibonacci numbers, how would you be able to determine roughly how many function calls are made by the program to calculate ...
0
votes
6answers
331 views

What is the sum of all the Fibonacci numbers from 1 to infinity.

Today I believe I had found the sum of all the Fibonacci numbers are from $1$ to infinity, meaning I had found $F$ for the equation $F = 1+1+2+3+5+8+13+21+\cdots$ I believe the answer is $-3$, ...
3
votes
2answers
77 views

Fibonacci Pairs

Find all positive integer solutions to $y^2 - xy - x^2 = 1$ and $y^2 - xy - x^2 = -1$ I have written a C++ program to yield some solution for large constants. I must make conjectures based on the ...
0
votes
1answer
32 views

Doubt in a property of the Fibonacci Series.

I came across this question in a book where they asked me to prove that there are exactly four terms such that $F_{F_n}= F_n$. Well, I think that this is false and that there are exactly three. I have ...
1
vote
1answer
22 views

Exponential generating function and fibonnaci

$F_n$ is the $n$th Fibonnaci number. $$g(x) = \sum^\infty_{n=0}F_n \frac{x^n}{n!}$$ Prove that $$g''(x)=g'(x)+g(x)$$ I've never dealt with derivatives in the above form so I am not exactly sure ...
-1
votes
0answers
34 views

PHI Conjecture: Fibonacci Number Line Segments & Simple Golden Ratio Puzzle?

This is a golden ratio conjecture. Does the golden ratio exist as conjectured below? The three line segments in the figure below have lengths of the Fibonacci numbers 2, 3, and 5. blue=2 green=3 ...
0
votes
0answers
28 views

Proofing that the Lucas numbers come closer to the Phi rounded numbers then the Fibonacci numbers.

Morning everyone, Bit of background, I'm a mid level programmer with very limited mathematics skills. As part of an assessment for a new role I've been asked to complete a technical task which ...
3
votes
1answer
88 views

Is there a number besides $\phi$ that either squared or added one gives the same answer?

Those who know golden ratio $\phi$ (phi) constant, know for sure that it is an interesting constant. It is roughly $\phi=1.618034...$ . It is present almost everywhere in nature and it has many very ...
1
vote
2answers
45 views

Prove equality for Fibonacci sequence [duplicate]

I have to show that $F_{n+k} = F_{k}F_{n+1} + F_{k-1}F_{n}$, where $F_{n}$ is nth Fibonacci element. I was trying with mathematical induction applied to n and saying k is constant. step for $n=1$ ...
0
votes
4answers
39 views

Prove that the given property of the fibonacci number directly from the definition

$F(n)= 3F(n-3)+2F(n-4)$ for $n \ge 5$. I just don't understand the whole process of this, my instructor has a rather weird way of explaining and I couldn't understand. can someone help me ...
1
vote
0answers
33 views

An identity for $q-$Fibonacci numbers if $q$ is a root of unity.

In his proof of the Rogers-Ramanujan identities I. Schur introduced two $q-$analogues of the Fibonacci numbers ${F_n}({q})$ and ${G_n}({q})$, which satisfy ${F_0}({q})=0$, ${F_1}({q})=1$ and ...
0
votes
3answers
95 views

Prove $\phi^n = \phi F_n + \text{(another Fibonacci number)}$ using mathematical induction.

I need to prove the following equation using mathematical induction and using the phi values if necessary. $\phi^n = \phi F_n + \text{(another Fibonacci number)}$ In this proof, it is kind of hard ...
-7
votes
0answers
40 views

Mathematical proof by induction. [duplicate]

How to prove the following using mathematical proof by induction? $\phi^n = \phi\times F_n + F_{n-1}$ $\phi = 1 + \sqrt 5 /2$ Fn is the Fibonacci number. I tried solving this using induction but ...
2
votes
2answers
49 views

Restrictions for rule of general sequence: $T_{n+2}=T_{n} + T_{n+1}$

This is a rule which gives a sequence where $11$ times the seventh term ($11 t_7$) is equal to the sum of the first $10$ terms ($s_{10}$), where the first two starting numbers can be chosen. Do any ...
0
votes
1answer
38 views

Fibonacci numbers and proving using mathematical induction

I need to prove the rule below using Mathematical proof by induction but actually I'm stuck in the middle of the proving. $$F_n^2 - F_{n-1}F_{n+1} = (-1)^{n+1} {~\rm for~} n>1$$ If someone can ...
-1
votes
0answers
32 views

Proving the GCD property of the Fibonacci numbers [duplicate]

How to prove the following GCD property of the Fibonacci number sequence using mathematical proof by induction? gcd (Fn , Fm) = F (gcd(n , m)) Help is much appreciated. Thank you in advance.
1
vote
1answer
62 views

Show that $\sum_{k=1}^{\infty}\frac{F_{2^{k-1}}}{L_{2^k}-2}=\frac{15-\sqrt{5}}{10}$

Show that$$\sum_{k=1}^{\infty}\frac{F_{2^{k-1}}}{L_{2^k}-2}=\frac{15-\sqrt{5}}{10},$$ where $F_n$ is a Fibonacci number and $L_n$ is a Lucas number.$^1$ Motivation: For example, when ...
1
vote
0answers
42 views

Proofs with Fibonacci and Lucas numbers via induction

How would I go about proving the following sequence using induction on $k$? $2F_{2n+k} = F_{n+k}L_n + F_nL_{n+k}$ I know I have to show that it's true for $k = 1$, but I can't even seem to be able ...
0
votes
0answers
28 views

Fibonacci Sequence and Time taken

Consider the following (incomplete) java code, which calculates the Fibonacci numbers ...
5
votes
2answers
145 views

Deducing the closed form for pentagonal numbers

Consider the sequence: $0,1,5,12,22,35,51,70,92,117,145,176,\ldots$ Find both a recurrence and a closed form for this sequence. I've done some research and found out that the majority ...
40
votes
5answers
977 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
0answers
21 views

Pisano Period - Fibonacci

I have to construct an algorithm which will return a fibonacci number mod another integer. I know that i have to implement the Pisano period. I know how to receive it, but the problem comes when I ...
1
vote
3answers
36 views

Prove that the $c_{n}$ in $\frac{1}{1-z-z^{2}}=\displaystyle\sum_{n=0}^{\infty}c_{n}z^{z}$ satisfy a Fibonacci-like recurrence relation

I need to prove that the coefficients $c_{n}$ of the expansion $\frac{1}{1-z-z^{2}}\sum_{n=0}^{\infty}c_{n}z^{n}$ satisfy the recurrence relation $c_{0}=c_{1}=1$, $c_{n}=c_{n-1}+c_{n-2}$, by ...
9
votes
1answer
51 views

Alternative “Fibonacci” sequences and ratio convergence

So the well known Fibonacci sequence is $$ F=\{1,1,2,3,5,8,13,21,\ldots\} $$ where $f_1=f_2=1$ and $f_k=f_{k-1}+f_{k-2}$ for $k>2$. The ratio of $f_k:f_{k-1}$ approaches the Golden Ratio the ...
7
votes
1answer
1k views

Another way to go about proving the limit of Fibonacci's sequence quotient.

It is not difficult to inductively prove that $$\eqalign{ & \phi = \phi + 0 \cr & {\phi ^2} = \phi + 1 \cr & {\phi ^3} = 2\phi + 1 \cr & {\phi ^4} = 3\phi + 2 ...
9
votes
1answer
244 views

Number of ways to write $n$ as sum of odd or even number of Fibonacci numbers

In our discrete mathematics exercises I came of with the question: Prove that the coefficients of $\prod_{n\geq2}{(1-x^{F_n})}=1-x-x^2+x^4+x^7+\dots$ can only be $-1,1$ or $0$, where $F_n$ ...
3
votes
1answer
81 views

Closed form for Fibonacci numbers

We know the closed form for Fibonacci number as $F_n=\frac{1}{\sqrt5}\left[\left(1+\frac{\sqrt5}{2}\right)^n−\left(1−\frac{\sqrt5}{2}\right)^n\right]$ But while finding $F_n \pmod{99991}$ the closed ...
3
votes
3answers
58 views

Recurrence Relation of a series

I know this would seem lame, but I need to ask this. I was trying to solve some recurrence based problems and I came across this series. $1,2,4,7,12,\dots$ Question was: To find the recurrence ...
0
votes
1answer
69 views

Fibonacci polynomials

The Fibonacci polynomials are defined by the recurrence relation: $$ F_{n+1}(x)=xF_{n}(x)+F_{n-1}(x)\, . $$ with $F_1(x)=1$ and $F_2(x)=x$. How can I prove: $$ F_n(x)=\sum_{j=0}^{\lfloor \frac{n-1}{2} ...
-1
votes
2answers
59 views

How can I prove by induction that this is a closed form of the Fibonacci sequence? [duplicate]

How can I prove by induction that this is a closed form of the Fibonacci sequence? $$F_n=\frac1{\sqrt5}\left(\frac{1+\sqrt5}2\right)^{n+1}-\frac1{\sqrt5}\left(\frac{1-\sqrt5}2\right)^{n+1}$$ I've ...
1
vote
1answer
124 views

Formula for fibonacci(a+b).

Is there any general formula for fibonacci(A+B)? I have tried to derive it , and got following results. $$\begin{align} &fib(a+1)=1*fib(a)+fib(a-1)\\ &fib(a+2)=2*fib(a)+fib(a-1)\\ ...
3
votes
2answers
300 views

Magic Squares with Lucas and Fibonacci Numbers

I am quite curious about can we construct magic squares using only Lucas and Fibonacci numbers(of course not repeating them? If yes, how can we construct them? And if not , what is the proof?
7
votes
5answers
9k views

Prove this formula for the Fibonacci Sequence

This formula provides the $n$th term in the Fibonacci Sequence, and is defined using the recurrence formula: $u_n = u_{n − 1} + u_{n − 2}$, for $n > 1$, where $u_0 = 0$ and $u_1 = 1$. Show that ...
0
votes
1answer
71 views

Partition function and Fibonacci n-th number upperbound

i need to proof this upperbound: "Call $p(n)$ the number of partitions of n (integer) and $F_n$ the $n-th$ Fibonacci number. Show that $p(n)\leq p(n-1) + p(n-2)$ and that $p(n)\leq F_n$ for $n\geq ...
2
votes
2answers
95 views

Fibonacci Numbers and Legendre symbol

How to prove congruence below ? $$F_{p-\left( \frac{5}{p}\right)} \equiv 0 \pmod p$$ Where $\displaystyle \left( \frac{}{}\right)$ is legendre symbol, and $\displaystyle p$ is a prime number.
0
votes
3answers
66 views

Prove by induction that the Fibonacci sequence $≤ [(1+\sqrt{5})/2]^{n−1}$, for all $n ≥ 0$.

If $F(n)$ is the Fibonacci Sequence, defined in the following way: $$ F(0)=0 \\ F(1)=1 \\ F(n)=F(n-1)+F(n-2) $$ I need to prove the following by induction: $$F(n) \leq ...