Is this induction proof correct?

  • Thread starter johann1301
  • Start date
  • #1
217
1

Homework Statement



The sequence {xn} is given by the recurrence relation

xn = cos(xn-1)sin(xn-2) for n ≥ 2

and x0=2 and x1=1,4. Show by induction that 0 ≤ xn ≤ 1 for all integers n ≥ 2.

The Attempt at a Solution



We formulate a statement:

Pn: 0 ≤ xn = cos(xn-1)sin(xn-2) ≤ 1 for n ≥ 2
---------------------------------------------------------------

We assume that Pn is true for n=k, where k ≥ 2:

Ak: 0 ≤ xk = cos(xk-1)sin(xk-2) ≤ 1 for k ≥ 2

We then set n=k+1:

xk+1 = cos(xk)sin(xk-1)

We know from the assumption Ak that:

0 ≤ xk ≤ 1

This implies that:

0,54 ≤ cos(xk) ≤ 1 which again implies 0 < cos(xk) < 1

We then have to show:

0 ≤ sin(xk-1) ≤ 1

We know that sine to any angle is always equal to or less then 1. We therefore have to prove:

0 ≤ sin(xk-1)

Since we assumed that 0 ≤ xk ≤ 1, this must be true for xk-1 as well. This means that if the assumption Ak is true when n=k, its true when n=k+1 also. The last thing is to prove the base case:

x2 = cos(1,4)sin(2) ≈ 0,155

0 ≤ 0,155 ≤ 1

Pn is thus true.

Is this correct argumentation?
 

Answers and Replies

  • #2
120
6
I'm trying to follow along, but how is it that

[itex]0 \leq x_k \leq 1 \Rightarrow 0.54 \leq cos(x_k) \leq 1 [/itex]?

Also, are you trying to use strong induction or weak induction?
 
  • #3
217
1
I'm trying to follow along, but how is it that

[itex]0 \leq x_k \leq 1 \Rightarrow 0.54 \leq cos(x_k) \leq 1 [/itex]?

Also, are you trying to use strong induction or weak induction?
Strong induction.

Since the value of xk is always between 0 and 1 radians, the value of cos(xk) has to lie between cos(1)≈0.5403... and cos(0)=1. If you plot cos(x) from x=0 to x=1 you will see that the values of cos(x) lies between 0.5403 and 1.
 
  • #4
Fredrik
Staff Emeritus
Science Advisor
Gold Member
10,851
412
We formulate a statement:

Pn: 0 ≤ xn = cos(xn-1)sin(xn-2) ≤ 1 for n ≥ 2
You shouldn't write out the definition of ##x_n## in the middle of your definition of ##P(n)##. Just say that for each integer n such that ##n\geq 2##, P(n) is the statement ##0\leq x_n\leq 1##. Your goal is to prove P(n) for all integers n such that ##n\geq 2##. To do this by induction is to prove the following two statements:

##P(2)##
For all integers n such that ##n\geq 2##, if P(n) then P(n+1).

We assume that Pn is true for n=k, where k ≥ 2:
This is poorly worded. It sounds like you're talking about some specific but unspecified integer k that's greater than or equal to 2. So you're saying that one of the infinitely many statements P(2), P(3), etc. is true, and you're not saying which one. I can't interpret the statement as a "for all k" statement either, because then it would be saying that all of the statements P(2), P(3), etc. are true. This is the result that you're trying to prove.

What you need to say here is this: Let n be an arbitrary integer such that n≥2. We will prove that if P(n) then P(n+1). So suppose that P(n) is true.

Note however that this is not sufficient to prove the theorem. You also need to prove P(2).
 

Related Threads on Is this induction proof correct?

  • Last Post
Replies
3
Views
586
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
823
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
1K
Replies
2
Views
1K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
1
Views
961
Top