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

0
votes
0answers
11 views

Prove equality of Fibonacci sequence

Let $u(n)$ — the Fibonacci sequence. Prove that $$u(1)^3+...+u(n)^3=\frac{ 1 }{ 10 } \left[ u(3n+2)+(-1)^{n+1}6u(n-1)+5 \right].$$ I suppose we need prove that equality by iduction in $n$. ...
0
votes
2answers
25 views

proof by induction for golden ratio and fibonacci sequence

I have to prove the following equation by induction for $$x = \phi$$ I am stuck and I don't know how to proceed. This is the equation $$ \phi ^n = f_n\phi + f_{n-1} $$ where $f_n$ is the nth term ...
0
votes
0answers
23 views

Golden Ration Generalization [closed]

Please help me to solve this exercise. (Sorry for my English) Given a natural number $p$ split a segment into two lengths of $a$ and $b$ with a> b such that: $\frac{a+b}{a}=p\frac{b}{a-b}$ ...
0
votes
1answer
48 views

A Pell-type equation

Simple Pell equations often have solutions that can be found with little work given certain conditions. These are of the form $x_{n}^{2} - A y_{n}^{2} = \pm 1$. There are harder equations that involve ...
1
vote
2answers
31 views

Find $r$, given that $F_r= 2F_{101}+F_{100}$

Find $r$, given that $F_r= 2F_{101}+F_{100}$. We know that the recurrence relation for the Fibonacci sequence is $F_n= F_{n-1}+F_{n-2}$ and that $F_0 = F_1 = 1$, but how to proceed further?
3
votes
3answers
107 views

Identity on Fibonacci numbers: $F_{2n}^2=F_{2n+2}F_{2n-2}+1$?

Let $F_n$ be the Fibonacci Sequence ($F_1=F_2=1, F_{n+2}=F_{n+1}+F_{n}$). Prove that $F_{2n}^2=F_{2n+2}F_{2n-2}+1$. I've tried everything from induction to telescoping series but I haven't got close. ...
4
votes
0answers
46 views

Finding first n so nth fibonacci is c modulo p

This is a question I stumbled upon in an online programming contest archive. The problem statement is simple, given $c \equiv F(n)$ mod $P$ and $P$, where $P$ is a prime of form 5$k$ + 1 or 5$k$ - 1, ...
1
vote
2answers
31 views

Fibonacci numbers relation

I was wondering if there was a relation between a Fibonacci number and its position. Is there a function $f(n)$ such that $$f(n)=F_n$$ where $F_n$ is the nth Fibonacci number?
0
votes
1answer
80 views

Proving formulas with products of Fibonacci numbers

While digging through my old notes, I stumbled upon some formulas involving multiplication of Fibonacci numbers that I discovered about 7 years ago (being fascinated with Fibonacci numbers at the ...
0
votes
1answer
39 views

How to find a formula relating fibonacci sequence?

By shifting property of fibonacci numbers, $$F_{m+n} = F_m · F_{n+1} + F_{m-1} · F_n$$ where $F_k$ denotes the kth Fibonacci number . I want to extend it to some n numbers . So , how to find a ...
1
vote
2answers
38 views

Generating Functions with Fibonacci

a) Let \begin{align*} F_{\text{even}}(x) &= F_0x^0 + F_2x^2 + F_4x^4 + F_6x^6 + F_8x^8 + \cdots \\ &= x^2 + 3x^4 + 8x^6 + 21x^8 + \cdots \end{align*} be the generating function whose ...
3
votes
1answer
74 views

Multiple of $p$ in first $p+1$ Fibonacci Numbers

Defining $F_0 = F_1 = 1$ and $F_{n+1} = F_{n} + F_{n-1}$ for $n>0$ gives the Fibonacci sequence, and it is well-known that modulo $p$, one of the first $p+1$ terms is $0.$ In fact, more is known, ...
2
votes
0answers
136 views

What is wrong with my reasoning? (Irrational numbers / Fibonacci sequence) [closed]

I just noticed that: We define a procedure $\mathcal{I}:\mathbb{R}\rightarrow \mathbb{R}$ that output a real number. The probability to obtain an irrational or rational number via $\mathcal{I}$ is ...
3
votes
1answer
51 views

