Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By Plato

Thread: Functions

  1. #1
    No one in Particular VonNemo19's Avatar
    Joined
    Apr 2009
    From
    Detroit, MI
    Posts
    1,849

    Functions

    Let $d:\mathbb{N}\rightarrow\mathbb{N}$ where$d(n)$ is the number of natural divisors of $n$. Prove that for all $n$, $d(2^{n-1})=n$. (I formulated this conjecture myself. So, if it's nonsensical let me know.)

    Induction:


    Base: let $n=1$. Then $d(2^{1-1})=1$.

    Now assume for some $k\in\mathbb{N}$, $d(2^{k-1})=k$. Then the number of natural divisors of $2^{k-1}$ can be listed as follows:
    $2^0,2^1,2^2,...,2^{k-1}$. Multiplying each divisor by 2 gives the list $2^1,2^2,..,2^{k-1},2^{(k+1)-1}$. But these are the divisors of $2^{(k+1)-1}$ without​ $1$. Thus $d(2^{(k+1)-1})=d(2^{k-1})+1=k+1$ as desired.
    Therefore by the principle of induction, $d(2^{k-1})=k$.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,153
    Thanks
    2605
    Awards
    1

    Re: Functions

    Quote Originally Posted by VonNemo19 View Post
    Let $d:\mathbb{N}\rightarrow\mathbb{N}$ where$d(n)$ is the number of natural divisors of $n$. Prove that for all $n$, $d(2^{n-1})=n$. (I formulated this conjecture myself. So, if it's nonsensical let me know.)
    It is far from nonsensical! In fact it is well known.
    If ${\large n=2^{p}\cdot3^{q}\cdot5^{r}\cdot7^{s}\cdot11^{t}}$ then $d(n)=(p+1)\cdot(q+1)\cdot(r+1)\cdot(s+1)\cdot(t+1 ).$
    Thanks from VonNemo19
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: Mar 30th 2012, 05:36 PM
  2. Replies: 0
    Last Post: Apr 15th 2010, 05:50 PM
  3. Replies: 3
    Last Post: Feb 23rd 2010, 05:54 PM
  4. Replies: 11
    Last Post: Nov 15th 2009, 12:22 PM
  5. Replies: 7
    Last Post: Aug 12th 2009, 04:41 PM

/mathhelpforum @mathhelpforum