Results 1 to 15 of 15

Math Help - Proving a property of a definition

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    13

    Proving a property of a definition

    I haven't felt like the professor has introduced the topic very well. I feel like I am expected to know how this works immediately but I have never done it before. I am missing the intuitive element I guess to this but moreover, I feel like sometimes the answers are too easy for me to see.


    Here is first problem I worked on ... going back to the comment of the answers being overly simplified:

    Fibonacci sequence

    F(1) = 1
    F(2) = 1
    F(n) = F(n-2) + F(n-1) for n >= 3

    Prove the given property of the Fibonacci sequence numbers directly from the definition.

    F(n+1) + F(n-2) = 2F(n) for n >= 3

    F(n+1) + F(n-2) = 2F(n)
    = [F(n-2) + F(n-1)] + F(n)
    = F(n) + F(n)
    = 2F(n)
    DONE .... this is the answer in the back of the book

    All of this makes sense except for one thing ... how in the world does this demonstrate that a property works. It's easy to see that the RHS can be manipulated back and forth a bit ... it does not show anything about the LHS of the equation. Furthermore, it doesn't demonstrate that both sides are equal, which, to me, would prove its validity. What am I missing here?

    Second problem that I am stuck on from the get go:

    F(n) = 5F(n-4) + 3F(n-5) for n>= 6

    I can't recognize a single property that I can transform this equation to ... I know very little about the fibonacci sequence other than the actual numbers so I am clueless I guess.

    Thanks for any input in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by mcox05 View Post
    I haven't felt like the professor has introduced the topic very well. I feel like I am expected to know how this works immediately but I have never done it before. I am missing the intuitive element I guess to this but moreover, I feel like sometimes the answers are too easy for me to see.


    Here is first problem I worked on ... going back to the comment of the answers being overly simplified:

    Fibonacci sequence

    F(1) = 1
    F(2) = 1
    F(n) = F(n-2) + F(n-1) for n >= 3

    Prove the given property of the Fibonacci sequence numbers directly from the definition.

    F(n+1) + F(n-2) = 2F(n) for n >= 3

    F(n+1) + F(n-2) = 2F(n)
    = [F(n-2) + F(n-1)] + F(n)
    = F(n) + F(n)
    = 2F(n)
    DONE .... this is the answer in the back of the book

    All of this makes sense except for one thing ... how in the world does this demonstrate that a property works. It's easy to see that the RHS can be manipulated back and forth a bit ... it does not show anything about the LHS of the equation. Furthermore, it doesn't demonstrate that both sides are equal, which, to me, would prove its validity. What am I missing here?

    Second problem that I am stuck on from the get go:

    F(n) = 5F(n-4) + 3F(n-5) for n>= 6

    I can't recognize a single property that I can transform this equation to ... I know very little about the fibonacci sequence other than the actual numbers so I am clueless I guess.

    Thanks for any input in advance.
    Have you tried using the actual definition and expanding it?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    13
    I have no idea how to go about doing that. For whatever reason, algebra is butter but I absolutely cannot figure out how to translate it to more abstract problems like this. Even simple ones.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by mcox05 View Post
    I have no idea how to go about doing that. For whatever reason, algebra is butter but I absolutely cannot figure out how to translate it to more abstract problems like this. Even simple ones.
    The n in F(n)=F(n-1)+F(n-2) is just a place holder. For example, let t=n-1 then you would no doubt agree with me saying that F(t)=F(t-1)+F(t-2), or equivalently F(n-1)=F(n-2)+F(n-3). Proceed.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2008
    Posts
    13
    Quote Originally Posted by Drexel28 View Post
    The n in F(n)=F(n-1)+F(n-2) is just a place holder. For example, let t=n-1 then you would no doubt agree with me saying that F(t)=F(t-1)+F(t-2), or equivalently F(n-1)=F(n-2)+F(n-3). Proceed.
    Lame attempt then stumped ...

    f(n) = 5f(n-4) + 3f(n-5)

    f(n-2) + f(n-1) = 5f(n-4) + 3f(n-5)

    ... that helps put it into perspective but you essentially just handed me a tool that I don't know how to use. I could put anything in place of n and have no idea where to run with it. I just simply don't understand how to manipulate functions. I can't see it like I can with something like 15x + 5x (yes, I know it is contrived but you get what I mean).

    Again, going back to my original comment. It feels like some big X component was skipped on handling properties but I cannot even figure out what it is.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by mcox05 View Post
    Lame attempt then stumped ...

    f(n) = 5f(n-4) + 3f(n-5)

    f(n-2) + f(n-1) = 5f(n-4) + 3f(n-5)

    ... that helps put it into perspective but you essentially just handed me a tool that I don't know how to use. I could put anything in place of n and have no idea where to run with it. I just simply don't understand how to manipulate functions. I can't see it like I can with something like 15x + 5x (yes, I know it is contrived but you get what I mean).

    Again, going back to my original comment. It feels like some big X component was skipped on handling properties but I cannot even figure out what it is.
    Think about it like this. Do you see that each F(t) can be decomposed into F(t-1)+F(t-2), and that then each of F(t-1),F(t-2) can be decomposed into F(t-2)+F(t-3),F(t-3)+F(t-4)....keep doing this and you'll notice that you can decompose F(n) into an expression like F(n)=\underbrace{F(n-4)+\cdots+F(n-4)}_{\text{some number}}+\underbrace{F(n-5)+\cdots+F(n-5)}_{\text{some other number}}. Guess what some number and some other number will be.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2008
    Posts
    13
    Quote Originally Posted by Drexel28 View Post
    Think about it like this. Do you see that each F(t) can be decomposed into F(t-1)+F(t-2), and that then each of F(t-1),F(t-2) can be decomposed into F(t-2)+F(t-3),F(t-3)+F(t-4)....keep doing this and you'll notice that you can decompose F(n) into an expression like F(n)=\underbrace{F(n-4)+\cdots+F(n-4)}_{\text{some number}}+\underbrace{F(n-5)+\cdots+F(n-5)}_{\text{some other number}}. Guess what some number and some other number will be.

    OMG did I finally have a "aha!" moment?! Tell me if I am on the right track here. BTW, your example put in terms that made sooooo much more damn sense (at least I think it did lol).

    f(1) = 1
    f(2) = 1
    f(n) = f(n-2) + f(n-1)

    prove the property using the definition ...
    that f(n) = 5f(n-4) + 3f(n-5) for n>=6 is true

    f(n) = 5f(n-4) + 3f(n-5)
    = [ f(n-4) + f(n-4) + f(n-4) + f(n-4) + f(n-4) ] + [ f(n-5) + f(n-5) + f(n-5) ]
    = 3f(n-3) + 2f(n-4)
    = 2f(n-2) + f(n-3)
    = f(n-2) + f(n-1) CHECK

    Which holds true with the original definition f(n) = f(n-2) + f(n-1)


    Tell me that I finally got it lol.

    P.s The explanation of decomposing the f(n) was the key that I was talking about. I just couldn't understand the method behind it ... I think it's probably that my professor just assumed that we all understood it from square one.
    Last edited by mcox05; January 6th 2010 at 10:54 PM. Reason: necessary
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778
    f(n) = 5f(n-4) + 3f(n-5)
    = [ f(n-4) + f(n-4) + f(n-4) + f(n-4) + f(n-4) ] + [ f(n-5) + f(n-5) + f(n-5) ]
    = 3f(n-3) + 2f(n-4)
    = 2f(n-2) + f(n-3)
    = f(n-2) + f(n-1) CHECK
    That is correct. I would only recommend writing it more like a proof in the final version. What I mean is that any proof has the following features.

    (1) For every written proposition (a statement that can be either true or false), its status (whether it is an assumption, an intermediate conclusion, a conjecture, an induction hypothesis, the intended goal of the proof, etc.) is clear.

    (2) A proof if forward-going, i.e., it starts from assumptions, proceeds by proving intermediate statements and finally shows that the final goal is true.

    In your writing, the status of "f(n) = 5f(n-4) + 3f(n-5)" is not very clear: is it what we need to show or is it a known fact we start with? Further, it is not clear whether in the following lines you are rewriting the LHS or the RHS of that equation.

    Your solution can start from the RHS and keep rewriting it until you arrive at the LHS: RHS = ... = ... = ... = LHS.

    The danger in starting from the goal of a proof and working on it until you get a true statement is in making a transition that is valid in one direction only. This way, you can "prove" false things. For example, we want to prove 2 = -2: we start from 2 = -2, take a square of both sides and arrive at a valid 4 = 4. The problem here is that x = y implies x^2=y^2 but not the other way around. For another example, we start from 5 = 6, multiply both sides by 0 and arrive at a valid 0 = 0. Again, here x = y implies xz=yz for any x, y and z, but not conversely.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Oct 2008
    Posts
    13
    Thank you for the insight emak. Although, I am getting away with demonstrating the property through it's definition so apparantly my professor doesn't require any form of formal proofing.

    Howeer I did hae a few more questions:

    Is it alid to decompose the equation as I did below regarding f(n+3)???
    1. f(n+3) = f(n+2) + f(n+1)

    Another question ... can expression below be manipulated in any fashion?

    f(n-1) + f(n+2)

    Thanks again.
    Last edited by mcox05; January 7th 2010 at 07:59 AM. Reason: clarification
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by mcox05 View Post
    Thank you for the insight emak. Although, I am getting away with demonstrating the property through it's definition so apparantly my professor doesn't require any form of formal proofing.

    Howeer I did hae a few more questions:

    Is it alid to decompose the equation as I did below regarding f(n+3)???
    1. f(n+3) = f(n+2) + f(n+1)

    Another question ... can expression below be manipulated in any fashion?

    f(n-1) + f(n+2)

    Thanks again.
    I mean, to what end? F(n-1)+F(n+2) =F(n-1)+F(n+1)+F(n)= F(n-1)+F(n)+F(n-1)+F(n-1)+F(n-2)=F(n)+3F(n-1)+F(n-2)

    Also, it may be useful to learn that F(n)=\frac{1}{\sqrt{5}}\left[\varphi^n+(-1)^{n+1}\varphi^{-n}\right]

    Where \varphi is the positive solution to \kappa^2-\kappa-1=0
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Oct 2008
    Posts
    13
    Mainly because now that I understand the basic premise, I need to learn more properties of decomposition.

    I am working on another problem, very similiar but I can't solve it entirely and I think it's because I am not aware of what I can and can't do.

    For instance, you pointed out that

    F(n-1)+F(n+2) = F(n-1)+F(n+1)+F(n)


    ... yet I don't understand how you arrived at that conclusion. I guess what I need is a little crash course on how to manipulate recursive relations (similar to what you learn while handling exponents).

    I am realizing that when the terms are similar and of the same type (i.e subtraction or addition, its easy to manipulate them). However, what can i do with something like the equation written above and what rules must be enforced.

    P.s sorry if this seems convoluted but my goal is to actually learn how this stuff works, not just hunt down answers to my homework. I am sure you can respect that.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by mcox05 View Post
    Mainly because now that I understand the basic premise, I need to learn more properties of decomposition.

    I am working on another problem, very similiar but I can't solve it entirely and I think it's because I am not aware of what I can and can't do.

    For instance, you pointed out that

    F(n-1)+F(n+2) = F(n-1)+F(n+1)+F(n)


    ... yet I don't understand how you arrived at that conclusion. I guess what I need is a little crash course on how to manipulate recursive relations (similar to what you learn while handling exponents).

    I am realizing that when the terms are similar and of the same type (i.e subtraction or addition, its easy to manipulate them). However, what can i do with something like the equation written above and what rules must be enforced.

    P.s sorry if this seems convoluted but my goal is to actually learn how this stuff works, not just hunt down answers to my homework. I am sure you can respect that.
    You just need to get past the fact that t can stand for anything( to a point) in F(t)=F(t-1)+F(t-2). Let t=n+2 and this becomes F(n+2)=F(n+2-1)+F(n+2-2)=F(n+1)+F(n)
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Oct 2008
    Posts
    13
    I think I am starting to understand that notion but what can I do when the problem has already substituted t for something else. Can I just perform the same operation?

    Here is a problem I am working on ... using your method.

    F(n+3) = 2F(n+1) + F(n)

    let n = n-2

    F([n-2] + 3) = F([n-2]+1) + F([n-2]+1) + F(n-2)
    F(n+1) = [F(n-1) + F(n-1)] + F(n-2)
    F(n) + F(n-1) = F(n) + F(n-1) CHECK


    does that work as I think it does?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by mcox05 View Post
    I think I am starting to understand that notion but what can I do when the problem has already substituted t for something else. Can I just perform the same operation?

    Here is a problem I am working on ... using your method.

    F(n+3) = 2F(n+1) + F(n)

    let n = n-2

    F([n-2] + 3) = F([n-2]+1) + F([n-2]+1) + F(n-2)
    F(n+1) = [F(n-1) + F(n-1)] + F(n-2)
    F(n) + F(n-1) = F(n) + F(n-1) CHECK


    does that work as I think it does?
    You may do it as many times as your little heart desires.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Newbie
    Joined
    Oct 2008
    Posts
    13
    Quote Originally Posted by Drexel28 View Post
    You may do it as many times as your little heart desires.

    Oh bless your heart. Most hated phrase you will here in a scrapebook shop. Thanks again for all your direction.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving linearity property of the integral.
    Posted in the Calculus Forum
    Replies: 2
    Last Post: May 17th 2010, 05:19 AM
  2. Need help with proving transitivity property
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 9th 2010, 07:13 AM
  3. Proving a Property of Integrals
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 11th 2009, 07:31 AM
  4. Need help proving basic property of tensors
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: October 24th 2009, 10:53 AM
  5. Proving the second property of Density Functions
    Posted in the Advanced Statistics Forum
    Replies: 5
    Last Post: May 24th 2009, 02:30 AM

Search Tags


/mathhelpforum @mathhelpforum