Thread: 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.

Originally Posted by mcox05

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?

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.

Originally Posted by mcox05

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 in is just a place holder. For example, let then you would no doubt agree with me saying that , or equivalently . Proceed.

Originally Posted by Drexel28

The in is just a place holder. For example, let then you would no doubt agree with me saying that , or equivalently . 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.

Originally Posted by mcox05

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 can be decomposed into , and that then each of can be decomposed into ....keep doing this and you'll notice that you can decompose into an expression like . Guess what some number and some other number will be.

Originally Posted by Drexel28

Think about it like this. Do you see that each can be decomposed into , and that then each of can be decomposed into ....keep doing this and you'll notice that you can decompose into an expression like . 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.

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 implies 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 implies for any , and , but not conversely.

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.

Originally Posted by mcox05

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?

Also, it may be useful to learn that

Where is the positive solution to

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.

Originally Posted by mcox05

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 can stand for anything( to a point) in . Let and this becomes

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?

Originally Posted by mcox05

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.

Originally Posted by Drexel28

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.