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

5
votes
3answers
307 views

Closed form for the sum of even fibonacci numbers?

I recently took a look a project euler, and I am trying to think of a smart way to do number 2. I looked at the sequence, and I saw that the question is basically asking for $$ \sum_{i=1}^n F_{3i} $$ ...
14
votes
1answer
1k views

Combinatorial proof of a Fibonacci identity: $n F_1 + (n-1)F_2 + \cdots + F_n = F_{n+4} - n - 3.$

Does anyone know a combinatorial proof of the following identity, where $F_n$ is the $n$th Fibonacci number? $$n F_1 + (n-1)F_2 + \cdots + F_n = F_{n+4} - n - 3$$ It's not in the place I thought it ...
5
votes
4answers
534 views

Fibonacci identity proof

I've been struggled for this identity for a while, how can I use combinatorial proof to prove the Fibonacci identity $$F_2+F_5+\dots+F_{3n-1}=\frac{F_{3n+1}-1}{2}$$ I know that $F_n$ is number of ...
3
votes
3answers
104 views

Write $\sum_{1}^{n} F_{2n-1} \cdot F_{2n}$ in a simpler form, where $F_n$ is the n-th element of the Fibonacci sequence?

The exercise asks to express the following: $\sum_{1}^{n} F_{2n-1} \cdot F_{2n}$ in a simpler form, not necessarily a closed one. The previous problem in the set was the same, with a different ...
0
votes
2answers
83 views

Sum of Fibonacci-Numbers

Is there a closed formula for the sum of the first $n$ even (or odd) Fibonacci numbers, like there is one for the $n$th number (Moivre-Binet)?
0
votes
2answers
88 views

Prove that a Fibonacci number is greater than $ φ^n$

How can I prove the following: If $f_n$ is a number of the Fibonacci sequence and φ= $\frac{1+\sqrt{5}}2$, then $f_n > φ^n$ for every $n >2$? I have tried using induction but I can't ...
0
votes
3answers
93 views

partial Fibonacci summation

Let $F_{n}$ be the n-th Fibonacci number. How to calculate the summation like following: $\sum_{n \geq 0} F_{3n} \cdot 2^{-3n}$
3
votes
1answer
62 views

All pairs sum to a different value

If we consider the integers $\{1,\dots,n\}$, what is the size of the largest subset $A$ so that all distinct pairs $x, y \in A$ sum to a different value? For this to make sense $(x,y)$ and $(y,x)$ ...
4
votes
2answers
278 views

Prove that the limit of two consecutive fibonacci numbers EXISTS. [duplicate]

Using the definition of Fibonacci numbers, $F_n=F_{n-1}+F_{n-2}$, I can prove that the limit of $\frac{F_{n+1}}{F_n}$ as $n\to\infty$ is $\phi$ if we assume that the limit exists. How can we prove ...
1
vote
1answer
126 views

Calculate Number of ways to make the grid

We wish to tile a grid of size Nx2 with rectangles (dominoes) of 2x1 (in either orientation).For given N I need to find the number of different ways to tile the grid. EXAMPLE : For N=1 answer is 1 ...
0
votes
0answers
54 views

Sequence of $r_n:=\frac{x_{n+1}}{x_n}$ where $x_n$ is a sequence

Let $f:X\rightarrow X$ be a function on some complete metric space $(X,d)$. Let, $x_n$ is a sequence in the metric space defined by $x_{n+1}=f(x_n)$ and starting from $x_0$. My questions are (1) ...
4
votes
5answers
825 views

Where do the first two numbers of Fibonacci Sequence come from? [duplicate]

I'm trying to code a simple algorithm that prints out the $n^{th}$ Fibonacci number. However, my program requires the initial seed values $F_0 = 0$ and $F_1 = 1$, when I'm hopeful I can figure ...
0
votes
1answer
40 views

asymptotics of $F_n = F_{k-1} F_{n-k-1} + F_{k-1} F_{n-k} + F_{k-2} F_{n-k} $

Starting from $F_n = F_{k-1} F_{n-k-1} + F_{k-1} F_{n-k} + F_{k-2} F_{n-k} $ and letting $F_k \approx \phi^k$, I am hoping to find the corresponding statement for the Golden ratio: $\phi^n = 2 ...
2
votes
3answers
307 views

Limit of the ratio of consecutive Fibonacci numbers [duplicate]

