text: # Thread: Induction and Fibonacci Numbers
  
  1. ## Induction and Fibonacci Numbers
  
  I am trying to figure out how to show that $\displaystyle f_{n+1}f_{n-1}-f_{n}^{2}=(-1)^{n}$ when n is a positive integer.
  
  My Work
  P(n) is $\displaystyle f_{n+1}f_{n-1}-f_{n}^{2}=(-1)^n$ for $\displaystyle n>=1$
  
  Basis step - P(1) is true because $\displaystyle f_{2}f_{0}-f_{1}^{2}=1*0-1=-1=(-1)^1$
  Inductive step - Assume $\displaystyle P(k)=f_{k+1}f_{k-1}-f_{k}^{2}=(-1)^k$ is true,
  then $\displaystyle P(k+1)=f_{k+2}f_{k}-(f_{k+1}^2=(-1)^{k+1}$is true
  
  Then prove $\displaystyle P(k+1)=[f_{k+1}f_{k-1}-f_{k}^{2}]+[f_{k+2}f_{k}-f_{k+1}^{2}]=(-1)^k+[f_{k+2}f_{k}-f_{k+1}^2]$, but I can't figure out how to get this P(k+1) equation to equal $\displaystyle (-1)^{k+1}$
  
  I received the reply below, which is probably a wonderful answer, but I am unclear as to where in the 3rd line came from. I though you had to add the initial part of the P(k+1) equation, which is $\displaystyle f_{k+1}f_{k}-f_{k+1}^2$, to both sides of the P(k) equation as I did above.
  
  Assume for n.
  
  We want to show that
  
  ,<--- negative of the induction hypothesis
  
  by the induction hypothesis.
  
  So, is true.
  
  2. $\displaystyle f_n(f_{n+1}+f_n) - f_{n+1}(f_{n}+f_{n-1})$ comes directly from the definition of the Fibonacci numbers. Remember that $\displaystyle f_n = f_{n-1} + f_{n-2}$?
  So in your case in $\displaystyle f_{n}f_{n+2} - f^2_{n+1}$
  $\displaystyle f_{n+2} = f_{n+1}+f_{n}$
  and
  $\displaystyle f^2_{n+1} = f_{n+1}f_{n+1} = f_{n+1}(f_{n}+f_{n-1})$,
  since $\displaystyle f_{n+1} = f_{n} + f_{n-1}$
  
  3. The math makes sense but I still do not understand why you are allowed to do the "negative of the inductive hypothesis" to get the extra -1 to make the answer $\displaystyle {-1}^{K}$. Doesn't the answer also still need to be $\displaystyle {-1}^{K+1}$?
  
  Also, I thought it wasn't supposed to prove the exact P(k+1) equation in the inductive step but rather the P(k) equation with the first part of P(k+1) added to both sides as follows:
  
  Then, aren't I supposed to work on the second half of this equation to make it equal $\displaystyle {-1}^{K+1}$?
  
  EDIT:
  
  The math makes sense but I still do not understand why you are allowed to do the "negative of the inductive hypothesis" to get the extra -1 to make the answer be ? I already understand that -$\displaystyle {-1}^{k}={-1}^{k+1}$ I just don't know where the exra -1 came from.
  
  4. First of all
  $\displaystyle (-1)^k \not= (-1)^{k+1}$
  because they have opposite signs.
  
  Second of all, extra $\displaystyle -1$ comes from swapping terms in the equation of the inductive assumption, as in $\displaystyle 5-2=3, but 2-5=-(3)$. That's it.
metadata: {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}