# Thread: Induction Help!

1. ## Induction Help!

Sorry for all of these induction promblems, i have a couple of more questions, and as an respected remember recommended, i will attempt these promblems.

=============================

Define the sequence F as follows:

$\displaystyle F_1=1, F_2=1, F_n=F_n-1 + F_(n-2) n >= 3$

Prove that

$\displaystyle F_1^2+F_2^2+... F_n^2 = F_nF_(n+1) whenever n is a positive integer.$

Here is what i did

1. P(n): $\displaystyle F_1^2+F_2^2+... F_n^2 = F_nF_(n+1)$
2. P(3) $\displaystyle F_3^2 = F_3F_3+1$ Im confused on this step, i got $\displaystyle F_9 = F_3F_4$
3. Assume: P(n): $\displaystyle F_1^2+F_2^2+... F_n^2 = F_nF_(n+1)$
4. Prove P(n+1)
$\displaystyle F_n+F_n+1+F_(n+1)^2 = F_n+1F_n+2$ // replaces right hand side of the original equation up to teh summation of the left hand side
$\displaystyle f_n+1[F_n+F_n+1+F_n+1 = F_n+1F_n+2$ // Factored out $\displaystyle F_n+1$. Im stucked, i need pointers on step 2 and 4, thanks.

2. ## Fibonacci Sequence

Hello tokio
Originally Posted by tokio
Sorry for all of these induction promblems, i have a couple of more questions, and as an respected remember recommended, i will attempt these promblems.

=============================

Define the sequence F as follows:

$\displaystyle F_1=1, F_2=1, F_n=F_n-1 + F_(n-2) n >= 3$

Prove that

$\displaystyle F_1^2+F_2^2+... F_n^2 = F_nF_(n+1) whenever n is a positive integer.$

Here is what i did

1. P(n): $\displaystyle F_1^2+F_2^2+... F_n^2 = F_nF_(n+1)$
2. P(3) $\displaystyle F_3^2 = F_3F_3+1$ Im confused on this step, i got $\displaystyle F_9 = F_3F_4$
3. Assume: P(n): $\displaystyle F_1^2+F_2^2+... F_n^2 = F_nF_(n+1)$
4. Prove P(n+1)
$\displaystyle F_n+F_n+1+F_(n+1)^2 = F_n+1F_n+2$ // replaces right hand side of the original equation up to teh summation of the left hand side
$\displaystyle f_n+1[F_n+F_n+1+F_n+1 = F_n+1F_n+2$ // Factored out $\displaystyle F_n+1$. Im stucked, i need pointers on step 2 and 4, thanks.
Thanks for showing us your attempt. The sequence is the well-known Fibonacci Sequence, each of whose terms is the sum of the two preceding terms. So the sequence looks like this:

$\displaystyle 1, 1, 2, 3, 5, 8, 13, 21, ...$

So, with $\displaystyle P(n)$ defined as you have done:

$\displaystyle P(3) = 1^2 + 1^2 + 2^2 = 1 + 1 + 4 = 6 = 2 \times 3 = F_3 \times F_4$

So $\displaystyle P(3)$ is true.

Now for the induction part:

$\displaystyle P(n) \Rightarrow F_1^2 + F_2^2 + ... + F_n^2 + F_{n+1}^2 = F_nF_{n+1}+F_{n+1}^2$

$\displaystyle = F_{n+1}(F_n + F_{n+1})$

$\displaystyle = F_{n+1}F_{n+2}$, since $\displaystyle F_{n+2}=$ the sum of the two preceding terms, $\displaystyle F_{n+1} + F_n$

$\displaystyle = F_{n+1}F_{(n+1)+1}$

$\displaystyle \Rightarrow P(n+1)$

Since we have already shown that $\displaystyle P(3)$ is true, this completes the proof.