Results 1 to 15 of 15

Math Help - Fibonacci's sequence

  1. #1
    Senior Member
    Joined
    Apr 2006
    Posts
    290

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote 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
    Your proof is correct.
    Do you know countinued fraction? There is an easy proof from there.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2006
    Posts
    290
    I don't no sorry.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member malaygoel's Avatar
    Joined
    May 2006
    From
    India
    Posts
    648
    Quote 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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,866
    Thanks
    745
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member malaygoel's Avatar
    Joined
    May 2006
    From
    India
    Posts
    648
    Quote 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?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,866
    Thanks
    745
    Hello, malaygoel!

    Is there any proof of this trivia?

    I'm so glad you asked . . .

    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!

    Follow Math Help Forum on Facebook and Google+

  9. #9
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,866
    Thanks
    745

    About Phi-bonacci

    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
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member malaygoel's Avatar
    Joined
    May 2006
    From
    India
    Posts
    648
    Quote 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?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote 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<x<F(k+1)
    But because,
    x-F(k-1)<F(k+1)-F(k-1)=F(k)
    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
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member malaygoel's Avatar
    Joined
    May 2006
    From
    India
    Posts
    648
    Quote 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<x<F(k+1)
    But because,
    x-F(k-1)<F(k+1)-F(k-1)=F(k)
    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?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by malaygoel
    What does F(k) represent here?
    The kth fibonacci number. Just like in all the previous posts.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    Nov 2005
    From
    Wethersfield, CT
    Posts
    92

    ...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.
    Last edited by Rich B.; June 11th 2006 at 09:13 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci sequence
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 6th 2010, 08:34 AM
  2. Fibonacci sequence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 28th 2010, 04:54 AM
  3. Replies: 2
    Last Post: March 1st 2010, 12:57 PM
  4. Fibonacci Sequence
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 15th 2009, 12:47 AM
  5. Fibonacci sequence
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: September 26th 2009, 09:28 PM

Search Tags


/mathhelpforum @mathhelpforum