You are doing it correctly, but you need to manipulate that fibonacci expression. You can do that by looking at the non-inductive proof I gave. And following with the same reasoning.

Printable View

- May 28th 2006, 10:02 AMThePerfectHacker
You are doing it correctly, but you need to manipulate that fibonacci expression. You can do that by looking at the non-inductive proof I gave. And following with the same reasoning.

- May 28th 2006, 03:43 PMNatasha1Quote:

Originally Posted by**ThePerfectHacker**

- May 28th 2006, 04:40 PMNatasha1
Is this better???

Step 1: For n = 1, we have

$\displaystyle (F_1 \cdot F_{1+2}) - (F_{1+1})^2 = (-1)^{1+1} = 1$

Hence the equation holds for n = 1

Step 2: Assume the equation is true for n = k (inductive hypothesis), we have:

$\displaystyle (F_k \cdot F_{k+2}) - (F_{k+1})^2 = (-1)^{k+1}$

Step 3: We then have to use our inductive hypothesis to prove that the statement is also true for n = k + 1, i.e we have to prove:

$\displaystyle (F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}$

Since there is a $\displaystyle k\geq 2$ such as,

$\displaystyle F(k)^2-F(k+1)F(k-1)=(-1)^{k-1}$

Then proof it hold for $\displaystyle k+1$. But the expression,

$\displaystyle F(k+1)^2-F(k+2)F(k)=(-1)(F(k)^2-F(k+1)F(k-1))$

But,

$\displaystyle F(k)^2-F(k+1)(k-1)=(-1)^{k-1}$

Thus,

$\displaystyle F(k+1)^2-F(k+1)F(k)=(-1)(-1)^{k-1}=(-1)^k$

Thus, it hold true for $\displaystyle k+1$.

$\displaystyle (F_{k+1} \cdot F_{k+3}) - (F_{k+2})^2 = (-1)^{k+2}$

Hence the equation holds true for n = k + 1 - May 29th 2006, 12:58 AMCaptainBlackQuote:

Originally Posted by**Natasha1**

$\displaystyle =F_{k+1} F_{k+2}+(F_{k+1})^2 - (F_{k+2})^2$.

Now:

$\displaystyle F_{k+1}=F_{k+2}-F_{k}$,

so:

$\displaystyle F_{k+1} F_{k+3} - (F_{k+2})^2=$$\displaystyle (F_{k+2}-F_{k}) F_{k+2}+(F_{k+1})^2 - (F_{k+2})^2$

.$\displaystyle =-F_{k} F_{k+2}+(F_{k+1})^2=-1((F_k \cdot F_{k+2}) - (F_{k+1})^2)=(-1)^{k+2}$

Which proves that if the statement is true for $\displaystyle k$ it is true for

$\displaystyle k+1$.

RonL - May 29th 2006, 06:48 AMSoroban
Hello, Natasha!

An*inductive*proof requires some world-class acrobatics . . .

Quote:

I need to prove**by induction**that for the Fibonacci sequence:

$\displaystyle (F_n)\cdot(F_{n+2}) - (F_{n+1})^2 \;= \;(-1)^{n+1}$ . . . $\displaystyle F_n$ being a Fibonacci number

Verify $\displaystyle S(1):\;\;(F_1)\cdot(F_3) - (F_2)^2 \:=\:(-1)^2\quad\Rightarrow\quad 1\cdot2 - 1^2\:=\:1$ . . . yes!

Assume $\displaystyle S(k)$ is true: .$\displaystyle (F_k)(F_{k+2}) - (F_{k+1})^2\;=\;(-1)^{k+1}$

. . and we will try to prove $\displaystyle S(k+1)\:=\:(F_{k+1})(F_{k+3}) - (F_{k+2})^2\:=\:(-1)^{k+2} $

Since $\displaystyle F_k\,=\,F_{k+2} - F_{k+1}$ and $\displaystyle F_{k+2} \,=\,F_{k+3} - F_{k+1}$

$\displaystyle S(k)$ becomes: $\displaystyle (F_{k+2} - F_{k+1})(F_{k+3} - F_{k+1}) - (F_{k+1})^2 \;= \;(-1)^{k+1} $

Expand: $\displaystyle (F_{k+2})(F_{k+3}) - (F_{k+1})(F_{k+2}) - (F_{k+1})(F_{k+3}) + (F_{k+1})^2 - $$\displaystyle (F_{k+1})^2\;=\;(-1)^{k+1}$

We have: $\displaystyle (F_{k+2})(F_{k+3}) - (F_{k+1})(F_{k+2}) - (F_{k+1})(F_{k+3}) \;= \; (-1)^{k+1}$

Factor: $\displaystyle (F_{k+2})\cdot(\underbrace{F_{k+3} - F_{k+1}}) - (F_{k+1})(F_{k+3}) \;= \; (-1)^{k+1} $

. . . . . . . . . . .This is $\displaystyle F_{k+2}$

An we have: $\displaystyle (F_{k+2})^2 - (F_{k+1})(F_{k+3}) \;=\;(-1)^{k+1} $

Multiply by $\displaystyle -1:\;\;(F_{k+1})(F_{k+3}) - (F_{k+2})^2\;=\;(-1)^{k+2} $

. . .*ta-DAA!*. . . This is $\displaystyle S(k+1)\;!$