Prove by induction

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Rhombic
Posts: 58
Joined: Wed Jan 01, 2014 11:42 pm UTC

Prove by induction

Postby Rhombic » Sun Apr 05, 2015 6:07 pm UTC

Given
[math]T_{n+1}={T_n}^2-T_n+1[/math]
and T0=2,

prove that

[math]\forall p\neq q \textup{GCD}(T_p,T_q)=1[/math]

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Prove by induction

Postby Qaanol » Sun Apr 05, 2015 7:27 pm UTC

Rhombic wrote:Given
[math]T_{n+1}={T_n}^2-T_n+1[/math]
and T0=2,

prove that

[math]\forall p\neq q \textup{GCD}(T_p,T_q)=1[/math]

Let me write those formulæ in bbcode:
T0 = 2
Tk+1 = Tk2 - Tk + 1

And you want to show by induction that the Tn are relatively prime.

Is this homework?
Last edited by Qaanol on Sun Apr 05, 2015 7:40 pm UTC, edited 2 times in total.
wee free kings

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Prove by induction

Postby Tirian » Sun Apr 05, 2015 7:38 pm UTC

Can you prove that Tn and Tn+1 are relatively prime for any n? Can you prove that Tn and Tn+2 are relatively prime for any n?

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Prove by induction

Postby Qaanol » Sun Apr 05, 2015 7:41 pm UTC

Also, have you tried listing out the first, say 10 or so terms to see if the conclusion holds for small n?

Because you should probably do that.

Edit: The proof is actually quite straightforward once you recognize the pattern.
wee free kings

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Prove by induction

Postby Cauchy » Mon Apr 06, 2015 5:54 am UTC

Like with many induction proofs, this problem can become simpler if you attempt to show a stronger statement. Specifically,

Spoiler:
For p < q, T_q is congruent to 1 mod T_p
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 9 guests