PMG76
asked on
use induction to prove a fibonacci sequence
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
Untitled.pdf
ASKER
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?
So to solve for the base case do you simply just choose a number to see if it is true?
>> 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 ?
The base case in this case is for n = 0. Can you prove that the statement is true for n = 0 ?
ASKER
L0 = 2
L1 = 1
so 2 + 1 + 0 = l 0+2
So yes 0 is greater than or equal to 2
L1 = 1
so 2 + 1 + 0 = l 0+2
So yes 0 is greater than or equal to 2
>> 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 ?
How did you get to that ?
What does :
L0 + L1 + ... + Ln = L(n+2) - 1
become for n = 0 ?
ASKER
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
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
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)
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)
When n=0
L0 + ... + Ln is L0 = 2
When n=1
L0 + ... + Ln is L0 + L1 = 2 + 1 = 3
L0 + ... + Ln is L0 = 2
When n=1
L0 + ... + Ln is L0 + L1 = 2 + 1 = 3
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 ?
>> 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 ?
ASKER
L0 + L1 + L0
(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
>> 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 ?
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 ?
ASKER
Lx + n?
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.
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.
ASKER
Lx + (N + 1) ?
ASKER
No, It appears that I don't understand what you mean.
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.
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.
>> 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".
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".
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
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
ASKER
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.
The distance is not a constant distance. I know how to do summations, but not making my own or this complicated.
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 ?
Do you understand the notation by what ozo wrote in http:#24762431 ?
ASKER
Yes, i believe so
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
"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
>> Yes, i believe so
Ok, then could you get back to http:#24762261, and continue from there ?
WaterStreet, thanks for keeping us in check ;)
Ok, then could you get back to http:#24762261, and continue from there ?
WaterStreet, thanks for keeping us in check ;)
ASKER
L0 + L1 + ... + L0 = L(0+2) - 1
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.
Refer back to ozo's post http:#24762431 to know what the notation L0 + L1 + ... + Ln stands for for different values of n.
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
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
ASKER
L0 + L1 + ... + L0 = L(0+2) - 1
should have been L0 + L1 + ... + Ln = L(0+2) - 1 correct?
should have been L0 + L1 + ... + Ln = L(0+2) - 1 correct?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
the range from 0 to 0 is (0), so when n=0, the sum is L0
L0 = L (0+2) -1?
L0 = L (0+2) -1?
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
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
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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
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
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
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
So, how far did you get ?
Can you prove the base case (n = 0) ?
Can you prove the step ?