Using second Principle of Mathematical Induction Proof

  • #1
renolovexoxo
25
0

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.
 

Answers and Replies

  • #2
Bacle2
Science Advisor
1,089
10
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 .
 
  • #3
renolovexoxo
25
0
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?
 
  • #4
Bacle2
Science Advisor
1,089
10
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.
 
  • #5
Bacle2
Science Advisor
1,089
10
Sorry if I was too abstruse.

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

for any j.
 
  • #6
HallsofIvy
Science Advisor
Homework Helper
43,010
969

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.
 
  • #7
renolovexoxo
25
0
So in the case, what would I consider k and j? Would i let n=k to finish this proof?
 
  • #8
Bacle2
Science Advisor
1,089
10
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?
 
  • #10
renolovexoxo
25
0
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.
 
  • #11
Fredrik
Staff Emeritus
Science Advisor
Gold Member
10,872
420
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.
 
Last edited:
  • #12
renolovexoxo
25
0
Thank you. That makes a lot more sense now.
 

Suggested for: Using second Principle of Mathematical Induction Proof

Replies
5
Views
2K
Replies
4
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
4
Views
543
  • Last Post
Replies
16
Views
3K
Replies
0
Views
4K
Replies
1
Views
2K
Replies
1
Views
1K
Replies
7
Views
2K
Top