Page 7 of 7 FirstFirst ... 34567
Results 91 to 94 of 94

Math Help - Prove some identities! (Round two)

  1. #91
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by Bruno J. View Post

    Here's an easy problem I made up : show that, for any positive integer n, we have

    \displaystyle \sum_{k=2}^\infty\lfloor \log_k n\rfloor = \sum_{k=1}^\infty \lfloor n^{1/k}-1\rfloor
    Simply put -since the sums are finite: \displaystyle\sum_{k=1}^{\infty}{\lfloor \log_k n\rfloor} = \sum_{k=2}^{\infty}{\left(\sum_{k^r \leq n ; r\geq 1} 1 \right) } = \sum_{r\geq 1}\left(\sum_{k^r\leq n; k\geq 2}1\right)

    And we are done since \displaystyle\sum_{k^r\leq n; k\geq 2}1 = \lfloor n^{1/r}-1\rfloor


    Now a couple of problems:

    1. Show that: \displaystyle\sum_{k=1}^n{\frac{d(k)}{k}} = \tfrac{1}{2}\cdot \log^2(n)+ O\left(\log(n)\right) (*)
    2. Show that: \displaystyle\sum_{k=0}^{n}{\binom{n}{k}\cdot (n-k)^{n-2}\cdot (-1)^k} = 0 for all n\in \{2,3,4,...\} (**)

    (*) Here d(k) is the number of positive integers dividing k.
    (**) For the case n=2 to work, we write 0^0 = 1
    Follow Math Help Forum on Facebook and Google+

  2. #92
    Member
    Joined
    Nov 2009
    Posts
    106
    Quote Originally Posted by PaulRS View Post
    2. Show that: \displaystyle\sum_{k=0}^{n}{\binom{n}{k}\cdot (n-k)^{n-2}\cdot (-1)^k} = 0 for all n\in \{2,3,4,...\}
    I'll assume n\ge 3. For n=2 it can be checked directly.

    Let

    \displaystyle{<br />
f(x)=\sum_{k=0}^n \binom{n}{k}x^k = (1+x)^n<br />
}

    Then

    \displaystyle{<br />
xf'(x)=\sum_{k=0}^n \binom{n}{k}kx^k<br />
}

    Differentiating more, it's easily seen that

    <br />
\displaystyle x(x(xf')'\cdots)' = \sum_{k=0}^n\binom{n}{k}P_m(k)x^k}

    Where on the left side we have m differentiations and on the right side P_m are polynomials of degree m.

    As such, \{P_0,P_1,P_2,\cdots,P_{n-2}\} form a basis to the vector space of polynomials of degree at most n-2. Therefore,

    \displaystyle{<br />
\sum_{k=0}^n \binom{n}{k}(n-k)^{n-2}x^k=\sum_{k=0}^n \binom{n}{k}k^{n-2}x^k<br />
}

    is a linear combination of

    <br />
(1)\;\;\;f,\; xf',\; x(xf')'\;\cdots\;, x(x(xf')'\cdots)'<br />

    up to n-2 times differentiation.

    But since the zero of f at -1 is of order n, we have that all the functions in (1) evaluated at -1 vanish, and thus their linear combination evaluated at that point,

    \displaystyle\sum_{k=0}^n \binom{n}{k}(n-k)^{n-2}(-1)^k

    also does.
    Follow Math Help Forum on Facebook and Google+

  3. #93
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by PaulRS View Post
    1. Show that: \displaystyle\sum_{k=1}^n{\frac{d(k)}{k}} = \tfrac{1}{2}\cdot \log^2(n)+ O\left(\log(n)\right)
     \displaystyle \sum_{n\leq x} d(n) = \sum_{n\leq x} \left\lfloor\frac xn\right\rfloor = \sum_{n\leq x} \frac xn -\sum_{n\leq x}\left\{\frac xn\right\}

     \displaystyle = x\left(\log x +\gamma x +O\left(\tfrac1x\right)\right) + O(x) = x\log x + O(x) .

    Now use Abel's summation to get

     \displaystyle \sum_{n\leq x} \frac{d(n)}n = \frac{x\log x + O(x)}x + \int_1^x \frac{\log t}t dt + O\left(\int_1^x \frac1t dt\right)

     \displayatyle = \frac12\log^2x + O\left(\log x\right) .

    -------

    Now I'll do you one better.

    It can be shown via the Dirichlet hyperbola method that  \displaystyle \sum_{n\leq x} d(n) = x\log x + (2\gamma-1)x + O\left(\sqrt{x}\right) .

    Now use Abel's summation to get

     \displaystyle \sum_{n\leq x} \frac{d(n)}n = \frac{x\log x + (2\gamma-1)x + O\left(\sqrt{x}\right)}x + \int_1^x \frac{\log t}t dt + \int_1^x \frac{2\gamma-1}t dt + O\left(\int_1^x t^{-3/2} dt\right)

     \displayatyle = \frac12\log^2x + 2\gamma\log x + O(1) .
    Last edited by chiph588@; February 6th 2011 at 11:29 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #94
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    My solutions:

    1.
    First proof: Consider the set of functions from a set A\to B.
    If we fix a subset S\subseteq B we have that the number of functions from A\to B such that f(A)\subseteq B - S is \left( |B| - |S|\right)^{|A|} so in fact what we are counting (in the original equation) by inclusion-exclusion is the number of functions such that f(A)\supseteq B which is of course absurd since in this case |f(A)|\leq  |A| = n-2<|B| = n

    Remark: If |A|=|B|=n we get n! = \displaystyle\sum_{k=0}^n{\binom{n}{k}\cdot (n-k)^n\cdot (-1)^k}, setting n = p-1 and using Fermat's Little Theorem + The Binomial Theorem we get a proof of Wilson's Theorem.


    Second Proof: The number of labeled trees with n vertices such that a given set -you choose it- of k labels correspond to leaves is (n-k)^{n-2}, so in fact what \displaystyle\sum_{k=0}^n{\binom{n}{k}\cdot (n-k)^{n-2}\cdot (-1)^k} is counting is the number of trees with no leaves, of course, if there are vertices this number will be 0.

    2. We write : \displaystyle\sum_{k=1}^n{\frac{d(k)}{k}}= \sum_{k=1}^n{\tfrac{1}{k}\cdot \sum_{d|k}{1}} = \sum_{d=1}^n{\sum_{d|k}{\tfrac{1}{k}}} = \sum_{d=1}^n{\tfrac{1}{d}\cdot H_{\left\lfloor \tfrac{n}{d} \right\rfloor}} where H_n = 1  + \tfrac{1}{2}+...+\tfrac{1}{n} , estimating this the rest follows.
    Follow Math Help Forum on Facebook and Google+

Page 7 of 7 FirstFirst ... 34567

Similar Math Help Forum Discussions

  1. Can't prove these identities?
    Posted in the Trigonometry Forum
    Replies: 6
    Last Post: November 20th 2010, 07:07 AM
  2. prove the following identities.
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: June 22nd 2010, 11:15 PM
  3. Prove Identities
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: January 26th 2010, 10:42 PM
  4. Prove these identities.
    Posted in the Trigonometry Forum
    Replies: 5
    Last Post: July 20th 2009, 09:42 PM
  5. help Prove identities
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: March 29th 2009, 07:39 AM

Search Tags


/mathhelpforum @mathhelpforum