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
34 views

Weird informatic problem with Fibonacci numbers in which I have some troubles

I don't know what happended to this website but for months I am not able to connect me in it. As I understand it the website is closed. It is in this website I found this problem. Let $L$ be ...
0
votes
1answer
44 views

Proof a formula of the Fibonacci sequence with induction

It turns out that the Fibonacci sequence satisfies the following explicit formula: For all integers $F_{n} ≥ 0$, $F_{n} = \frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^{n+1} - ...
8
votes
2answers
844 views

Sum of inverse of Fibonacci numbers

If $F(n)$ is the nth Fibonacci number, How can I prove that: $$\sum_{i=1}^{\infty} \frac{1}{F(i)}\approx 3.36\, .$$
0
votes
1answer
27 views

Use partial fractions to write $\frac{1}{x^2 + x – 1}$ as $\frac{A_1}{x – α_1} + \frac{A_2}{x – α_2}$ and write it as a power series

Find the roots $α_1$, $α_2$ of $x^2 + x – 1$ and use partial fractions to write $\frac{1}{x^2 + x – 1}$ as $\frac{A_1}{x – α_1} + \frac{A_2}{x – α_2}$ , for suitable $A_1, A_2$. Using the power series ...
0
votes
2answers
38 views

Prove that $\frac{a_{n+1}}{a_n}<2$ for every n>1 using induction

Fibonacci sequence of $a_n$: Prove that $\frac{a_{n+1}}{a_n}\leq2$ for every $n\geq1$. I was able to prove this using the base case: $$n=1 | n=2$$ ...
4
votes
1answer
56 views

Can $F_n^2-F_m^2$ be factored as a product of Fibonacci or Lucas numbers when $n-m$ is odd?

