Using second Principle of Mathematical Induction Proof

[renolovexoxo]

Homework Statement

Let F: N->N be defined by f(1)=1 and f(2)=2 and f(n+2)=1/2(f(n+1)+f(n))

Use Theorem 1.3 to prove that 1<=f(n)<=2 for all n in N

Homework Equations

For each n in N let P(n) be a statement about the positive integer n. If a) P(1) is true, and b) for k>1, P(k) is true whenever P(j) is true for all positive integers j<k, then P(n) is true for all n in N.

The Attempt at a Solution

I honestly don't really know how to even start this one. I have a hard time understanding what the theorem is even saying, so I don't know how to apply it.

 

[Bacle2]

Let' s see. Let's first parse the statement:

P(n) is the statement 1<=f(n)<=2 , so, e.g., P(3) is the statement 1<=P(3)<=2 ,

etc.

You're asked to show that if for any general number k>1 , it follows that

1<= f(n) <= 2 for all n in {1,2,...,k-1} , i.e., for any pos. integer you select,

you have that (and your job is to show that for any k you do have this) :

1) 1<=f(1)<=2
2) 1<=f(1)<=2
...
...
k-1) 1<= f(k-1)<=2

Then, you can conclude that ,for any number , say',s', that :

1<=f(s) <=2 .

 

[renolovexoxo]

I'm having trouble with how I am supposed to prove it without knowing the f(n) that is being used. Is there some part of the theorem that I'm missing that would help me with that aspect of this proof?

 

[Bacle2]

True that you don't know f(n), but you know some properties of it (recursively-

defined),from the first line in your original post.

 

[Bacle2]

Sorry if I was too abstruse.

Try maybe showing it for some specific numbers n, and see how to generalize it

for any j.

 

[HallsofIvy]

Homework Statement

Let F: N->N be defined by f(1)=1 and f(2)=2 and f(n+2)=1/2(f(n+1)+f(n))

So f(1)= 1 which is between 1 and 2 (inclusive). f(2)= 2 which is between 1 and 2 (inclusive). f(3)= f(1+ 2)= (1/2)(f(2)+ f(1))= (1/2)(2+1)= 3/2 which is between 1 and 2.
f(4)= (1/2)(f(3)+ f(2))= (1/2)(3/2+ 2)= (1/2)(7/2)= 7/4= 1 and 3/4 which is between 1 and 2.
f(5)= (1/2)(f(4)+ f(3))= (1/2) (7/4+ 3/2)= (1/2)(13/4)= 13/8= 1 and 5/8 which is between 1 and 2.

That's what it is saying!

Use Theorem 1.3 to prove that 1<=f(n)<=2 for all n in N

Homework Equations

For each n in N let P(n) be a statement about the positive integer n. If a) P(1) is true, and b) for k>1, P(k) is true whenever P(j) is true for all positive integers j<k, then P(n) is true for all n in N.

The Attempt at a Solution

I honestly don't really know how to even start this one. I have a hard time understanding what the theorem is even saying, so I don't know how to apply it.

 

[renolovexoxo]

So in the case, what would I consider k and j? Would i let n=k to finish this proof?

 

[Bacle2]

So f(1)= 1 which is between 1 and 2 (inclusive). f(2)= 2 which is between 1 and 2 (inclusive). f(3)= f(1+ 2)= (1/2)(f(2)+ f(1))= (1/2)(2+1)= 3/2 which is between 1 and 2.
f(4)= (1/2)(f(3)+ f(2))= (1/2)(3/2+ 2)= (1/2)(7/2)= 7/4= 1 and 3/4 which is between 1 and 2.
f(5)= (1/2)(f(4)+ f(3))= (1/2) (7/4+ 3/2)= (1/2)(13/4)= 13/8= 1 and 5/8 which is between 1 and 2.

That's what it is saying!

What do you mean by that's what it is saying? Are you referring to my post?

 

[Bacle2]

So in the case, what would I consider k and j? Would i let n=k to finish this proof?

I don't think I can explain it much better than they do in here:

http://en.wikipedia.org/wiki/Mathematical_induction#Complete_induction

Look up the section.

 

[renolovexoxo]

I'm sorry, but I still don't really understand what it is saying. I've read it several times and really am having a hard time. We didn't go over any examples of anything like this in class.

 

[Fredrik]

The problem defines a sequence f(1), f(2),... and is asking you to prove that all the terms of that sequence is in the interval [1,2]. So you need to prove the infinitely many statements:
f(1) is in [1,2]
f(2) is in [1,2]
...
The theorem that you included under "relevant equations" is telling you that you can do that by proving only two statements. This saves you an infinite amount of time. That's the whole point of induction. If we call the statements above P(1), P(2), and so on, the two statements you have to prove are:

P(1) is true.
For all positive integers n, if P(k) is true for all integers k<n, then P(n) is true.

I'm sure you will have no problems with the first of these statements. The proof of the second statement would typically start with "Let n be an arbitrary positive integer such that P(k) is true for all positive integers k<n." To complete the proof, you just need to show that P(n) is true.

 

[renolovexoxo]

Thank you. That makes a lot more sense now.