I have read in a book that the limit of the ratio of consequent Fibonacci numbers is the golden ratio. However, it was just mentioned thus not justified. So, my question is how would you derive the ...
1
vote
0answers
90 views

I am trying to prove this problem by induction, how can can i prove the following?

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 ...
5
votes
1answer
532 views

How to prove that Fibonacci number is integer?

How to prove that formula for Fibonacci numbers are always integers, for all $n$: $$ F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}} $$ where, $\varphi = \frac{1 + \sqrt{5}}{2}$ and $\psi = \frac{1 - ...
0
votes
1answer
169 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 ...
4
votes
4answers
565 views

How to prove this is a rational number

I'm not sure how to prove this is a rational number $\frac{q}{m}$, can some one show me? $$\frac{q}{m}=\frac{(\frac{1+\sqrt5}{2})^n - (\frac{1-\sqrt5}{2})^n}{\sqrt5}$$
5
votes
2answers
178 views

Number of bitstrings with $000$ as substring

I have $F_n$ number of bitstrings that have $000$, How would I prove that for $n \ge 4$ , $a_n = a_{n-1} +a_{n-2}+a_{n-3}+ 2^{n-3}$? Now there are many ways to go about this but if I choose starting ...
5
votes
1answer
295 views

What is wrong with my induction proof?

The Fibonacci sequence is defined by $a_1 = 1, a_2 = 1$ and for all $n \ge 2, a_{n+1} = a_n + a_{n-1}$. Thus the sequence begins $$1,1,2,3,5,8,13,21,...$$ prove that for all $n \ge 1, a_n < ...
5
votes
1answer
227 views

Sum of digits in Fibonacci sequence

This is my first question here so please go easy on me. If you add the digits of each number on the Fibonacci sequence until your number is less than 10, it seems that you get a pattern of 24 numbers ...
1
vote
1answer
436 views

Formula for binary sequences of length m with no n consecutive 1s?

Formula for binary sequences of length $m$ with no $n$ consecutive $1$s? I know The number of binary strings of length $m$ without consecutive $1$s is the Fibonacci number $F_{m+2}$. But how about ...
8
votes
1answer
115 views

Is this number rational or irrational?

Start writing down the Fibonacci numbers, using two digits for each one 01 01 02 03 05 08 13 21 34 55 ... Eventually you will reach three digit numbers. When ...
0
votes
2answers
104 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 ...
2
votes
2answers
105 views

Internet problem solving contest question

I am trying to solve a problem from the IPSC http://ipsc.ksp.sk/2001/real/problems/f.html It basically asks to compute the following recursion. ...
3
votes
3answers
290 views

Another way to go about proving Binet's Formula

As I showed in another question of mine, it is easy to prove that $$\tag{1}\phi^{n+1} =F_{n+1} \phi+F_{n }$$ given $F_1=1$ , $F_2=1$ , $F_{n+1}=F_n+F_{n-1}\text{ ; }n\geq2$. Now, extending $(1)$ ...
0
votes
2answers
29 views

Express recursive funtion in Fibonacci

Given the Fibonacci function and the function $L_n = L_{n-1} + L_{n-2} + 1$, how do I go from this: $L_n + 1 = L_{n-1} + L_{n-1} + 1 + 1 \\ (L_n + 1) = (L_{n-1} + 1) + (L_{n-2} + 1)$ To this: $L_n = ...
7
votes
1answer
225 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
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 ...
1
vote
4answers
95 views

New Fibonacci sequence

I have new Fibonacci number That I want to know is there any special direct formula to count f(n). like the normal Fibonacci: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2) For example I want to ...
2
votes
0answers
69 views

Lucas Number Equivalent of the Pisano Period?

I'm doing some work with the Pisano Period, and it's leading to also talk about the Lucas numbers $mod \ m$, and their period. Is there a specific notation already designated? Sticking with using a ...
4
votes
3answers
199 views

Probability that a chosen number will be a Fibonacci number

Suppose that I randomly choose an integer $x$ with $1 \leq x \leq n$ where $n$ is a natural number. What is the probability that $x$ will be a Fibonacci number?
6
votes
1answer
236 views

Let $F_n$ be a Fibonacci number and $p$ a prime. Verify that for $p \le 61$, if $p\equiv\pm1 \pmod{5}$ then $p\mid F_{p-1}$

