Fibonacci Induction Proof: Step-by-Step Guide for n >= 1 | Easy Tutorial

[teppel]

Homework Statement

Hi may i know how 2 start with this proof by induction of fibonacci .
For n >= 1
<br /> \sum_{i = 1} ^ n fib^2(n) = fib(n) * fib(n + 1)}<br />

Homework Equations

The Attempt at a Solution

First step - Basic step i sub 1 to the equation.
Then i get
fib(1)^2 = fib(1) * fib(2)
1^2 = 1*1
1 = 1 (proof)

Second step i need to sub n - 1 into the equation. But i stuck at this step, anyone can guide me along how to continue ? Maybe can give me some link or tutorial on the induction. Because i still quite blur at how the proof by induction work. I google about the topic, but the examples still too hard for me to understand.
Thanks in advance.

 

[Mark44]

Homework Statement

Hi may i know how 2 start with this proof by induction of fibonacci .
For n >= 1
<br /> \sum_{i = 1} ^ n fib^2(n) = fib(n) * fib(n + 1)}<br />

Homework Equations

The Attempt at a Solution

First step - Basic step i sub 1 to the equation.
Then i get
fib(1)^2 = fib(1) * fib(2)
1^2 = 1*1
1 = 1 (proof)

Second step i need to sub n - 1 into the equation. But i stuck at this step, anyone can guide me along how to continue ? Maybe can give me some link or tutorial on the induction. Because i still quite blur at how the proof by induction work. I google about the topic, but the examples still too hard for me to understand.
Thanks in advance.

It helps to use a different variable, say k.

Your next step is to assume that the statement is true for n = k. IOW, assume that the following is true.

<br /> \sum_{i = 1} ^ k fib^2(k) = fib(k) * fib(k + 1)<br />

Finally, show that the statement is true for n = k + 1, using the previous assumption (the induction hypothesis).
<br /> \sum_{i = 1} ^{k + 1} fib^2(k + 1) = fib(k + 1) * fib(k + 2)<br />

 

[teppel]

It helps to use a different variable, say k.

Your next step is to assume that the statement is true for n = k. IOW, assume that the following is true.

<br /> \sum_{i = 1} ^ k fib^2(k) = fib(k) * fib(k + 1)<br />

Finally, show that the statement is true for n = k + 1, using the previous assumption (the induction hypothesis).
<br /> \sum_{i = 1} ^{k + 1} fib^2(k + 1) = fib(k + 1) * fib(k + 2)<br />

Haha. Thanks for the help, i try to figure out. Do u have any tutorial or simple example link for me to start researching on ? Because i can't find a simple version of induction online. Whenever i do a search, it just return me tons of words.

 

[Mark44]

On wikipedia.org search for "mathematical induction"

 

[teppel]

On wikipedia.org search for "mathematical induction"

Thanks for the help

 

[teppel]

Hi, after some thoughts. i not sure whether i got the logic right anot. Please point to me if there any error

\sum_{i = 1} ^ n fib^2(n) = fib(n) * fib(n + 1)}

After basic step - which i sub 1 into the equation, mention b4 at the above post
Then i get
fib(1)^2 = fib(1) * fib(2)
1^2 = 1*1
1 = 1 (proof)

Induction step
I use k - 1 instead of k because of my lecturer preference. No error with it right ?
\sum_{i = 1} ^{k - 1} fib^2(k - 1) = fib(k - 1) * fib(k)

mine Logic is
fib(k - 1) x fib(k) + (fib(k) x fib(k - 1) - fib(k - 1) x fib(k)) = fib(k) x fib(k + 1)

I add the different between fib(k) and fib(k - 1) to fib(k - 1).
But how i going to extend the above sentence. i can to a fibonacci equation on those k and k + 1. As they are not number. Anyone can give me some lights to continue ?