• Support PF! Buy your school textbooks, materials and every day products Here!

Using second Principle of Mathematical Induction Proof

  • #1

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
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
41,833
955

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
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
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,851
407
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
Thank you. That makes a lot more sense now.
 

Related Threads on Using second Principle of Mathematical Induction Proof

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