Problem: n n 7 7 n + 1 7 7 n + 1 2 n + 3 2 n + 3
Solution:
The proof is by induction. The base is provided by the n = 0 n = 0 7 7 0 + 1 = 7 1 + 1 = 2 3 7 7 0 + 1 = 7 1 + 1 = 2 3 x = 7 2 m − 1 x = 7 2 m − 1 m m ( x 7 + 1 ) / ( x + 1 ) ( x 7 + 1 ) / ( x + 1 ) x 7 + 1 x 7 + 1 x + 1 x + 1 ( x 7 + 1 ) / ( x + 1 ) ( x 7 + 1 ) / ( x + 1 )
x 7 + 1 x + 1 = ( x + 1 ) 7 − ( ( x + 1 ) 7 − ( x 7 + 1 ) ) x + 1 = ( x + 1 ) 6 − 7 x ( x 5 + 3 x 4 + 5 x 3 + 5 x 2 + 3 x + 1 ) x + 1 = ( x + 1 ) 6 − 7 x ( x 4 + 2 x 3 + 3 x 2 + 2 x + 1 ) = ( x + 1 ) 6 − 7 2 m ( x 2 + x + 1 ) 2 = { ( x + 1 ) 3 − 7 m ( x 2 + x + 1 ) } { ( x + 1 ) 3 + 7 m ( x 2 + x + 1 ) } x + 1 x 7 + 1 ​ ​ = x + 1 ( x + 1 ) 7 − ( ( x + 1 ) 7 − ( x 7 + 1 ) ) ​ = ( x + 1 ) 6 − x + 1 7 x ( x 5 + 3 x 4 + 5 x 3 + 5 x 2 + 3 x + 1 ) ​ = ( x + 1 ) 6 − 7 x ( x 4 + 2 x 3 + 3 x 2 + 2 x + 1 ) = ( x + 1 ) 6 − 7 2 m ( x 2 + x + 1 ) 2 = { ( x + 1 ) 3 − 7 m ( x 2 + x + 1 ) } { ( x + 1 ) 3 + 7 m ( x 2 + x + 1 ) } ​
Also each factor exceeds 1 . It suffices to check the smaller one; 7 x ≤ x 7 x ​ ≤ x
( x + 1 ) 3 − 7 m ( x 2 + x + 1 ) = ( x + 1 ) 3 − 7 x ( x 2 + x + 1 ) ≥ x 3 + 3 x 2 + 3 x + 1 − x ( x 2 + x + 1 ) = 2 x 2 + 2 x + 1 ≥ 113 > 1 ( x + 1 ) 3 − 7 m ( x 2 + x + 1 ) ​ = ( x + 1 ) 3 − 7 x ​ ( x 2 + x + 1 ) ≥ x 3 + 3 x 2 + 3 x + 1 − x ( x 2 + x + 1 ) = 2 x 2 + 2 x + 1 ≥ 1 1 3 > 1 ​
Hence ( x 7 + 1 ) / ( x + 1 ) ( x 7 + 1 ) / ( x + 1 )
This problem was suggested by Titu Andreescu.
The problems on this page are the property of the MAA's American Mathematics Competitions