Let f 1 = 1, where n ∈ N . Show that f 2 n + 1 = f n + 1 2 + f n 2

Question

Let       f    1    =  1, where   n  ∈      N  . Show that       f          2      n      +      1        =      f          n      +      1        2    +      f    n    2

Arianna Turner · Accepted Answer

This result, and others like it, is most easily shown using matrices. First, prove to yourself by induction that            (                                    1                                1                                                1                                0                              )        n    =      (                                        f                          n              +              1                                                            f            n                                                            f            n                                                f                          n              −              1                                            )    .(We choose       f    0    =  0, of course.) Let   M  =      (                            1                          1                                      1                          0                      )  . Then       M          2      n        =      M    n        M    n   implies                              (                                                                      f                                      2                    n                    +                    1                                                                                                f                                      2                    n                                                                                                                        f                                      2                    n                                                                                                f                                      2                    n                    −                    1                                                                                )                                    =                                          (                                                                                f                                          n                      +                      1                                                                                                            f                    n                                                                                                                    f                    n                                                                                        f                                          n                      −                      1                                                                                            )                    2                                                  =                              (                                                                      f                                      n                    +                    1                                    2                                +                                  f                  n                  2                                                                              f                                      n                    +                    1                                                                    f                  n                                +                                  f                  n                                                  f                                      n                    −                    1                                                                                                      ⋯                                            ⋯                                              )                ,                                          (                                                                      f                                      2                    n                    +                    1                                                                                                f                                      2                    n                                                                                                                        f                                      2                    n                                                                                                f                                      2                    n                    −                    1                                                                                )                                    =                                          (                                                                                f                                          n                      +                      1                                                                                                            f                    n                                                                                                                    f                    n                                                                                        f                                          n                      −                      1                                                                                            )                    2                                                  =                              (                                                                      f                                      n                    +                    1                                    2                                +                                  f                  n                  2                                                                              f                                      n                    +                    1                                                                    f                  n                                +                                  f                  n                                                  f                                      n                    −                    1                                                                                                      ⋯                                            ⋯                                              )                ,            where we have left out entries that give nothing new. Therefore, we immediately have      f          2      n      +      1        =      f          n      +      1        2    +      f    n    2    .We also get       f          2      n        =      f    n    (      f          n      +      1        +      f          n      −      1        )  =      f    n    (      f    n    +  2      f          n      −      1        ) for free.This is the Fibonacci sequence, about which much is known.

seiyakou2005n1 · Accepted Answer

f          2      n      +      1        =      f          2      n        +      f          2      n      −      1      Using the formula again on       f          2      n            f          2      n      +      1        =  2      f          2      n      −      1        +      f          2      n      −      2      Now using it on       f          2      n      −      1            f          2      n      +      1        =  3      f          2      n      −      1        +  2      f          2      n      −      2      Suppose after iterating this process i times, we have      f          2      n      +      1        =      a    i        f          2      n      +      1      −      i        +      b    i        f          2      n      −      i      Then after the next iteration we will have      f          2      n      +      1        =  (      a    i    +      b    i    )      f          2      n      −      i        +      a    i        f          2      n      −      i      In other words,       b          i      +      1        =      a    i   and       a          i      +      1        =      a    i    +      b    i  So       a    i    =      b          i      +      1       and       b          i      +      2        =      b          i      +      1        +      b    i  . Since       b    1    =      b    2    =  1Moreover, after i iteration of the process we have      f          2      n      +      1        =      b          i      +      1            f          2      n      +      1      −      i        +      b    i        f          2      n      −      i        =      f          i      +      1            f          2      n      +      1      −      i        +      f    i        f          2      n      −      i      Now just set i = n, and you get the result.

Let f 1 </msub> = 1 , where n ∈ <mrow class="MJX-TeXAtom-O

Answered question

Answer & Explanation

New Questions in Calculus 2