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

1
vote
1answer
637 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 ...
2
votes
0answers
103 views

Inequality with Fibonacci numbers

The sequence $F_n$ of natural numbers defined by equation $F_{n+2}=F_{n+1}+F_{n}$, with $F_0=0, F_1=1$ is called the Fibonacci sequence. The n-th term in the sequence is called the n-th Fibonacci ...
5
votes
2answers
223 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
541 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 ...
5
votes
4answers
2k 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}$$
1
vote
2answers
1k 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
176 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 ...
4
votes
1answer
265 views

Solve Recurrence Equation with Induction

Question: Given the recurrence equation for the recursive Fibonacci sequence program: $T(n) = T(n-1) + T(n-2) + b$ $T(0) = T(1) = a$ Using induction, show that $T(n) \leq f(n)$, where $f(n) = c2^n, ...
26
votes
3answers
1k views

Why does $\frac{1 }{ 99989999}$ generate the Fibonacci sequence?

$\frac{1}{99989999} = 1.00010002000300050008001300210034005500890144... \times 10^{-8}$ (Link), which includes the Fibonacci sequence $(1\ 1\ 2\ 3\ 5\ 8\ 13\ 21\ 55\ 89\ 144\ldots )$. This is ...
0
votes
2answers
407 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 ...
4
votes
1answer
119 views

Fibonacci numbers expressed as squares of lower Fibonacci numbers

I am no mathematician so my apologies for my ignorance. I notice that every number in the Fibonacci series can be expressed as a previous Fibonacci number squared plus or minus (alternating) another ...
2
votes
1answer
86 views

Source for relationship between $d$-ary Fibonacci numbers and generalized golden ratio?

I am not a mathematician (but a computer scientist) and stumbled across the following in the analysis of an algorithm (Berthold Vöcking: How Asymmetry Helps Load Balancing). The author gives Knuth: ...
2
votes
2answers
120 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. ...
0
votes
2answers
45 views

Express recursive function 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 = ...
1
vote
1answer
56 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 ...
2
votes
0answers
119 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 ...
2
votes
4answers
113 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 ...
3
votes
1answer
67 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)$ ...
9
votes
1answer
1k views

Proof that Fibonacci Sequence modulo m is periodic? [duplicate]

It's well known that the Fibonacci sequence $\pmod m$ (where $m \in \mathbb N$) is periodic. I have figured out a proof for this, but upon googling, I found proofs online that were far more ...
4
votes
3answers
332 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?
-1
votes
1answer
94 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 ...
2
votes
1answer
111 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
1answer
98 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} + ...
-1
votes
3answers
218 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
68 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 ...
7
votes
3answers
252 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
3answers
3k 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 ...
2
votes
4answers
120 views

Fibonacci proof question: $f_{n+1}f_{n-1}-f_n^2=(-1)^n$ [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
114 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 ...
5
votes
5answers
2k 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
286 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
4
votes
1answer
181 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
2answers
67 views

Why is $\sum_{k=0}^{n} f(n,k) = F_{n+2}$?

If $f(n,k)$ is the number of $k$ size subsets of $[ n ] = { 1 , \ldots , n }$ which do not contain a pair of consecutive numbers, how can I show that $\sum_{k=0}^{n} f(n,k) = F_{n+2}$? ($F_{n}$ is the ...
13
votes
2answers
415 views

Interpolated Fibonacci numbers - real or complex?

The common Binet-formula for the Fibonacci-numbers $$ f_n = {\varphi^n- (1-\varphi)^n \over \sqrt 5 } \small {\qquad \qquad \text{ where }\varphi={1+\sqrt 5\over 2}}$$ allows interpolation to ...
0
votes
3answers
279 views

Fibonacci divisibility

Is $2051$ a factor of any fibonacci number? It is not a factor of any perfect number. The prime factors of $2051$ are $7$ and $293$, which are both prime. the $8$th fibonacci number, is the first ...
1
vote
1answer
64 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
47 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. ...
2
votes
4answers
133 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 ...
6
votes
1answer
195 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 ...
1
vote
1answer
519 views

Proof for subsets of Fibonacci numbers

Let $a(n)$ be the number of subsets $A$ of $\{1,2,...,n\}$ with the property that $A$ is either the empty set or $\forall k \in A ( k \geq |A|)$. How can I prove that $a(n) = F(n+2)$ and show that ...
1
vote
1answer
85 views

Limit of a function not using Stirling's Approximation

I want to compute the following limit: $$\lim_{n\to\infty} \frac{\left(\frac{e}{F_{n+1}}\right)^{F_{n+1}} F_{n+1}!}{\left(\frac{e}{F_n}\right)^{F_n} F_n!},$$ where $F_n$ is the $n$th Fibonacci ...
1
vote
3answers
173 views

recurrence relation for squares of fibonacci numbers

I have a problem finding a proof that the squares of the Fibonacci numbers satisfy the recurrence relation $a_{n+3} - 2*a_{n+2} - 2*a_{n+1} + a_n = 0$ and solving this recurrence relation. Some help ...
0
votes
1answer
1k views

Induction on Fibonacci Sequence and the Golden Ratio

I'm trying to prove $f_n \leq \left(\frac{1 + \sqrt{5}}{2}\right)^{n-1}$ with induction, and I'm stuck in the induction step. Basis: n = 2 $f_{2} \leq \left(\frac{1 + \sqrt{5}}{2}\right)^{2-1} ...
1
vote
1answer
67 views

Proof Help dealing Lucas and Fibonacci Numbers

Claim: $L_n=F_{n-1}+F_{n+1}$ for all $n >0$ Could someone please help me prove this? My professor mentioned it in class, but didn't show us how to prove it. I am just curious. The $L$ stands for ...
4
votes
2answers
72 views

Fibonacci induction stuck in adding functions together

Using Fibonacci... I am Proving: $$f_3 + f_6 + \cdots + f_{3n} = \frac12(f_{3n+2}-1) $$ I did the assumption of $f_1$ which gave $\mathrm{LHS}=2=\mathrm{RHS}$. For the second part where it is $n+1$ ...
3
votes
1answer
462 views

Taylor series with Fibonacci coefficients

Let $\{a_n\}$ be the Fibonacci numbers given by $a_0=0,a_1=1,a_{n+2}=a_{n+1}+a_n$ for $n\geq 0$. Prove that $f(z)=a_0+a_1z+a_2z^2+\ldots$ is a rational function, and determine which rational ...
1
vote
1answer
90 views

Fibonacci sequences

I have the following: $$ f_3+f_6 + \dots+f_{3n} = \frac 12 (f_{3n+2}-1) $$ for $f_0=0$ and $f_1=1$ When I calculate $n\ge2$ and $f_n= f_{n-1}+f_{n-2}$, I get: LHS = 8 while RHS = 10. LHS $$f_6 ...
3
votes
1answer
1k views

Exponential lower bound for Fibonacci numbers

Can someone show me how to solve through induction, $F(N) \geq (3/2)^N$ for all $N\geq N_0$, where $F(n)$ is the Fibonacci function and $N_0$ is some positive integer. I know that $N_0$ should be ...
0
votes
1answer
137 views

Simplifying Sigma Notation

I am working on the proof on showing the ratio of two consecutive Fibonacci numbers converges to the golden ratio to explain to a student I am tutoring. I am getting to some confusion in a ...
3
votes
2answers
212 views

Fibonacci combinatorial identity

Can someone explain how to prove the following identity involving Fibonacci sequence $F_n$ $F_{2n} = {n \choose 0} F_0 + {n\choose 1} F_1 + ... {n\choose n} F_n$ ?