The Fibonacci and Lucas numbers are defined for all integers $n$ by the recurrence relations $$F_n=F_{n-1}+F_{n-2}\text{ where }F_1=1\text{ and }F_2=1,$$ $$L_n=L_{n-1}+L_{n-2}\text{ where }L_1=1\text{ ...
0
votes
2answers
46 views

Prove that $F_nF_{n+1}=\frac{1}{4}(F_{n+2}^2-F_{n-1}^2)$

The Fibonacci and Lucasnumbers are defined for all integers $n$ by the recurrence relations $$F_n=F_{n-1}+F_{n-2}\text{ where }F_1=1\text{ and }F_2=1,$$ $$L_n=L_{n-1}+L_{n-2}\text{ where }L_1=1\text{ ...
0
votes
2answers
47 views

Variations on Fibonacci Sequence

Do mathematicians use variations on the Fibonacci sequence? I'm thinking specifically about something like this: Start with three $1s$ and for each consecutive number, add the three previous number ...
1
vote
1answer
20 views

Is $\sum_{n,m \geq 0} F_n^m x^n y^m$ a rational generating function?

I am curious if the generating function defined by: $$ F(x,y)=\sum_{n=0}^{\infty} \sum_{m=0}^{\infty} F_{n}^m x^n y^m$$ where $F_n$ is the $n$th fibonacci number, is a rational function. That is, Is ...
1
vote
2answers
28 views

General solution expressed in $a_0$ and $a_1$ of a Fibonacci-like sequence?

What is the general solution expressed in $a_0$ and $a_1$ of a Fibonacci-like sequence ? I mean if $a_0,a_1$ are given and $a_{n+1}:=a_n+a_{n-1}$ ...
4
votes
1answer
62 views

Proof Fibonacci derivation

I was wondering how to prove that $$f(n+m+2) = f(n+1)f(m+1) + f(n)f(m)$$ where $f$ is the fibonacci sequence and n, m are positive integers. Can be this done with induction? I'm lost with this ...
2
votes
0answers
23 views

fibonacci recurrence problem. [duplicate]

The Fibonacci numbers Fn are defined by the recurrence Fn=Fn−1+Fn−2, with base cases F0=0 and F1=1. Prove that any non-negative integer can be written as the sum of distinct and non-consecutive ...
0
votes
1answer
28 views

Fibonacci n-step numbers

I have searched the web for a definition and I found that this are typically defined as $F^n_{m} = F^n_{m-1} + F^n_{m-2} + \dots + F^n_{m-n}$ where $n$ stands for the number of previous numbers who ...
0
votes
1answer
37 views

Reference request for a divisibility property of Fibonacci numbers

Define the Fibonacci numbers $F_n$ by $F_n=F_{n-1}+F_{n-2}$ and initial values $F_0=0$ and $F_1=1.$ I would like to get a reference for the following result: If $p$ is a prime number with $p \equiv ...
8
votes
2answers
108 views

Why do ratios of these Fibonacci-type sequences approach $\pi$?

Define $A_n$ by $A_1=12$, $A_2=18$, and $A_n=A_{n-1}+A_{n-2}$ for $n\ge3$. Similarly define $B_n$ by $B_1=5$, $B_2=5$, and $B_n=B_{n-1}+B_{n-2}$ for $n\ge3$. Terms of $A_n$: $12, 18, 30, 48, ...
2
votes
2answers
62 views

Prove that for all $n \geq 1$, $F_{-n}$ = $(-1)^{n+1}F_n$ where F is the Fibonacci numbers.

Prove that for all $n \geq 1$, $F_{-n}$ = $(-1)^{n+1}F_n$ where F is the Fibonacci numbers. I've already shown that the formula holds for $n = 1$ and $n = 2$. So I supposed the formula holds for $n$ ...
0
votes
1answer
36 views

Sum of digits of Fibonacci number a perfect square

During my problem solving with Fibonacci numbers following thought crossed my mind. How many Fibonacci numbers are there such that sum of its digits is a perfect square? Here is a list of ...
0
votes
1answer
54 views

Find a generating function with Fibonacci

$$G(x) = \sum_{n=1}^\infty na_n x^n $$ Hello. I need to find a generating function for the summation above, where $a_n$ is the Fibonacci sequence. I have found the generating function for the ...
1
vote
4answers
64 views

Basic Discrete Mathematics Recurrence question

Good afternoon, I've been assigned the following problem from my Intro to Discrete Mathematics: Show that $\sum_{i=1}^n$ F(i) = F(n+2) - 1 note: F(n) is the nth term in the fibonacci sequence. ...
0
votes
1answer
106 views

Greatest Common Divisor with Fibonacci Numbers [duplicate]

Prove that for all integers $n\geq 0$: $$\gcd(F_{n+1},F_n)=1$$ I am extremely lost. Please can some provide some hint or direction? Thank you so very much
-2
votes
4answers
44 views

Fibonacci Numbers Induction?

Show that $a_n=n^2+n+1$ satisfies \begin{cases} a_0=1\\ a_k=a_{k-1}+2k & \text{for $k>0$} \end{cases} I want to use induction to solve this problem. but I don't know what my base will be ...
0
votes
1answer
52 views

Fibonacci-like formula for Padovan sequence

For the Fibonacci sequence, one can show the following and easy to calculate equation : $$\forall n\in \mathbb Z,~\mathcal F_n=\mathcal F_{\lfloor\frac{n}{2}\rfloor+1}^2-(-1)^n\mathcal ...
0
votes
1answer
53 views

Prove fibonacci with matrixes [duplicate]

I have a question which i could not figure out the answer to, it was the hardest of them all that i got and i couldnt figure it out, its a proof of fibonaccis serie using matrixes and i need som help ...
2
votes
3answers
57 views

Proof with Fibonacci Sequence

I was working on my homework assignment for one of my classes and I have come across a proof question that my classmates and I are finding difficult to answer. The problem is asking us to prove that ...
1
vote
1answer
34 views

How to show this Fibonacci identity? $f_{3n}=f^3_{n+1} + f^3_n - f^3_{n-1}$

I already know that $f_{n+m}=f_{n-1}f_m + f_nf_{m+1}$. By letting $m=n$ it immediately follows that $f_{2n}=f_{n}(f_{n+1} + f_{n-1})$ and from that we get $f_{2n}=f^2_{n+1} - f^2_{n-1}$. From this ...
4
votes
1answer
257 views

Fibonacci sequence in the factorization of certain polynomials having a root at the Golden Ratio

I was playing around with the Golden Ratio $\Phi = \frac{1 + \sqrt 5}{2}$ on Wolfram Alpha and I noticed that if $F_n$ denotes the $n{th}$ Fibonacci number, then the polynomial $P_n(x) = x^n - F_n x - ...
1
vote
0answers
27 views

How to make inductive step for a Fibonacci proof [duplicate]

I have to prove $F^2_{n−1} = F^2_n + F^2_{n−1}$ for any $n >=1$ by induction (for the Fibonacci sequence). For the basis step, I have: $n = 1; $ $F_{(1)-1} = F^2_{(1)} + F^2_{(1)-1} ->$ $ ...
0
votes
2answers
72 views

Let $F_n$ denote the nth Fibonacci number and prove that the following re true for every possible integer $n$

$$\sum_{i = 1}^n F_{i}^2 = F_n F_{n+1}$$ -I solved a similar Fibonacci sequence that was the following: $$\sum_{i = 1}^n F_i = F_{n + 2} - 1$$ But, I am having trouble with this one, any help is ...
2
votes
0answers
25 views

Prove that $\sum^{n}_{i=0}\binom{n}{i}F_{i}=F_{2n}$ [duplicate]

I am asked: Let $F_{i}$ denote the $i$-th Fibonacci number. Prove that $$\sum^{n}_{i=0}\binom{n}{i}F_{i}=F_{2n}$$ I have the base case and the inductive hypothesis, but I'm not sure what ...
12
votes
1answer
346 views

How to prove this series about Fibonacci number: $\sum_{n=1}^{\infty }\frac{F_{n}}{2^{n}}=2$? [duplicate]

How to prove this series: I have no idea where to start. $$\sum_{n=1}^{\infty }\frac{F_{n}}{2^{n}}=2$$ where $F_{1}=1,~F_{2}=1,~F_n=F_{n-1}+F_{n-2},~~n\geq 3$.
3
votes
0answers
58 views

Fibonacci numbers properties

I've verified that $F_{41} \mod F_{32}= F_{23}$ where $41-32=9$ and $32-9=23$. I suppose these facts are correlated. Is there a simple way to show how? Simpler question: how can I justify that ...
1
vote
0answers
53 views

Help me find the mistake in my solution of the limit

Let $x_1=1, x_2=2,$ $$x_n=x_{n-1}+x_{n-2}, (n>2)$$ The task is to find: $$\lim \limits_{x\to\infty}\frac{x_{n+1}}{x_n}!$$ My attempt at solution: We write the recursive formula as: ...
4
votes
1answer
25 views

First Fibonacci Number with Given Remainder

I wonder is there more effective algorithm than brute-force-search to find the first Fibonacci number with given remainder $~~r~~$ modulo given integer $~~m~~$. $$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
3
votes
3answers
92 views

Induction Proof for $F_{2n} = F^2_{n+1} - F^2_{n-1}$

As stated in the tag, I'm trying to prove by induction the claim $F_{2n} = F^2_{n+1} - F^2_{n-1}$, where $F_{n}$ is the $n^{th}$ Fibonacci number. I've spent hours on the inductive step without ...
0
votes
2answers
193 views

Rate of Convergence vs Radius of Convergence

What is the difference between finding the 'rate of convergence' and the radius of convergence'? The question I am trying to solve here is to find the rate of convergence of the ratio of Fibonacci ...
2
votes
1answer
68 views

On $4n+1 = x^2, 5n+1 = y^2$ and the Fibonacci numbers

While answering this question, I decided to look at the particular case, $$4n+1 = x^2\\5n+1 = y^2$$ to be solved simultaneously. The solutions for $n,x,y$ are A157459, A007805, and A049629, ...
1
vote
0answers
44 views

Does 1/4 eventually repeat in Fibonacci coding?

In a regular, positional number system (like our decimal numbers), every rational number ends in a repeating sequence (even if it's just 0). For example, 1/3 in base 10 is 0.33333..., in base 5 it's ...
12
votes
0answers
121 views

Do all rational numbers repeat in Fibonacci coding?

In a regular, positional number system (like our decimal numbers), every rational number ends in a repeating sequence (even if it's just 0). For example, 1/3 in base 10 is 0.33333..., in base 5 it's ...
0
votes
1answer
47 views

Need help calculating probability…

First time here, so I hope you'll not get too frustrated if I make any etiquette mistakes for this forum. So here's my question. I know there are snow day calculators out there, but I'm trying to ...
1
vote
0answers
25 views

Find length of sequence with fibonacci principle

Let assume we have sequence: $${l_{n + 1}} = {l_n} + {l_{n - 1}} $$ $$\begin{array}{l}{l_0} = 0\\{l_1} = 01\\{l_2} = 010\end{array}$$ Our goal to get $|{l_n}|$ (length). For ${l_0}$ it's 0, for ...
1
vote
2answers
42 views

Proof and geometrical significance of $F(n+1)^2-F(n) \cdot F(n+2)$?

My son notes that for Fibonacci numbers $F_n$, $$ (F_{n+1})^2-F_n \cdot F_{n+2} =(-1)^n $$ I assume that this is true. Update: I see that the proof is already here: Prove the given property of the ...
0
votes
0answers
41 views

Is the following statement true: $F_n\leq p\leq F_{n+2}$

Let be $n\in\{2,3,\ldots\}$ Is the following statement true: There exists a prime number so that $F_n\leq p\leq F_{n+2}$ while $F_n$ is a Fibonacci number.
4
votes
1answer
62 views

Fibonacci sequence digits

We define the Fibonacci sequence by $F_{n+2}=F_{n+1}+F_{n}$, with $F_0=0$ and $F_1=1$. How to compute the last $30$ digits of $F_{2^{200}}$ for instance? can we use Python?how?
2
votes
0answers
77 views

Fibonacci Numbers and the Harmonic Series

$$\sum_{k=1}^{n} \frac{1}{k}=H_n=\frac{p_n}{q_n}$$ Where $p_n,q_n$ are coprime intergers. The first few values for $p_n+q_n$ are $2,5,7,37,197,69,504,1041,9649$. When are $p_n+q_n$ Fibonacci ...
4
votes
1answer
104 views

Some heuristics about the Pisano Period, primes and Fibonacci primes. What reasons are behind them?

I started to read about the Pisano Period, $\pi(n)$, applied to the classic Fibonacci sequence and made some simple tests looking for possible properties of the sequence. I have observed the following ...
0
votes
1answer
31 views

Is there some function which return probability to select prime number from $n$ first Fibonacci numbers.

So my question is: is there function return probability to select prime number from $n$ first Fibonacci numbers. So maybe it realize with $\pi(n)$ function?
1
vote
2answers
91 views

Domino tiling extended in N dimensions.

The standard domino tiling problem, is the number of ways to tile a board of size 2xn by dominos of size 2x1. The answer directly follows a recursion, the same as the Fibonacci series. If I extend ...
1
vote
1answer
36 views

How is this identity for Fibonacci numbers called?

In the course of proving another identity, I've found that $$F_n \equiv F_kF_{n-k+1} + F_{k-1}F_{n-k}$$ …for all corresponding n and ...
11
votes
0answers
313 views

Are all totient values of Fibonacci Numbers distinct?

This question was inspired while I was seeing how certain recurrence relations would behave when I applied Multiplative Functions. Let $F_{n}$ be a sequence for which $F_{1}=1,F_{2}=1$, and ...