# Thread: Help with Mathematical Induction Proofs (Side question: Breaking-up Summations)

1. ## Help with Mathematical Induction Proofs (Side question: Breaking-up Summations)

Need some help with various problems. I've already completed all the proofs, I would just like for someone to check for errors. I'm new to induction, and I'm attempting to teach myself. Can someone make sure I'm not teaching myself incorrectly?

Given the Fibonacci sequence:
$f(0) = 0, f(1) = 1, f(n) = f(n-1) + f(n-2)$
Prove by Induction:
$f(1)^2 + f(2)^2 + f(3)^2 + ... + f(n)^2 = f(n)f(n+1)$
Let n = 2. We know that f(2) = 1 and f(3) = 2.
$\displaystyle\sum\limits_{k=1}^n f(n)^2$ = f(n)f(n+1)
$\displaystyle\sum\limits_{k=1}^n f(2)^2$ = f(2)f(2+1)
(f(1)^2 + f(2)^2) = 1 * 2
(1+1) = 2
2 = 2 √
Assume:
$\displaystyle\sum\limits_{k=1}^n f(n)^2$ = f(n)f(n+1)
Prove:
$\displaystyle\sum\limits_{k=1}^n f(n)^2$ + f(n+1)^2= f(n+1)f(n+2)
We know that f(4) = 3 by the given formula.
Ultimately, the proof will roll out to be 6 = 6 if we let n = 2 for the new formula.

Does my work look appropriate for mathematical induction so far?

Lastly, this might need a new thread, but I'm also having trouble understanding "breaking up" summations.

By the definition of a summation, if I want to prove for example:

$\displaystyle\sum\limits_{k=3n}^5 2k$ = 4n(4n+2), so the proof should look like
$\displaystyle\sum\limits_{k=3n}^5 2k$ + $\displaystyle\sum\limits_{k=3(n+1)}^5 2k$ - $\displaystyle\sum\limits_{k=n}^n 2k$= 4(n+1)(4(n+1)+2),

Am I correct or incorrect? Do I even need to split the summation for this situation?

The summations for the latter example (not the Fibonacci example) are actually supposed to be ^ 5n and ^ 5(n+1) for the incremented summation. Latex seems to only like one integer or character.

And lastly...
is
$\displaystyle\sum\limits_{k=0}^n 5^k$ + $\displaystyle\sum\limits_{k=n}^n 5^k$
(where the second summation is actually supposed to be ^ (n+1))
mathematically legal without subtracting any part of the summation?
I would appreciate any help or tips.

2. Originally Posted by Auxilium1990
Need some help with various problems. I've already completed all the proofs, I would just like for someone to check for errors. I'm new to induction, and I'm attempting to teach myself. Can someone make sure I'm not teaching myself incorrectly?

Given the Fibonacci sequence:
$f(0) = 0, f(1) = 1, f(n) = f(n-1) + f(n-2)$
Prove by Induction:
$f(1)^2 + f(2)^2 + f(3)^2 + ... + f(n)^2 = f(n)f(n+1)$
Let n = 2. We know that f(2) = 1 and f(3) = 2.
$\displaystyle\sum\limits_{k=1}^n f(n)^2$ = f(n)f(n+1)
$\displaystyle\sum\limits_{k=1}^n f(2)^2$ = f(2)f(2+1)
(f(1)^2 + f(2)^2) = 1 * 2
(1+1) = 2
2 = 2 √
Assume:
$\displaystyle\sum\limits_{k=1}^n f(n)^2$ = f(n)f(n+1)
Prove:
$\displaystyle\sum\limits_{k=1}^n f(n)^2$ + f(n+1)^2= f(n+1)f(n+2)
We know that f(4) = 3 by the given formula.
Ultimately, the proof will roll out to be 6 = 6 if we let n = 2 for the new formula.

Does my work look appropriate for mathematical induction so far?

Lastly, this might need a new thread, but I'm also having trouble understanding "breaking up" summations.

By the definition of a summation, if I want to prove for example:

$\displaystyle\sum\limits_{k=3n}^5 2k$ = 4n(4n+2), so the proof should look like
$\displaystyle\sum\limits_{k=3n}^5 2k$ + $\displaystyle\sum\limits_{k=3(n+1)}^5 2k$ - $\displaystyle\sum\limits_{k=n}^n 2k$= 4(n+1)(4(n+1)+2),

Am I correct or incorrect? Do I even need to split the summation for this situation?

The summations for the latter example (not the Fibonacci example) are actually supposed to be ^ 5n and ^ 5(n+1) for the incremented summation. Latex seems to only like one integer or character.

And lastly...
is
$\displaystyle\sum\limits_{k=0}^n 5^k$ + $\displaystyle\sum\limits_{k=n}^n 5^k$
(where the second summation is actually supposed to be ^ (n+1))
mathematically legal without subtracting any part of the summation?
I would appreciate any help or tips.

Your question's too long: subdivide it in several ones if you need to. Let us focus on the Fibonacci question:

We assume that $\sum\limits^n_{i=0}F(i)^2=F(n)F(n+1)$ , and we now take n+1:

$\sum\limits^{n+1}_{i=0}F(i)^2=\sum\limits^n_{i=0}F (i)^2+F(n+1)^2=F(n)F(n+1)+F(n+1)^2$

$=\left[F(n)+F(n+1)\right]F(n+1)=F(n+2)F(n+1)$ , where

the second equality stems from the inductive hypothesis and the last one is just the definitiom

of the Fibonacci series.

Tonio