Solved

use induction to prove a fibonacci sequence

Posted on 2009-07-02
35
499 Views
Last Modified: 2012-05-07
I need some help stepping through this example.  I have added a file of the problem to make it clear what is being asked.
Untitled.pdf
0
Comment
Question by:PMG76
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 12
  • 12
  • 8
  • +3
35 Comments
 
LVL 53

Expert Comment

by:Infinity08
ID: 24762167
First of all, that's not the Fibonacci sequence, but it's similar.

So, how far did you get ?

Can you prove the base case (n = 0) ?
Can you prove the step ?
0
 

Author Comment

by:PMG76
ID: 24762185
You are correct.  I scanned the wrong question, but I need help with this one too.

So to solve for the base case do you simply just choose a number to see if it is true?
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24762196
>> So to solve for the base case do you simply just choose a number to see if it is true?

The base case in this case is for n = 0. Can you prove that the statement is true for n = 0 ?
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:PMG76
ID: 24762225
L0 = 2
L1 = 1

so 2 + 1 + 0 = l 0+2

So yes 0 is greater than or equal to 2
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24762261
>> so 2 + 1 + 0 = l 0+2

How did you get to that ?

What does :

        L0 + L1 + ... + Ln = L(n+2) - 1

become for n = 0 ?
0
 

Author Comment

by:PMG76
ID: 24762279
I plugged 2 in for L0
I plugged 1 in for L1
I plugged 0 in for n

so I got 2 + 1 + 0 = 0 + 2 -1
so no, n is not >= to 0
0
 
LVL 84

Expert Comment

by:ozo
ID: 24762285
You know that Ln = L(n-1) + L(n-2) for all b
You also know that L0 + ... + Ln = L(n+2) - 1 for some n
Can you now prove it for n+1?
i.e. that
L0 + ... + L(n+1) = L(n+3)
0
 
LVL 84

Expert Comment

by:ozo
ID: 24762303
When n=0
L0 + ... + Ln is L0 = 2

When n=1
L0 + ... + Ln is L0 + L1 = 2 + 1 = 3

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24762306
We're still working on proving the base step, ozo ;)

>> I plugged 2 in for L0
>> I plugged 1 in for L1
>> I plugged 0 in for n

That's not how it works ... The left side of :

        L0 + L1 + ... + Ln = L(n+2) - 1

is the sum of all sequence elements up to and including the item with index n. What would the sum be of all sequence elements when n = 0 ?
0
 

Author Comment

by:PMG76
ID: 24762332
L0 + L1 + L0
0
 
LVL 84

Expert Comment

