# Math Help - Fibonacci's sequence

1. ## Fibonacci's sequence

Two consecutive Fibonacci numbers are relatively prime

This is my proof - am i correct?

Let Fn and Fn+1 be any two consecutive Fibonacci numbers and suppose there is an integer d > 1 such that d divides Fn and d divides Fn+1.

Then Fn+1 - Fn = Fn-1 will also be divisible by d (if d divides a and d divides b, then a = d*m and b = d*n for some integers m and n. Then a - b = d*m - d*n = d * (m-n), so d divides (a - b) as well). But now notice that Fn - Fn-1 = Fn-2 will also be divisible by d.

We can continue this way showing that Fn-3, Fn-4, ... , and finally F1 = 1 are all divisible by d. Certainly F1 is not divisible by d > 1. Thus we have a contradiction that invalidates the assumption. Thus it must be the case that Fn and Fn+1 are relatively prime.

Has anyone know of any other properties of the Fibonacci’s Sequence?? please

2. Originally Posted by Natasha1
Two consecutive Fibonacci numbers are relatively prime

This is my proof - am i correct?

Let Fn and Fn+1 be any two consecutive Fibonacci numbers and suppose there is an integer d > 1 such that d divides Fn and d divides Fn+1.

Then Fn+1 - Fn = Fn-1 will also be divisible by d (if d divides a and d divides b, then a = d*m and b = d*n for some integers m and n. Then a - b = d*m - d*n = d * (m-n), so d divides (a - b) as well). But now notice that Fn - Fn-1 = Fn-2 will also be divisible by d.

We can continue this way showing that Fn-3, Fn-4, ... , and finally F1 = 1 are all divisible by d. Certainly F1 is not divisible by d > 1. Thus we have a contradiction that invalidates the assumption. Thus it must be the case that Fn and Fn+1 are relatively prime.

Has anyone know of any other properties of the Fibonacci’s Sequence?? please
Do you know countinued fraction? There is an easy proof from there.

3. I don't no sorry.

4. You can write your proof formally as an inductive one. Let H(n) be the assertion that the Fibonacci numbers F_n and F_{n-1} are coprime. Then H(1) is true, since F_1=1 and F_0=0 have no common factor greater than 1. Now suppose H(n) is true, that is, F_n and F_{n-1} are coprime. Then, as you correctly say, any common factor between F_{n+1} and F_n would also be a common factor between F_n and F_{n-1}. But H(n) says that must be 1. So we have H(n) implies H(n+1). Hence by induction H(n) is true for all n.

In a recent thread it was shown that (F_n * F_{n+2}) - (F_{n+1})^2 = (-1)^{n+1}. This implies that F_n and F_{n+1} are coprime since any common factor would divide the LHS and so divide the RHS which is +- 1.

5. Originally Posted by Natasha1
Has anyone know of any other properties of the Fibonacci’s Sequence?? please
• Take any three adjacent numbers in the sequence, square the middle number, multiply the first and third numbers. The difference between these two results is always 1.
• Take any four adjacent numbers in the sequence. Multiply the outside ones. Multiply the inside ones. The first product will be either one more or one less than the second.
• The sum of any ten adjacent numbers equals 11 times the seventh one of the ten. Mesoamericans thought the numbers 7 and 11 were special.

6. Hello, Natasha!

Here's a fascinating bit of Fibonacci trivia . . .

. . . $\sum^{\infty}_{k=1}\frac{F_k}{10^{k+1}}\,=\,\frac{ 1}{89}$

That is: $\frac{1}{10^2} + \frac{1}{10^3} + \frac{2}{10^4} + \frac{3}{10^5} + \frac{5}{10^6} + \frac{8}{10^7} + \frac{13}{10^8} + \frac{21}{10^9} + \hdots \:=\:\frac{1}{89}$

In other words:

$0.01$
$0.001$
$0.0002$
$0.00003$
$0.000005$
$0.0000008$
$0.00000013$
$0.000000021$
. . . . $\vdots$
$\_ \_ \_ \_ \_ \_ \_ \_ \_ \_ \_ \_ \_ \_$
$0.01123595...\;=\;\frac{1}{89}$

And $89$ happens to be the $11^{th}$ Fibonacci number.

Why? .Who knows? .Math is filled with little "jokes" like that.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Here's another joke . . .

Did you ever notice that:

. . . . $3^2 + 4^2\;=\;5^2$
. . $3^3 + 4^3 + 5^3\;=\;6^3$

Hey, have we stumbled onto an important pattern?

. . No . . . those two cases are just concidences.

7. Originally Posted by Soroban
Hello, Natasha!

Here's a fascinating bit of Fibonacci trivia . . .

. . . $\sum^{\infty}_{k=1}\frac{F_k}{10^{k+1}}\,=\,\frac{ 1}{89}$

That is: $\frac{1}{10^2} + \frac{1}{10^3} + \frac{2}{10^4} + \frac{3}{10^5} + \frac{5}{10^6} + \frac{8}{10^7} + \frac{13}{10^8} + \frac{21}{10^9} + \hdots \:=\:\frac{1}{89}$