Dominos ($2 \times 1$ on $2 \times n$ and on $3 \times 2n$)

How many ways are there to tile dominos (with size $2 × 1$) on a grid of $2 × n$? How about on a grid of $3 × 2n$?
1
vote
2answers
47 views

Why does Cassini's identity imply consecutive Fibonacci's number are relatively prime?

From Knuth's The Art of Computer Programming, Volume 1 on page 81 he gives Cassini's identity $F_{n+1} F_{n-1} - F_n^2 = (-1)^n$. Relation(4) and follows by saying "Relation(4) shows that $F_n$ ...
6
votes
1answer
85 views

Even Fibonacci Numbers and $\sqrt{5}$

My question is simple, but a mystery to me. Skip to the last paragraph if you're not interested in the story of my exploration. EDIT: I seem to have misinterpreted a key detail regarding how the ...
13
votes
4answers
296 views

How to prove $ \sum_{k=0}^n \frac{(-1)^{n+k}{n+k\choose n-k}}{2k+1}=\frac{-2\cos\left(\frac{2(n-1)\pi}{3}\right)}{2n+1}$

How to prove $$\sum_{k=0}^n \binom{n+k}{n-k}\frac{(-1)^{n+k}}{2k+1}=-\frac{2}{2n+1}\,\cos\left(\frac{2(n-1)\pi}{3}\right)\;\text{?}$$ I have a proof by induction for it, but it isn't simple! I want ...
2
votes
1answer
26 views

Is this Bertrand's postulate-related statement valid?

Bertrand's postulate says: For every $n>1$ there is always at least one prime $p$ such that $n<p<2n$. Is the following statement: For every $n>3$ there is always at least one ...
44
votes
4answers
4k views

Eyebrow-raising pattern of number of primes between terms of the Fibonacci number sequence?

So, $$1,1,2,3,5,8,13,21...$$ Any connection to primes?...it appears not. However, in between the Fibonacci numbers are how much primes? Let's see: 1 and 1 ZERO 1 and 2 NADA 2 and 3 ZILCH 3 and 5 ZIP ...
1
vote
2answers
69 views

How to solve the difference equation $u_n = u_{n-1} + u_{n-2}+1$

Given that: $$ \begin{equation} u_n=\begin{cases} 1, & \text{if $0\leq n\leq1$}\\ u_{n-1} + u_{n-2}+1, & \text{if $n>1$} \end{cases} \end{equation} $$ How do you solve this ...
4
votes
1answer
37 views

How to determine the generating function?

So I have $$\overset{*}{F} = \overset{*}{F}_{n-1} + \overset{*}{F}_{n-2} + g(n)$$ where $\overset{*}{F}$ is NOT a Fibonacci number for $n \geq 2$. $g(n)$ is any function $g: \mathbb{N} \to ...
2
votes
0answers
37 views

Fibonacci-related infinite sum

Prove that $$\sum_{n=0}^\infty \frac{1}{F_{2n+1}}=\frac{\sqrt{5}}{4}\theta_2^2\bigg(\frac{3-\sqrt{5}}{2}\bigg)$$ and $$\sum_{n=0}^\infty \frac{1}{F_{2n+1}+F_{2k-1}}=\frac{(2k-1)\sqrt{5}}{2F_{2k-1}}$$ ...
4
votes
1answer
41 views

How many Fibonacci Numbers are in the sequence

I have $I_n = \{2^n + 1, 2^n + 2, 2^n + 3, \dots , 2^{n+1}\}$ and I am trying to prove using induction how many Fibonacci numbers are there. First, the length of $I_n$ is $|I_n| = 2^n$ then for $F_0 ...
0
votes
1answer
23 views

Proving $F_n \ge (\frac{1}{2}(1+\sqrt{5}))^{n-2}$ for $n \in \mathbb{N}_{>1}$ when $F_n$ is the nth Fibonacci number

Let $F_n$ be defined as the nth Fibonacci number. Prove that $F_n \ge (\frac{1}{2}(1+\sqrt{5}))^{n-2}$ with $n \in \mathbb{N}_{>1}$ My approach thus far was to use induction over $n$. ...
0
votes
3answers
43 views

Prove $F(n) < 2^n$ [closed]