by:ozo
ID: 24762345
(if the ... in the 0 and 1 case are too confusing to you, then see if you can do the inductive step starting from the n=2 base case, it shouldn't really matter what n you use for the inductive step, since the same proof should work for all n larger than the base case
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24762346
>> L0 + L1 + L0

L0 + L1 + ... + Ln is a notation that stands for the sum of all Lx for x ranging from 0 to n.
What would be that sum for n = 0 ?

ie. what would be the sum of all Lx for x ranging from 0 to 0 ?
0
 

Author Comment

by:PMG76
ID: 24762359
Lx + n?
0
 
LVL 84

Expert Comment

by:ozo
ID: 24762369
No, the sum notation indicates
L0 when n=0
L0 + L1 when n=1
L0 + L1 + L2 when n=2
L0 + L1 + L2 + L3 when n=3
L0 + L1 + L2 + L3 + L4 when n=4
etc.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24762377
>> Lx + n?

It seems I'm confusing you ...

Do you understand everything I said in http:#24762346 ?
0
 

Author Comment

by:PMG76
ID: 24762379
Lx + (N + 1)  ?
0
 

Author Comment

by:PMG76
ID: 24762393
No, It appears that I don't understand what you mean.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24762401
You're just guessing now :)

Maybe you should read up a bit on summations :

        http://en.wikipedia.org/wiki/Summation

so that you can at least understand the mathematical notation used.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24762417
>>         http://en.wikipedia.org/wiki/Summation

Btw, don't read too much of it, just the first few paragraphs, up to and including the one talking about the "index of summation".
0
 
LVL 84

Expert Comment

by:ozo
ID: 24762431
the range from 0 to 0 is (0), so when  n=0, the sum  is
L0
the range from 0 to 1 is  (0,1) so when  n=1, the sum  is
L0 + L1
the range from 0 to 2 is  (0,1,2) so when  n=2 the sum  is
L0 + L1 + L2
the range from 0 to 3 is  (0,1,2,3) so when  n=3 the sum  is
L0 + L1 + L2 + L3

0
 

Author Comment

by:PMG76
ID: 24762447
The formula is then n/2 (2a + (n-1) d

The distance is not a constant distance.  I know how to do summations, but not making my own or this complicated.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24762545
Ok, it seems reading that wiki page confused you even more ... Just forget it heh ...

Do you understand the notation by what ozo wrote in http:#24762431 ?
0
 

Author Comment

by:PMG76
ID: 24762584
Yes, i believe so
0
 
LVL 18

Expert Comment

by:WaterStreet
ID: 24762589
PMG76,

"I know how to do summations, but not making my own or this complicated."

I don't plan on adding anything, except to wonder if the difficulty is who to listen to and how it relates to your then most recent posting.

My suggestion is to address your postings directly to the expert to whom you are speaking.

That's all I have to say.

WaterStreet,
Core Zone Advisor
EE's Other Zone

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24762611
>> Yes, i believe so

Ok, then could you get back to http:#24762261, and continue from there ?


WaterStreet, thanks for keeping us in check ;)
0
 

Author Comment

by:PMG76
ID: 24762692
L0 + L1 + ... + L0 = L(0+2) - 1
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24762754
The right side is ok, but the left side still isn't ...

Refer back to ozo's post http:#24762431 to know what the notation L0 + L1 + ... + Ln stands for for different values of n.
0
 
LVL 84

Expert Comment

by:ozo
ID: 24762791
n/2 (2a + (n-1) d)
would be the formula for the sum of
(a+0*d) + (a+1*d) + (a+2*d) + ... (a+(n-1)*d)
or
sum(i=0 ... n-1 : a+i*d)

The sum in question here is
L0 + L1 + ... + Ln
or
sum(i=0...n : Li)

I explicitly told you what that sum was for various n in
http:#2476243
0
 

Author Comment

by:PMG76
ID: 24762797
L0 + L1 + ... + L0 = L(0+2) - 1

should have been L0 + L1 + ... + Ln = L(0+2) - 1  correct?
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 300 total points
ID: 24762848
>> should have been L0 + L1 + ... + Ln = L(0+2) - 1  correct?

But what is L0 + L1 + ... + Ln for n = 0 ? Refer to ozo's post http:#24762431 to know ...
0
 

Author Comment

by:PMG76
ID: 24762889
the range from 0 to 0 is (0), so when  n=0, the sum  is L0
L0 = L (0+2) -1?
0
 
LVL 84

Expert Comment

by:ozo
ID: 24762926
the L0 + L1 + ... + Ln  notation, in attempting to illustrate the sequence in general, may be confusing in suggesting that L1 is necessarily part of the sum.
sum(i=0...n : Li) may be less misleading in that sense, but is also more abstract, which may make it less intuitive.
You can just take our word that
 L0 + L1 + ... + Ln
means
L0
when n=0
...
and that
 L0 + L1 + ... + Ln
means
L0 + L1 + L2 + L3
when n=3
and that
 L0 + L1 + ... + Ln
means
L0 + L1 + L2 + L3 + L4
when n=4
but doesn't matter as much whether you believe us for n=0 and n=1
as long as you can extend it to larger n, and can do the inductive step
from some n for which
L0 + L1 + ... + Ln  = Ln+2  - 1
is true to the next value of n
0
 
LVL 84

Assisted Solution

by:ozo
ozo earned 200 total points
ID: 24762962
> L0 = L (0+2) -1?
yes
L(0+2)
is L2
Ln = L(n-1) + L(n-2)
so
L2 = L1 + L0
= 1 + 2 = 3


0
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 24764473
Given  

Ln-2 + Ln-1 =Ln     (1)

show

L0 + L1 + L2 + L3+  Ln  = Ln+2  - 1


(A) Base case

True for n=0 as

    L2 - 1 = 3 -1 = 2 = L0


(B)  Assume true for n

ie that L0 + L1 + L2 + L3+  Ln  = Ln+2  - 1     (2)

then

L0 + L1 + L2 + L3+  Ln  +  Ln+1

  =  Ln+2  - 1 +   Ln+1     (by inductive assumption eqn (2) )

  =  Ln+3  - 1       (  by  eqn 1 )


Hence if true for n true  for n+1,  since true for n=0 by inductive assumption true for all n

Proved
0
 
LVL 2

Expert Comment

by:Bob_Everard
ID: 24777139
You want induction, here's induction.

First, show that it's true for some value of n >=2, say n = 2.

L0 + L1 + L2 = 2 + 1 + 3 = 6 = 7 - 1 = L4 - 1. True.

(L0 + L1 + L2) + L3 = 6 + 4 = 10
(L4 - 1) + L3            = 7 + 4 = 11 , which means (L3 + L4 - 1) = L5 - 1

QED
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethi…
When we purchase storage, we typically are advertised storage of 500GB, 1TB, 2TB and so on. However, when you actually install it into your computer, your 500GB HDD will actually show up as 465GB. Why? It has to do with the way people and computers…
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

734 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question