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

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]

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

Re: Prove by induction

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

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?

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

Re: Prove by induction

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

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.