Consider the Fibonacci function $\large{F(n)}$, which is defined such that $F(1) = 1, F(2) = 1$, and $F(n) = F(n−2)+F(n−1)$ for $n > 2$ I know that I should do it using mathematical induction but ...
1
vote
1answer
33 views

An equation to prove with terms of Fibonacci sequence

I would like to prove an equation but I have stuck. The equation that is to prove is the below: $f(n)^2 + (-1)^{n+1} = f(n+1)f(n-1) , n \ge 2$. I'm trying to do an inductive proof of this equation. ...
1
vote
0answers
34 views

Fibonacci Sequence (conceptual/mechanical)

I'm in Calc II and have my exam on series/sequences tomorrow. There will be an extra credit question related to Fibonacci and am trying to gather as much info on the sequence as possible. -If the ...
14
votes
6answers
248 views

show that $\frac{1}{F_{1}}+\frac{2}{F_{2}}+\cdots+\frac{n}{F_{n}}<13$

Let $F_{n}$ is Fibonacci number,ie.($F_{n}=F_{n-1}+F_{n-2},F_{1}=F_{2}=1$) show that $$\dfrac{1}{F_{1}}+\dfrac{2}{F_{2}}+\cdots+\dfrac{n}{F_{n}}<13$$ if we use Closed-form expression ...
1
vote
4answers
215 views

Proof the golden ratio with the limit of Fibonacci sequence [duplicate]

Let $F_n=F_{n-1}+F_{n-2}$ the Fibonacci numbers, and $\phi=\frac{1+\sqrt5}{2}$ The exercise asks me to prove that: $\lim\limits_{n \to \infty}\frac{F_{n+1}}{F_n}=\phi$. Sorry as can be proceed??
4
votes
2answers
65 views

Conjecture: only one even Fibonacci term divided by two gives a prime: $F(9) = 34 = 2 \times 17$

Every Fibonacci term $F(3n)$ is divisible by two $F(3) = 2$ $F(6) = 8$ $F(9) = 34$ $...$ After seeking Fibonacci tables factorization until $F(10000)$, for every term $\frac{F(3n)}{2}$, it ...
0
votes
2answers
26 views

How does one arrive at a certain expression for the Fibonacci Zeta function?

In this paper by L. Navas, it is described how one can obtain a analytic continuation of the Fibonacci Dirichlet series (though I'm not sure it's actually a Dirichlet Series). First, the following ...
1
vote
0answers
75 views

Proving that a Fibonacci number is divisible by integer a

I am working on a review problem and can't figure out how to go about getting to an answer. We are told to let $F_n$ be the $nth$ Fibonacci number (defined as $F_1=F_2=1,F_{n+1}=F_n+F_{n-1}$). Show ...
1
vote
2answers
29 views

if d divides n then prove that fibonacci of d divides fibonacci of n

prove that if $d$ divides $n$ then prove that fibonacci of $d$ divides fibonacci of $n$. i have tried to write $F(n)$ as a multiple of $F(d)$ using the fact that $n = ad$ for some natural $a$ but got ...
3
votes
1answer
61 views

Limit of A Fibonacci

Let $P(x)$ be an $n^{th}$ degree-polynomial which is defined below for some odd natural number $n$. And let us denote the set of roots of $P$ by $\{r_1,r_2,r_3,\dots, r_n \}$. $$\displaystyle P(x) = ...
2
votes
1answer
63 views

Covering a rectangle of size $n\times1$ with dominos

A rectangle of size $n\times1$ is given. (a) In how many ways the rectangle can be covered with dominoes of size $1\times1$ and $2\times1$? (b) In how many ways the rectangle can be covered with ...
4
votes
0answers
67 views

Show that for a given $s$ there are a finite number of Fibonacci number of form $n^2+s$

