wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> sum phi(n)/(2^n - 1)
        
(Message started by: Eigenray on Sep 9^th, 2009, 9:23pm)

Title: sum phi(n)/(2^n - 1)
Post by Eigenray on Sep 9^th, 2009, 9:23pm

Evaluate:
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_n=1^{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supinfty.gif} [link=http://en.wikipedia.org/wiki/Euler%27s_totient_function]http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(n)[/link]/(2ⁿ-1)

Title: Re: sum phi(n)/(2^n - 1)
Post by william wu on Sep 13^th, 2009, 2:43pm

Here is an upper bound ~~that matches numerical calculation of the limit~~ (thanks Eigenray):

[hideb]

We first prove the following inequality: n/2ⁿ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gifphi(n)/(2^n - 1) for n > 1.
By rearranging, the inequality we wish to show can be rewritten as 1 - (1/2)^n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gifphi(n)/n.
This holds since

phi(n)/n
= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif_p|n (1-1/p)
<= 1-1/n
<= 1 - (1/2)^n
where the first inequality holds since n>1, and the second inequality holds since n <= 2^n.

Thus, applying this inequality to every term of our series except the first term, we have

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_{n=1 to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif} phi(n) / (2^n - 1)
<= 1 + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_{n=2 to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif} n/2ⁿ
= 1 + -1/2 + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_{n=1 to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif} n/2ⁿ
= 2.5

In the last equality, the sum http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifn/2^n can be evaluated by using the trick of differentiating the geometric series http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifx^n = 1/(1-x) when |x|<1. In this way, we can show that http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_{n=1 to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif} n x^n = x/(1-x)^2, which evaluates to 2 when x = 1/2.

[/hideb]

Title: Re: sum phi(n)/(2^n - 1)
Post by Eigenray on Sep 13^th, 2009, 5:41pm

The only way the upper bound could be sharp is if it were sharp term by term, which it isn't. The upper bound you give is actually
1 - 1/2 + 2 = 2.5

Hint: I intentionally made the problem more difficult by making it 'easier', i.e., asking for less information.

Title: Re: sum phi(n)/(2^n - 1)
Post by Eigenray on Sep 21^st, 2009, 2:04am

Here is the 'harder' (easier) version: if x > 1, evaluate:
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(n)/(xⁿ-1)