Define the Fibonacci entry point of $p$ to be the least integer $n$ such that $p\mid F_n$ So for example, for $p = 3$ - the Fibonacci entry point is $n = 4$ since $F_4 = 3$ and obviously $3\mid 3$. ...
-2
votes
1answer
70 views

Application of convergence of Fibonacci series

'There are infinite prime numbers' is a fact that can be deduced by 'reciprocal of primes diverges' statement, so from this can we deduce the fact that --> 'there are finite Fibonacci numbers in ...
1
vote
1answer
88 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
3answers
886 views

Fibonacci numbers and proof by induction

Consider the Fibonacci numbers $F(0) = 0; F(1)=1; F(n) = F(n-1) + F(n-2)$. Prove by induction that for all $n>0$, $$F(n-1)\cdot F(n+1)- F(n)^2 = (-1)^n$$ I assume $P(n)$ is true and try to show ...
0
votes
2answers
858 views

Summation of series of product of Fibonacci numbers

What is the sum of following product of Fibonacci numbers $$\sum_{k=1}^{n-1} Fib(k)*Fib(n+3-k)$$ can anyone suggest only approach to find general term?
-1
votes
3answers
118 views

Fibonacci Sequence or Golden Ratio?

Using the polar coordinate system, $r$ increases directly with $\theta$. In other words, $r=k\theta$. Which of the following shapes is constructed? A) Fibonacci Sequence B) Golden Ratio C) ...
1
vote
1answer
49 views

Pascal/Fibonacci and Combinatorics notation

I'm doing Pascal's Triangle and there are a ton of questions related to Pascal and the Fibonacci numbers embedded in the triangle, but I have a question about combinatorics which is most likely a very ...
6
votes
3answers
186 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 ...
2
votes
4answers
108 views

Fibonacci proof question [closed]

Show that $$f_{n+1}f_{n-1}-f_n^2=(-1)^n$$ when $n$ is a positive integer and $f_n$ is the $n$th Fibonacci number.
1
vote
1answer
73 views

Fibonacci… Easier by induction or directly via Binet's formula

I have tried both for several of them and haven't been able to get anywhere in 3 hours of work. It seems to not matter which method I choose, I end up in the middle of a HUGE mess of algebra. Could ...
2
votes
3answers
363 views

Why is 11 times the 7th term of a fibonacci series equal to the sum of 10 terms?

Why is 11 times the 7th term of a fibonacci series equal to the sum of 10 terms? I was watching scam-school on youtube the other day and this number trick just astonished me. Can someone please ...
2
votes
3answers
127 views

Golden ratio / Fibonacci which branch of math?

Friends, The Golden ratio / Fibonacci sequence are studied under which branch of math? Can you recommend some good textbooks on the subject? Thanks
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 : ...
6
votes
1answer
175 views

Rectangle with coordinates of all vertices Fibonacci numbers

Suppose the coordinates of all vertices of a given (non-degenerate) rectangle are Fibonacci numbers. Suppose that the rectangle is not such that one of its vertices is on the $x$-axis and another on ...
4
votes
1answer
125 views

Proof/Disproof of property of perpendicular lines in the Fibonacci grid

In my struggle to try to make progress on this question, I am trying to find a proof or counterexample of the following, stronger, statement: Denote by $K$ the subset of the Gaussian integers such ...
2
votes
4answers
118 views

Fibonacci sequence proof

Prove the following: $$f_3+f_6+...f_{3n}= \frac 12(f_{3n+2}-1) \\ $$ For $n \ge 2$ Well I got the basis out of the way, so now I need to use induction: So that $P(k) \rightarrow P(k+1)$ for some ...
0
votes
1answer
60 views

Proof by Induction for a $f_3 + f_6 + · · · + f_{3n} = \frac{1}{2} (f_{3n+2} - 1)$ [duplicate]

The Fibonacci numbers are defined as follows: $f_0 = 0,\ f_1 = 1$, and for $n ≥ 2,\ f_n = f_{n−1} +f_{n−2}$. Prove that for every positive integer $n$, $$f_3 + f_6 + \ldots + f3_n = \frac{1}{2} ...
1
vote
1answer
45 views

Question about Fibonacci sequence

I proved that at Fib. $$\frac{1}{f_{n-1}f_{n+1}}=\frac{1}{f_{n-1}f_{n}}-\frac{1}{f_{n}f_{n+1}}$$ I need to prove two thing: 1.$$\sum_{n=2}^{\infty}\frac{1}{f_{n-1}f_{n+1}}=1$$ 2. ...