It is well known that the last Fibonacci number $F_k$ such that $\exists \ n \in \Bbb{N} : F_k = n^2$ is $144$. Thus there are only $4$ perfect squares among the Fibonacci sequence (assuming you ...
1
vote
4answers
67 views

Why the $GCD$ of any two consecutive fibonnaci numbers is $1$?

Note: I've noticed that this answer was given in another question, but I merely want to know if the way I'm using could also give me a proof. I did the following: $$F_n=F_{n-1}+F_{n-2} \\ ...
1
vote
0answers
56 views

What are the next few “tetranacci-like” pseudoprimes?

Starting with $n=0$: $k=2$ Given the roots $x_i$ of $x^2-x-1=0$. Then, we have the Lucas numbers, $$A_n = x_1^n+x_2^n = 2, 1, 3, 4, 7, 11, 18,\dots$$ The $n$ that divides $A_n-1$ are all the ...
1
vote
2answers
49 views

Prove that the sum of the first $n$ even terms of the Fibonacci sequence is given by $(F_{3n} + F_{3n + 3} - 2) / 4$ not using induction?

each even term in the Fibonacci sequence has a position index which is a multiple of 3, therefore the even term is $F_{3n}$: $F_{3 (0)} = 0$ $F_{3 (1)} = 2$ $F_{3 (2)} = 8$ $F_{3 (3)} = 34$ $F_{3 ...
1
vote
1answer
61 views

Show that exist $i>0$ such that the Fibonacci number $F_{i}$ is divisible by 2015

This is a problem that has haunted me for more than a month. Not all the time - but from time to time, and always on windy or rainy days, it suddenly reappears in my mind: Assume that the sequence ...
4
votes
2answers
48 views

Proving that $F_{kn}$ is a multiple of $F_n$ by induction on $n$ (Fibonacci numbers)

Question: I want to prove that $F_{kn}$ is a multiple of $F_n$. Approach: I have to deduce this result from the following results: $$F_{n+k} = F_{k}F_{n+1} + F_{k-1}F_{n}$$ I have shown the ...
0
votes
2answers
51 views

Sum of odd Fibonacci Numbers

Trying to prove that the sum of odd-index consecutive Fibonacci numbers is the next even-index Fibonacci number. I have a gap in my proof that I cannot figure out. I know that induction would be ...
0
votes
1answer
31 views

Prove or disprove this relation between one root of the quadratic and the cubic equation of a certain form, and linear recurrences.

It is well known that the n-anacci (higher degree Fibonacci, that is Tribonacci and so on) numbers can be computed in closed form from roots of polynomials in the way Eric Weisstein at Mathworld ...
0
votes
1answer
51 views

Discrete Mathematics Fibonacci Sequence

I am studying for the final exam in my Discrete Mathematics class and came upon the following problem on the study guide we were given. Given the following algorithm: If $n = 0$, then $f(n) = 0$ ...
0
votes
1answer
34 views

Why do I get the Fibonacci sequence when I start with 1 and keep using the + sign?

I played with this on a calculator and when I entered 1 and kept hitting the + button, I got the noticeable Fibonacci sequence! Can someone explain to me why this happens?
2
votes
2answers
52 views

Proving that for Fibonacci numbers $a_n \lt (\frac {1 + \sqrt 5} 2)^n$ for $n \ge 1$

I'd like to prove that for Fibonacci numbers $a_n \lt \left(\frac {1 + \sqrt 5} 2\right)^n$ for $n \ge 1$. I suppose it needs induction so, after verifying the trivial case $n=1$, the inductive step ...
2
votes
4answers
50 views

Finding growth bounds on Fibonacci Sequence

I've been working on this following problem: Find a constant $c< 1$ such that $F_n \leq 2^{cn}$ for all $n \geq 0$. I honestly have no idea where to begin on this. I've done plenty of proofs ...
0
votes
0answers
51 views

How to prove a claim about Fibonacci sequence

I have to prove that for any natural number $n$ there exists $i>0$ such that $n\mid F_i$, where $F_i$ is the $i$-th Fibonacci number.
0
votes
1answer
43 views

Generalized Fibonacci Sequence with Modular Arithmetic

Consider the following generalized Fibonacci sequence: Given $a$ and $b$ positive integers, and the known values $g_1, g_2, ...g_b$ where $g_k = g_k$ (mod $a$), then for ...
0
votes
0answers
35 views

Generalized Fibonacci Sequences G_{n+p}

I have been given the following generalized fibonacci sequences: For some positive integer $m,p$, $g_{n+p}=g_{n+p-1}+g_{n+p-2}+...+g_{n+1}+g_n (mod m)$ I have been given two problems: (1) For $m=2$ ...