In other words:

$0.01$
$0.001$
$0.0002$
$0.00003$
$0.000005$
$0.0000008$
$0.00000013$
$0.000000021$
. . . . $\vdots$
$\_ \_ \_ \_ \_ \_ \_ \_ \_ \_ \_ \_ \_ \_$
$0.01123595...\;=\;\frac{1}{89}$

And $89$ happens to be the $11^{th}$ Fibonacci number.

Why? .Who knows? .Math is filled with little "jokes" like that.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Is there any proof of this trivia?

8. Hello, malaygoel!

Is there any proof of this trivia?

We want to evaluate: .[1] . $S\;=\;\frac{F_1}{10^2} + \frac{F_2}{10^3} + \frac{F_3}{10^4} + \frac{F_4}{10^5} + \frac{F_5}{10^6} + \hdots$

Multiply by 10: .[2] . $10S\;=\;\frac{F_1}{10} + \frac{F_2}{10^2} + \frac{F_3}{10^3} + \frac{F_4}{10^4} + \frac{F_5}{10^5} + \hdots$

Add [1] and [2]: . $11S\;=\;\frac{F_1}{10} + \frac{F_1+F_2}{10^2} + \frac{F_2+F_3}{10^3} + \frac{F_3+F_4}{10^4} + \frac{F_4+F_5}{10^5} + \hdots$

. . which gives us: .[3] . $11S\;=\;\frac{F_1}{10} + \underbrace{\frac{F_3}{10^2} + \frac{F_4}{10^3} + \frac{F_5}{10^4} + \frac{F_6}{10^5} + \hdots}$

Examine that last portion . . .

We have: . $100\left(\underbrace{\frac{F_3}{10^4} + \frac{F_4}{10^5} + \frac{F_5}{10^6} + \frac{F_6}{10^7} +\hdots}\right)$
. . . . . and this is $S$ minus the first two terms: . $S - \frac{F_1}{10^2} + \frac{F_2}{10^3}$

Hence, [3] becomes: . $11S\;=\;\frac{F_1}{10} + 100\left(S - \frac{F_1}{10^2} - \frac{F_2}{10^3}\right) \;= \;\frac{F_1}{10} + 100S - F_1 - \frac{F_2}{10}$

This simplifies to: . $89S\;=\;\frac{9}{10}F_1 + \frac{1}{10}F_2$

Since $F_1 = F_2 = 1$, we have: . $89S\;=\;\frac{9}{10}(1) + \frac{1}{10}(1) \;=\;1$

Therefore: . $S\;=\;\frac{1}{89}$ . . . ta-DAA!

9. Here are some facts.

1)The divine proportion is called "the most irrational number" meaning it is the most difficult to approximate with rationals (you need countinued fractions to prove this).

2)Let $d=\gcd(a,b)$ then $\gcd(F(a),F(b))=F(d)$ (another proof to your original problem because two consectutive number are coprime).

3)Every number is expressable as a sum of distinct fibonacci number non of which are adjacent.

Here's an algebraic proof of: $\lim_{n\to\infty}\frac{F_{n+1}}{F_n}\:=\:\phi$

You must be familiar with the Binet function for Fibonacci numbers:
. . . $[1]\;\;F_n\;=\;\frac{(1 + \sqrt{5})^n - (1 - \sqrt{5})^n}{2^n\sqrt{5}}$

and you must know that: $[2]\text{ If }|r| < 1\text{, then }\lim_{n\to\infty} r^n\: = \;0$

We have the ratio: $\displaystyle{R\;=\;\frac{F_{n+1}}{F_n}\;=$ $\frac{(1+\sqrt{5})^{n+1} - (1 - \sqrt{5})^{n+1}}{2^{n+1}\sqrt{5}}$ $\cdot\,\frac{2^n\sqrt{5}}{(1+\sqrt{5})^n - (1 - \sqrt{5})^n} }$

. . which simplifies to: $R\;=\;\frac{1}{2}\cdot\frac{(1+\sqrt{5})^{n+1} - (1-\sqrt{5})^{n+1}}{(1+\sqrt{5})^n - (1-\sqrt{5})^n}$

Divide top and bottom by $(1+\sqrt{5})^n:$

. . $R\;=\;\frac{1}{2}\cdot\frac{(1 + \sqrt{5}) - \frac{(1-\sqrt{5})^{n+1}}{(1+\sqrt{5})^n} }{1 - \frac{(1-\sqrt{5})^n}{(1+\sqrt{5})^n}} \;=\;\frac{1}{2}$ $\cdot\frac{(1 + \sqrt{5}) - (1-\sqrt{5})\left(\frac{1-\sqrt{5}}{1+\sqrt{5}}\right)^n}{1 - \left(\frac{1-\sqrt{5}}{1+\sqrt{5}}\right)^n}$

Note that: $\left|\frac{1-\sqrt{5}}{1+\sqrt{5}}\right| < 1.$ . Let $r = \frac{1-\sqrt{5}}{1+\sqrt{5}}$

