Question

\[f _{n}\] denotes the nth Fibonacci number. Prove \[\sum_{k=0}^{n} f _{k}^{2} =f _{n} f _{n+1}\]

Answer 1

if you would be kind enough, please show me the steps as u solve it

Answer 2

Have you tried induction?

Answer 3

i don't know how to do induction
..im very bad at discrete math

Answer 4

i think i just had a really bad teacher

Answer 5

Have you learnt induction in your course?

Answer 6

yes i have but it just went over my head..i don't even know where to start or what the steps are...but if you are willing to teach me how to do it step by step then that would be good..we got a take home final and i must pass it to have the slightest chance of passing the class..so u can show me how to do it and explain it good or just give me the answer and show all the steps...

Answer 7

The reason I ask is induction is the way to prove this result.

When you learn induction, it's probably one of the most involved mathematical procedures you will have learnt up to that time. Let me see if I can find a good video or web site that can walk you through it and you can review at your pace.

Answer 8

ok thank you

Answer 9

Here is a good example of proof by induction.
http://www.khanacademy.org/video/proof-by-induction?playlist=Algebra
Watch this, make sure you really understand it. If that means you watch it 2 or 3 times, nothing wrong with that.

And then we can talk about your problem again.

Answer 10

ok will do..thanks again :)

Answer 11

Once you've digested the Khan Academy video, watch this example so you see one more example which is slightly more complicated and definitely faster.
http://www.youtube.com/watch?v=3qTJrWCgVwI&feature=related
Your problem is a step up in complexity again.

Answer 12

(This second video also cracks me up because you feel like he wouldn't hesitate to beat you with that black rod if you made an error.)

Answer 13

ok so i watched both videos and understand what the authors were doing...but i dont know where to take the numbers from my problem and plug it in to the formula \[s(n) = n(n+1) / 2\]

Answer 14

lol

Answer 15

that formula for the sum of integers has nothing to do with your problem.

Answer 16

hey brb i have to use the rest room...but keep typing i'll bb in a min..

Answer 17

The general method for using induction is the following

1. Define carefully the statement you want to prove by induction P(n), as per the second video and define the domain of n (usually n are natural numbers)

2. Show that P(1) is true. (or whatever the lowest value of n is in the domain of P(n))

3. Show that for arbitrary k in the domain of P(n), that
P(k) ==> P(k+1)
i.e., the result P(k) logically implies P(k+1)

4. Then conclude by the Principle of Mathematical Induction that P(n) is true for all n

Answer 18

So ... step 1:
For your problem, what is the statement P(n) you are trying to prove?

Answer 19

still there?

Answer 20

back

Answer 21

ok sooo how do i start to do my problem?

Answer 22

\[\sum_{k=0}^{n} f _{k}^{2} =f _{n} f _{n+1}\]

Answer 23

Right and what is the domain of n here?

Answer 24

im not sure to be honest

Answer 25

n is non-negative integers; n = 01,2,3,4,...

Now. Before we go any further, what is the definition of the Fibonacci numbers?

Answer 26

i don't know that either lol =/

Answer 27

im telling u ..this class has been soo hard for me man i have no clue what i am doing

Answer 28

i take notes and everything but i have no idea what i am writing down

Answer 29

Do you have a textbook? If so, look up Fibonacci numbers there. If not, go and google it. Then tell me what you find.

Answer 30

oh yeah it is when u add the current number with the previous number to get the next number

Answer 31

but it starts' with 0 and 1

Answer 32

so it's 0,1, then 1+0= 1, then 1+1=2, 2+1=3, 3+2=5, 5+3=8.....right?

Answer 33

Ok, so in terms of the \[ f_n \] write down the definition

Answer 34

\[ f_0 = 0, f_1 = 1 \]
and
\[ f_{n+2} = f_n + f_{n+1} \]

Answer 35

ok. So returning now to the four steps:
2. Show that P(1) is true. (or whatever the lowest value of n is in the domain of P(n))

Hence, show that P(0) is true.

Answer 36

see i dont understand that when it's put like that
it has to be dummied down for me hehe

Answer 37

given those values of f0 and f1, the formula is saying
f2 = f0 + f1 = 0 + 1 = 1.

So what is f3?

Answer 38

f3 = f1 + f2 = ...

Answer 39

f3 = f0 + f1+ f2= 0 + 1+ 2 = 3?

Answer 40

No, f_n+2 = f_n+1 + f_n.

Hence f3 = f2 + f1
= 1 + 1
= 2

What is f4?

Answer 41

f0 = 0, f1 = 1, f2 = 1, f3 = 2

What is f4?

Answer 42

im so confused now

Answer 43

hold on

Answer 44

f0 = 0,
f1 = 1,

f2 = f0 + f1 = 0 + 1 = 1

f3 = f1 + f2 = 1 + 1 = 2

f4 = f2 + f3 = ...

Answer 45

let me ask something so how would you find f(64) or some large number like that?

Answer 46

so f4 = f2, which is 1 + f3, which is 2, so 2+1 = 3

Answer 47

so to find f(64) do u have to find all the f from 0-63 ?

Answer 48

Yes, f4 = f2 + f3 = 1 + 2 = 3
and f5?

The short answer to your question is as we currently define this sequence, there's no quick way to find f(64) or f(640), which isn't to say there ins't a quick way; you just don't know it yet.

Answer 49

so f5 is (and only because we found f 0-4 right?) = f3 + f4, which is 2+3 respectively, which = 5
so f5=5?

Answer 50

yes.

Answer 51

Ok. So follow now the procedure I've outlined for you.

Step 2: Show P(0) is true.

Then steps 3 and 4.

Answer 52

one question...where are u getting 0 from? is it because k=0 under the sum sign?

Answer 53

So P(0) says that
\[ \sum_{k=0}^0 f_k^2 = f_0f_1 \]

This is true because f0 = 0 and hence the LHS (left hand side) of that expression is
\[ f_0^2 = 0^2 \]
and the RHS is
\[ f_0f_1 = 0 . 1 = 0 \]
and are therefore equal.

Hence the statement P(0) is true.

Answer 54

Step 3: show that P(k) implies P(k+1) for arbitrary k.

(And yes I know that n can equal zero from the way the question is posed.)

Answer 55

If P(k) is true then
\[ \sum_{j=0}^k f_j^2 = f_kf_{k+1} \]
We've changed the variable of summation to j to avoid having k mean two things.

Show that this implied P(k+1) i.e., that
\[ \sum_{j=0}^{k+1} f_j^2 = f_{k+1}f_{k+2} \]

Answer 56

i have no idea wht u are saying man

Answer 57

then go back and watch that second video again. I am following exactly the procedure he is using there, but applying it to your problem.

Answer 58

are u solving it or are some other step?

Answer 59

that's what i need help with ...what am i taking from my problem and what am i plugging in?

Answer 60

I've completely outlined it for you. You need to read a few more proofs by induction to understand what's going on here. I'm sure your text book has a few. Go and find them. Copy them out. Then back a blank piece of paper and replicate one or two of them without looking. When you can do that, then you'll be ready to tackle this problem.

Answer 61

Very patient, JJ.