Waste less time on Facebook — follow Brilliant.

Question from Elementary Number Theory by David M. Burton


I was solving the \(3rd\) question from the \(1st\) chapter from the book. I squeezed my brain but I'm unable to figure out how to start proving this.

Any help is welcome.

The Problem:

Use the Second Principle of Finite Induction to establish that \[ a^n-1=(a-1)(a^{n-1}+a^{n-2}+a^{n-3}+...+a+1) \] for all \(n>=1\). [Hint: \(a^{n+1}-1=(a+1)(a^n-1)-a(a^{n-1}-1))\) ]

(P.S. I don't need complete proof, I just want to know how to start. If I'm too noob to figure out things after that, I'll ask for complete solution if some would kindly provide :) )

Note by Kou$htav Chakrabarty
3 years, 7 months ago

No vote yet
1 vote


Sort by:

Top Newest

That seems like a pretty ridiculous hint! If I were going to use induction I'd use \( a^{n+1}-1 = (a^n-1) + a^n(a-1) \) and then substitute the expansion in using the inductive hypothesis. Much cleaner.

Patrick Corn - 3 years, 7 months ago

Log in to reply

Hi Patrick On a different matter can you prove for me that if the sum of two perfect squares is a perfect square then their difference can not be a perfect square Enjoy reading your solutions Des O Carroll

Des O Carroll - 3 years, 7 months ago

Log in to reply

I'm not sure you're going to like this answer, Des! But here goes. Suppose \( a^2+b^2=c^2 \) and \( a^2-b^2 = d^2 \). This describes a curve in projective \( 3 \)-space (cut out by the intersection of two planes).

Set \( y = 2b \), \( x = 2(a-d) \), \( z = 2a-c-d \) for all points on the curve except \( (1,0,1,1). \) If \( (a,b,c,d) = (1,0,1,1), \) set \( (x,y,z) = (0,1,0). \) Then if I did the algebra right, \( x,y,z \) satisfy the equation \( y^2z= x(x-z)(x-2z). \) You may recognize this as an elliptic curve, and in fact this map gives an isomorphism between your original curve and the elliptic curve. Standard elliptic curve methods show that this curve has rank 0 and exactly four torsion points: \( (0,1,0) \) plus the three points \( (a,0,1) \) where \( a = 0,1,2 \). These points correspond to the points \( (1,0,\pm 1, \pm 1) \) on the original curve. So the only rational solutions to your original equations are the "trivial" ones where \( b = 0 \).

This is kind of a punt because the "standard elliptic curve methods" are pretty deep. It's not hard to find the torsion subgroup, but showing that the rank is 0 is in general pretty tricky. I actually used a computer algebra system to verify this, but I'm sure there is a down-to-earth way to do it as well for this specific example.

Sorry if I did the algebra wrong! I am sure that the original curve and my elliptic curve are isomorphic (computer algebra system again!), but I haven't checked for sure that my isomorphism is correct.

Patrick Corn - 3 years, 7 months ago

Log in to reply

@Patrick Corn Many thanks Patrick Im afraid that much of the solution is beyond me but it confirms that this is quite a difficult problem not accessible to an easy solution Anyway it was so kind of you to get back to me so quickly and thanks again Des O Carroll

Des O Carroll - 3 years, 7 months ago

Log in to reply

After proving the base cases for \(n=1,2\), plug in the expansion of \(a^{n}-1\) and \(a^{n-1}-1\) (this is valid due to the induction assumption) in the formula given in the hint to get the result for \(a^{n+1}-1\).

Abhishek Sinha - 3 years, 7 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...