. . Then we have: $R\;=\;\frac{(1 + \sqrt{5}) - (1-\sqrt{5})r^n}{1 - r^n}$

Hence: $\lim_{n\to\infty}R\;=$ $\;\lim_{n\to\infty}\frac{1}{2}\cdot\frac{(1 + \sqrt{5}) - (1 - \sqrt{5})r^n}{1 - r^n} \;=\;\frac{1}{2}\cdot\frac{(1 + \sqrt{5}) - (1 - \sqrt{5})\cdot0}{1 - 0}$

Therefore: $\lim_{n\to\infty}\frac{F_{n+1}}{F_n}\;=\;\frac{1 + \sqrt{5}}{2}\;=\;\phi$

11. Originally Posted by ThePerfectHacker
Here are some facts.

3)Every number is expressable as a sum of distinct fibonacci number non of which are adjacent.
What is the proof?

12. Originally Posted by malaygoel
What is the proof?
Using induction for $n>2$.
----
Each of the integers $1,2,3,...,F(k)-1$ is a sum of numbers from the set $S=\{ F(1),F(2),...,F(k-2) \}$ none of which are repeated. Select $x$ such as,
$F(k)-1
But because,
$x-F(k-1)
We can express,
$x-F(k-1)$ as sum of numbers from $S$ none of which are repeated. Thus, as a result, $x$ is expressable as a sum of the numbers,
$S\cup F(k-1)$ without repetitions.
This means that any of the numbers,
$1,2,...,F(k+1)-1$ is expressable from the set,
$S\cup F(k-1)$ and the induction is complete.

Thus any number is expressable as a sum of distinct fibonacci numbers.

Note if any of the two fibonacci numbers are consecutive then they can be combined to give the number fibonacci number. Countinuing combining adjacent fibonacci number you have proven Zeckendorf's Representation

13. Originally Posted by ThePerfectHacker
Using induction for $n>2$.
----
Each of the integers $1,2,3,...,F(k)-1$ is a sum of numbers from the set $S=\{ F(1),F(2),...,F(k-2) \}$ none of which are repeated. Select $x$ such as,
$F(k)-1
But because,
$x-F(k-1)
We can express,
$x-F(k-1)$ as sum of numbers from $S$ none of which are repeated. Thus, as a result, $x$ is expressable as a sum of the numbers,
$S\cup F(k-1)$ without repetitions.
This means that any of the numbers,
$1,2,...,F(k+1)-1$ is expressable from the set,
$S\cup F(k-1)$ and the induction is complete.

Thus any number is expressable as a sum of distinct fibonacci numbers.

Note if any of the two fibonacci numbers are consecutive then they can be combined to give the number fibonacci number. Countinuing combining adjacent fibonacci number you have proven Zeckendorf's Representation
What does F(k) represent here?

14. Originally Posted by malaygoel
What does F(k) represent here?
The $k$th fibonacci number. Just like in all the previous posts.

15. ## ...more golden trivia

Hi:

1. Any integral power of phi can be expressed as a linear binomial function of phi.

Specifically, (phi)^k = F_k(phi) + F_k-1, where F_n denotes the nth Fibonacci element (F_1=1, F_2=1, etcetera).

Ex: (phi)^6 = 8(phi) + 5
Ex: (phi)^2 = (phi) + 1
Ex: (phi)^-1 = (phi) - 1
Ex: (phi)^-6 = -8(phi) + 13

Note the existence of F_-1 and F_-2 in Examples 3 and 4. There is nothing inherent in the recursive definition of F_k that would restrict k to the set of natural numbers, N. Hence:

{...F_-5, F_-4, F_-3, F_-2, F_-1, F_0, F_1, F_2, F_3, ...} = {...5, -3, 2, -1, 1, 0, 1, 1, 2...}.

Notes:

i) Observe the alternating algebraic sign left of the equality.
Indeed, F_n < 0 iff n<0 and n even. Else, F_n >= 0.
ii) In all cases, |F_n| = F_|n|. E.g., |F_-8| = F_|-8| = F_8 = 21. Thus, F_-8 = -21.
iii) Proof by induction is straightforward and reasonably non-cumbersome.

2. Let a,b,c be consecutive in Z. Then, (phi)^a + (phi)^b = (phi)^c.

Example: (phi)^2+(phi)^3=(phi)^4

Argument: (phi)^2+(phi)^3= ((phi)+1)+(2(phi)+1)=3(phi)+2=(phi)^4.

3. (phi)^-1 + (phi)^-2 + (phi)^-3 + ... = phi.

Proof: (phi) > 1 implies 0 < (phi)^-1 < 1. Hence the series is harmonic and equivalent to:

u^1 + u^2 + u^3 + ... = u / (1 - u), where u = (phi)^-1. Therefore, the sum becomes [(phi)^-1] / [-(phi)+2] = [(phi)^-1] / [(phi)^-2] = phi, which completes the proof.

Regards,

Rich B.