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

Find a sequence

Find the function for the sequence $a_0 = 0, a_1 = 1$ and $a_{n}=a_{n+10}+a_n$ for all $n>0$.
2
votes
0answers
77 views

Can I use the equality $\phi^2=\phi+1$ without proving it?

I am looking at the following exercise: $$\text{ Show with induction,that the } i^{th} \text{ number Fibonacci satisfies the equality: } $$ $$F_i=\frac{\phi^i-\hat{\phi}^i}{\sqrt{5}}$$ where $\phi$ ...
2
votes
1answer
63 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: ...
1
vote
3answers
80 views

How to compute the nth number of a general Fibonacci sequence with matrix multiplication?

If we want to compute the nth Fibonacci number we just power the matrix $M = \left[\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right]$ $n$ times and we get $M =\left[ \begin{array}{cc} ...
2
votes
1answer
74 views

The number of partitions of $n$ and the $n$th Fibonacci number.

I'm very sorry if this is a duplicate in any way. There's a lot of material out there on connections between these sequences so it's a possibility . . . Let $P_n$ be the number of partitions of $n$ ...
-1
votes
1answer
62 views

Checking a formula works for many numbers [closed]

Hello StackExchange users. I have discovered a formula which works out any Fibonacci number using the formula to work out the value of any cell in Pascal's triangle. It uses the sigma notation which I ...
3
votes
1answer
117 views

Golden ratio, $n$-bonacci numbers, and radicals of the form $\sqrt[n]{\frac{1}{n-1}+\sqrt[n]{\frac{1}{n-1}+\sqrt[n]{\frac{1}{n-1}+\cdots}}}$

The following infinite nested radical $$\sqrt{1+\sqrt{1+\sqrt{1+\sqrt{1+\cdots}}}}$$ is known to converge to $\phi=\displaystyle\frac{\sqrt{5}+1}{2}$. It is also known that the similar infinite ...
13
votes
4answers
363 views

Converting recursive equations into matrices

How do we convert recursive equations into matrix forms? For instance, consider this recursive equation(Fibonacci Series): $$F_n = F_{n-1} + F_{n-2}$$ And it comes out to be that the following that ...
1
vote
1answer
69 views

Fibonacci numbers $F_{n+3} + F_{n} = 2F_{n+2}$

Prove $F_{n+3} + F_{n} = 2F_{n+2}$ for any positive integer n. So What I did was this: fn+ fn+1 = fn+2 fn + fn+1 = fn+2 => fn+2 -fn+1 fn+1 + fn+2 = fn+3 then I subsituted into equation in ...
2
votes
5answers
2k views

What is the summation notation for the Fibonacci numbers?

I learned about summation notation the other day, and I'm looking for a way to write the Fibonacci numbers with it. What would it look like?
2
votes
2answers
58 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 ...
1
vote
4answers
133 views

Fibonacci Calculation using a larger matrix

So the formula to generate the fibonacci sequence in matrix form is: $$ \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & ...
2
votes
2answers
92 views

How do I apply the $\pm4$ part of the equation $5F_n^2\pm~4=L_n^2$ without knowing $n$?

I'm trying to test a great many numbers $a^3+b^3$ to see if any of them are Fibonacci using the formula $$a^3+b^3=F_n \iff 5(a^3+b^3)^2\pm~4=L_n^2$$ I want to make my search more efficient by having ...
11
votes
5answers
1k views

How to tell if a Fibonacci number has an even or odd index

Given only $F_n$, that is the $n$th term of the Fibonacci sequence, how can you tell if $n \equiv 1 \mod 2$ or $n \equiv 0 \mod 2$? I know you can use the Pisano period, however if $n \equiv 1$ or ...
0
votes
1answer
42 views

Base case in the Binet formula (Proof by strong induction)

I don't understand why the author says that the inductive formula does not apply until $u_3$. The formula does not depend on other terms in the Fibonacci sequence, so I thought I could just prove it ...
1
vote
2answers
70 views

How to establish this inequality without using induction?

Given the Fibonacci sequence $a_1 = 1$, $a_2 = 2$, $\ldots$, $a_{n+1} = a_n + a_{n-1} $ for $n \geq 2$, how to derive, without using induction, the inequality $$ a_n < (\frac{1+\sqrt{5}}{2})^n $$ ...
1
vote
0answers
293 views

Calculating Pisano periods for any integer

I recently stumbled across this SPOJ question: http://www.spoj.com/problems/PISANO/ The question is simple. Calculate the Pisano period of a number. After I researched my way through the web, I found ...
5
votes
1answer
90 views

Number of zeros in Fibonacci sequences mod $p$

We know that Fibonacci sequences are periodic in mod $m$. For example, for $p\equiv \pm 1 \pmod 5$ and $\pm 2 \pmod 5$ the periods for Fibonacci sequences modulo $p$ divide $p-1$ and $2p+2$ ...
3
votes
1answer
88 views

Fibonacci series mod a number

I'm trying to write a program with an input of numbers $n$ and $k$ (where $n<10^{20}$ and $k<10^9$), where I compute fib[n] % k. What is a good FAST way of computing this? I have read many ...
1
vote
1answer
109 views

What is length of period of fibonacci number mod 1000033

Can some explain me how the period of Fibonacci mod $1000033$ is $4684$. As we know if $n$ mod $5$ is $2$ or $3$ then period is $2n + 2$ so the period should me $2\times1000033 + 2$ but why it is ...
-1
votes
1answer
153 views

Asymptotic value of Fibonacci numbers

It is well known that $F_n\sim\frac{\phi^n}{\sqrt{5}}$, where $\phi=\frac{1+\sqrt{5}}{2}$. Does someone know a better estimate? With proof please. I'm trying to calculate the following limit: Let ...
1
vote
5answers
180 views

A Non-recursive Fibonacci Sequence

How can I determine the general term of a Fibonacci Sequence? Is it possible for any one to calculate F2013 and large numbers like this? Is there a general formula for the nth term of the Fibonacci ...
0
votes
1answer
72 views

Let $u_n$ be the $n$-th entry in the Fibonacci sequence $1,1,2,3,5,8,13,\ldots$

If you start with $u_1 = 1$ and $u_2 = 1$, then the sequence can be generated using the formula $$u_{n+1} = u_n + u_{n-1}\ .$$ If $u_n = r^n$, what is r? Can anyone figure this out? I am so stuck ...
4
votes
2answers
118 views

The sum of $n$ consecutive Fibonacci numbers.

The sum of $8$ consecutive Fibonacci numbers is divisible by $3$. How can I generalize this for the sum of $n$ consecutive Fibonacci numbers? For example, $$1+1+2+3+5+8+13+21=54=3\times 18 \\ ...
1
vote
1answer
61 views

Proof that golden angle successively divides the largest gap by the golden ratio?

The golden angle divides the circumference of a circle by the golden ratio. "If radial spokes are placed successively into the circle, each spaced by a golden angle increment, then each additional ...
28
votes
4answers
555 views
1
vote
4answers
88 views

Determine which Fibonacci numbers are even

(a) Determine which Fibonacci numbers are even. Use a form of mathematical induction to prove your conjecture. (b) Determine which Fibonacci numbers are divisible by 3. Use a form of mathematical ...
1
vote
4answers
47 views

Help understanding Recursive algorithm question

We have a function that is defined recursively by $f(0)=f_0$, $f(1)=f_1$ and $f(n+2) = f(n)+f(n+1)$ for $n\geq0$ For $n\geq0$, let $c(n)$ be the total number of additions for calculating $f(n)$ ...
2
votes
1answer
54 views

What's the Lucas version of the Möbius test for Fibonacci numbers?

I recently came across the following, attributed to Möbius: $$(a\in\mathbb N)=F_n\iff\left[\varphi a-\tfrac{1}{a},\varphi a+\tfrac{1}{a}\right]\ni(b\in\mathbb N)$$ It is the lesser-known test used to ...
1
vote
1answer
34 views

What is the Lucas counterpart to the Fibonacci identity $5F_n^2\pm~4=\lambda^2$?

It's a well-known rule that a number $x$ belongs to the Fibonnaci Sequence iff: $$\begin{align}5x^2\pm~4&=\lambda^2&\lambda\in\mathbb Z\end{align}$$ In other words, if and only if $5x^2\pm~4$ ...
1
vote
1answer
44 views

Looking for a sum 1/(Fib(n)*Fib(n+2))

I am looking for the sum of the series: $$\sum_{n=1}^{\infty}\frac{1}{F_{n}F_{n+2}},$$ where $F_{n}$ is the $n$-th Fibonacci number. I was thinking about splitting the fraction into 2 like in the ...
1
vote
2answers
58 views

Compute $F_{1000} \bmod F_{11}$, where $F_n$ denote the Fibonacci numbers

Compute $F_{1000} \bmod F_{11}$, where $F_n$ denote the Fibonacci numbers. Progress: $F_{11}=89$ . I believe you should find the period of $F_n \bmod 89$ and use that to solve it. But I'm not not ...
9
votes
2answers
812 views

Find all integer solutions for the equation $|5x^2 - y^2| = 4$

In a paper that I wrote as an undergraduate student, I conjectured that the only integer solutions to the equation $$|5x^2 - y^2| = 4$$ occur when $x$ is a Fibonacci number and $y$ is a Lucas number. ...
0
votes
1answer
34 views

finding $n$ consecutive composite Fibonacci numbers.

For each $n$, How can we find $n$ consecutive composite Fibonacci numbers?
2
votes
3answers
96 views

Is it true that $5^k \mid f(5^k)$?

I guess if it is true that $5^k \mid f(5^k)$, where $f(n)$ denotes the $n$-th Fibonacci's number. I have tried to prove it by induction on $k$, but nothing. Have you got any ideas?
2
votes
1answer
32 views

Is a Lucas Number with either a power of 2 or a prime index always coprime with all previous Lucas Numbers?

I was looking at this webpage which lists the first 200 Lucas Numbers color-coded with their prime factors and I noticed that all the Lucas numbers with power of two or prime indexes were relatively ...
1
vote
1answer
70 views

Compute $F_{1000} \bmod 1001$, where $F_n$ denote the Fibonacci numbers

Compute $F_{1000} \bmod 1001$, where $F_n$ denote the Fibonacci numbers. I have tried using the fact that $F_{n^k} \bmod F_n = 0, k=1,2,3,...$ but that doesn't get me anywhere. Thanks!
3
votes
0answers
51 views

Are $1$ and $3$ the only numbers of the form $2^n-1$ that exist in the Fibonacci sequence? [duplicate]

Are $1$ and $3$ the only numbers of the form $2^n-1$ that exist in the Fibonacci sequence? Then, if they are not the only ones, are there infinite cases? I have tried finding another example using a ...
0
votes
1answer
48 views

Function relating Euler's constant and the golden ratio

Okay, I was messing around on Excel with some coefficients and I stumbled onto this. Not sure if it converges but it gets pretty damn close around the 1024th term mark. Was wondering if somebody could ...
0
votes
1answer
38 views

Help with a proof involving Fibonacci numbers.

I'm working through SICP MIT course, and I'm a little lost on how to prove the following statement. I think I'm able to demonstrate it, but have no idea how to prove this statement. I may ...
0
votes
2answers
87 views

Non integer Fibonacci numbers

I'm pretty sure we're all familiar with the Fibonacci sequence. Most people with more than passing knowledge of this most marvelous gem are aware of the Binet formula, $Fib(n) = (\varphi^n - ...
7
votes
2answers
248 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 ...
1
vote
2answers
95 views

How many $a$-nary sequences of length $b$ never have $c$ consecutive occurrences of a digit?

Let $S(a,b,c): = \#\{a$-nary sequences of length $b$ without $c$ consecutive occurrences of a digit$\}$. For example, $S(2,n,3)$ would be the number of binary sequences of length $n$ without $3$ ...
-3
votes
2answers
808 views

Expressing Fibonacci numbers as the sum of squares.

As we know that by observation, the Fibonacci numbers ($F_0=0$, $F_1=1$, $F_{n}=F_{n-1}+F_{n-2}$) have the identity $$F_{2k+1}=F_k^2 + F_{k+1}^2.$$ In particular, if $n$ is odd, then $F_n$ is a sum of ...
2
votes
2answers
80 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$ ?
8
votes
3answers
127 views

Asking About Binomial Sum Related to Fibonacci

How would I prove $$ \sum\limits_{i,j\ge 0} {n-i \choose j} {n-j \choose i}=F_{2n+1} $$ where $n$ is a nonnegative integer and $\{F_n\}_{n\ge 0}$ is a sequence of Fibonacci numbers? Thank you very ...
1
vote
1answer
53 views

Does this mean some Wall-Sun-Sun primes have already been found?

In the PrimeGrid project statistics page for Wall-Sun-Sun Prime Search, it says, Wall-Sun-Suns ... 2 Near Wall-Sun-Suns ... 208 However, all the internet search ...
2
votes
0answers
43 views

Fibonacci applied to human population living to dead ratio problem

If this forum is not the right one for my question, please redirect it. I do not know where to ask it. The question might seem tongue-in-cheek, believe me it's not! Last week to occupy my mind, I ...
1
vote
2answers
57 views

Help with a proof I can't quite

Let $(F_j)^\infty_{j=1}$ be the sequence of Fibonacci numbers. For all $n \in \mathbb{N}$, $\sum\limits_{k=1}^{2n-1}F_kF_{k+1}=(F_{2n})^2$. I handled the base case quite well but couldn't go very ...
3
votes
1answer
117 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?