# Proving a properties of fibonacci numbers

1. May 10, 2013

### John112

Let p[n] be the following property of Fibonacci numbers:
p[n]: f$_{n+1}$ * f$_{n-1}$ - (f$_{n}$)$^{2}$ = (-1)$^{n}$. Prove p[n] by induction.

This is the proof I wrote. i used regular induction. Is weak induction sufficient to prove it or do I need to prove this by strong induction?

proof:

BASE STEP: p[1]: f$_{2}$ * f$_{0}$ - (f$_{1}$)$^{2}$ = (1 * 0) - 1 = -1

and (-1)$^{1}$ = -1

INDUCTIVE STEP:

assume P[k]: f$_{k+1}$ * f$_{k-1}$ - (f$_{k}$)$^{2}$ = (-1)$^{k}$

show p[k+1]: f$_{k+2}$ * f$_{k}$ - (f$_{k+1}$)$^{2}$ = (-1)$^{k+1}$

We know f$_{k+2}$ = f$_{k+1}$ + f$_{k}$

p[K+1]: f$_{k+2}$ * f$_{k}$ - (f$_{k+1}$)$^{2}$ = (-1)$^{k+1}$

substitute f$_{k+2}$ = f$_{k+1}$ + f$_{k}$ into p[k+1]

p[k+1]: (f$_{k+1}$ + f$_{k}$) * f$_{k}$ - (f$_{k+1}$)$^{2}$ = (-1)$^{k+1}$

= f$_{k}$ * f$_{k+1}$ + (f$_{k}$)$^{2}$ - (f$_{k+1}$)$^{2}$

We know p[k]: f$_{k+1}$ * f$_{k-1}$ - (f$_{k}$)$^{2}$ = (-1)$^{k}$

We can rewrite p[k] as: (f$_{k}$)$^{2}$ = f$_{k+1}$ * f$_{k-1}$ - (-1)$^{k}$

We substitue (f$_{k}$)$^{2}$ from p[k] into the (f$_{k}$)$^{2}$ in p[k+1]

= f$_{k+1}$ + f$_{k}$ + f$_{k+1}$ * f$_{k-1}$ - (-1)$^{k}$ - f$_{k+1}$$^{2}$)

= f$_{k+1}$ (f$_{k+1}$ + f$_{k}$) (-1)$^{k}$ - f$_{k+1}$$^{2}$)

= (f$_{k+1}$)$^{2}$) - (-1)$^{k}$ - (f$_{k+1}$)$^{2}$)

= - ((-1)$^{k}$)

= (-1)$^{k+1}$

Does this proof strong enough or would I have to do this by strong induction? If by strong induction, how do I got about proving it?

2. May 10, 2013

### Staff: Mentor

Every valid proof with weak induction is a valid proof with strong induction, too (and this is the first time I saw specific words for them). Your proof uses valid steps only, therefore it is valid. There is no need to do more.