# Proving a property of a definition

• Jan 6th 2010, 06:37 PM
mcox05
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.
• Jan 6th 2010, 07:01 PM
Drexel28
Quote:

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?
• Jan 6th 2010, 08:53 PM
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.
• Jan 6th 2010, 08:54 PM
Drexel28
Quote:

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 $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.
• Jan 6th 2010, 09:36 PM
mcox05
Quote:

Originally Posted by Drexel28
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.
• Jan 6th 2010, 09:44 PM
Drexel28
Quote:

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 $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.
• Jan 6th 2010, 11:50 PM
mcox05
Quote:

Originally Posted by Drexel28
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.
• Jan 7th 2010, 04:06 AM
emakarov
Quote:

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.
• Jan 7th 2010, 08:56 AM
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.
• Jan 7th 2010, 01:55 PM
Drexel28
Quote:

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? $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$
• Jan 7th 2010, 02:10 PM
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.
• Jan 7th 2010, 02:13 PM
Drexel28
Quote:

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 $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)$
• Jan 7th 2010, 03:26 PM
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?
• Jan 7th 2010, 04:11 PM
Drexel28
Quote:

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.
• Jan 7th 2010, 04:26 PM
mcox05
Quote:

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.