Can anyone help me to solve this problem:
Consider as a natural number greater than . Prove that sum of all numbers of the form with the condition ( and are relatively prime) and and is always equal to
Can anyone help me to solve this problem:
Consider as a natural number greater than . Prove that sum of all numbers of the form with the condition ( and are relatively prime) and and is always equal to
Rule #10: Do not beg for answers. If your question is unanswered do not make a post begging for someone to reply back, it is totally useless. Other members can see the question.
But what should i do? I need the answer. I would wonder if anyone help me.
Thnx
Here's where I started. The problem states that for all , , for
Base case : , so
Look at
See if you can notice the pattern. First of all, most pairs stay in the set when moving from to . This is because if they are relatively prime, this has nothing to do with . So, consider the pairs we gain advancing from to , and consider the pairs we lose.
Gain: From to , we gain all pairs
Lose: From to , we lose all pairs
Consider . I observe exactly three cases...
Case 1: , n brings no new factors, so the only pair lost is and the only pairs gained are Example
Case 2: If is prime, . Since n brings exactly one new factor, the pairs gained are and the pairs lost are those of the form for all Example
Case 3: If n is a power of a prime , . So n brings the same gains/losses as case 2, excepting the pairs where the prime (sorry, poor choice of notation). Example
The idea of this approach is that since most of the pairs stay the same, their "part" of the sum remains unchanged. So in jumping from n-1 to n, the part of the sum subtracted from the lost pairs must balance perfectly the part of the sum added by the gained pairs. So for case 1 it is easy to verify the algebraic identity
For case 2, we have the more complicated for n prime
Case 3 is the more complicated formula from my last post. It can easily be seen that case 2 is a special case of 3 for k=1. So if we can prove case 3 the problem is done. However, it may be easier to tackle 2 first to gain enough insight to do 3.