Induction question (1 Viewer)

[apollo1]

culd someone help me with this induction question:

 

[evanstroeve]

 

[evanstroeve]

I'm assuming the first two steps were done okay?
Making the substitution from assumption in step 2, in line 3

 

[apollo1]

wat do you do when you prove true for n = 1?
bcuz i keep getting P1 = 1 and Q1 = 1 and they arent unique.

 

[evanstroeve]

Oh yeah, not sure about that. They're unique for n=2, n=3 etc. Doesn't restrict n such that some where in the question?

 

[largarithmic]

That doesn't prove uniqueness. You have to add another second part of the proof to prove uniqueness.

Suppose for a contradiction that for some n>=1, there exist distinct ordered pairs of integers (p,q) and (r,s) such that:


Now clearly q=/=s; if q were to equal s, then p = r, so (p,q) and (r,s) would be the same ordered pair. Hence we deduce q-s =/= 0, and so rearranging the above:

Which would imply that the square root of 2 were rational since p,q,r,s are integers with s-q nonzero. This is clearly a contradiction of the original assumption that distinct pairs (p,q) and (r,s) existed; so there is a unique pair (p,q).

 

[apollo1]

largarithmic wat is wrong with evanstroeve's method?

 

[evanstroeve]

That doesn't prove uniqueness. You have to add another second part of the proof to prove uniqueness.

Suppose for a contradiction that for some n>=1, there exist distinct ordered pairs of integers (p,q) and (r,s) such that:


Now clearly q=/=s; if q were to equal s, then p = r, so (p,q) and (r,s) would be the same ordered pair. Hence we deduce q-s =/= 0, and so rearranging the above:

Which would imply that the square root of 2 were rational since p,q,r,s are integers with s-q nonzero. This is clearly a contradiction of the original assumption that distinct pairs (p,q) and (r,s) existed; so there is a unique pair (p,q).

I get the jist of what you're saying. But aren't Pk+1 and Qk+1 unique for all k?
But the question asks for a method "using induction", how would you solve our problem with the step n = 1?

 

[largarithmic]

I get the jist of what you're saying. But aren't Pk+1 and Qk+1 unique for all k?
But the question asks for a method "using induction", how would you solve our problem with the step n = 1?

No. The problem explicitly asks to to prove there are unique Pk and Qk. What that then means is you have to show there aren't two different possible solutions for them. You don't need induction for this, and any use of induction is probably a bit silly; so when n=1, you just say "let (p,q) and (r,s) be two distinct ordered pairs of positive integers such that 1+root2 = p+qroot2 = r+sroot2" and proceed as above. You essentially use induction to show there exist Pk and Qk, but then you do the short thing I mentioned to do with irrationality to prove they are unique.

The serious problem, Apollo1, with the method is that he's actually assuming uniqueness to do the problem. He gets to this step:

And then concludes that implies Pk+1 = Pk + 2Qk and Qk+1 = Pk + Qk.

That's subtly but seriously wrong: because when you do that you assume that there are unique integers P and Q s.t. P + Qroot2 = M, where M is whatever number (here (1+root2)^(k+1)) that you're dealing with. And you can't just assume that with the inductive step.

 

[Trebla]

The proof for n = k + 1 is based on the assumption that p_k and q_k are unique when n = k by the nature of the induction proof.

If you assume p_k and q_k are unique then doesn't that imply that (p_k + 2q_k) and (p_k + q_k) are also unique if the assumption holds (given p and q are positive integers)? If so, then the only issue is proving uniqueness for n = 1 to verify the assumption.

 

[seanieg89]

The proof for n = k + 1 is based on the assumption that p_k and q_k are unique when n = k by the nature of the induction proof.

If you assume p_k and q_k are unique then doesn't that imply that (p_k + 2q_k) and (p_k + q_k) are also unique if the assumption holds (given p and q are positive integers)? If so, then the only issue is proving uniqueness for n = 1 to verify the assumption.

 

[largarithmic]

The proof for n = k + 1 is based on the assumption that p_k and q_k are unique when n = k by the nature of the induction proof.

If you assume p_k and q_k are unique then doesn't that imply that (p_k + 2q_k) and (p_k + q_k) are also unique if the assumption holds (given p and q are positive integers)? If so, then the only issue is proving uniqueness for n = 1 to verify the assumption.

seanieg89 is completely right, although you have unique Pk and Qk assumed, you need to prove that there isnt a different P(k+1) and Q(k+1) that DOESNT satisfy the recurrence relation (obviously if it satisfied that same recurrence that'd be fine, but you need to check that it doesnt).

seanieg89 do you know if you can just say that at HSC level and not do a thing where rearrange to get root2 = rational stuff? Its not much extra anwyay

 

[seanieg89]

Not a clue, personally I would do the extra work to be safe...the BOS is kind of unpredictable in their expectations of rigour.