Results 1 to 5 of 5

Math Help - A Recurrence Relation

  1. #1
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7

    A Recurrence Relation

    Define the function f: \mathbb{N} \longrightarrow \mathbb{N} recursively by: \sum_{d \mid n}f(d)=2^n, \ \forall n \in \mathbb{N}. Prove that f(n) is divisible by n for all n \in \mathbb{N}.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2008
    From
    France
    Posts
    1,458
    Quote Originally Posted by NonCommAlg View Post
    Define the function f: \mathbb{N} \longrightarrow \mathbb{N} recursively by: \sum_{d \mid n}f(d)=2^n, \ \forall n \in \mathbb{N}. Prove that f(n) is divisible by n for all n \in \mathbb{N}.
    A very small part of the answer

    \sum_{d \mid 1}f(d)=f(1)=2

    If n is prime \sum_{d \mid n}f(d)=f(1)+f(n)=2^n therefore f(n)=2^n-2 which is divisible by n according to Fermat's little theorem

    Fermat's little theorem - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    First, that recurrence relation determines completely the numbers f(n), and they are in fact given by: <br />
f\left( n \right) = \sum\limits_{\left. d \right|n} {\mu \left( {\tfrac{n}<br />
{d}} \right) \cdot 2^d } <br />
-by Möbius' inversion formula.

    Okay, but the path we will take is rather different. Consider the primitive strings of bits of length (*) n these happen to satisfy the same recurrence relation, hence they must be equal - from what I said above-.

    (*) A string is not primitive if it is a concatenation of smaller ( all of them equal) strings. For example <br />
\begin{array}{*{20}c}<br />
   1 & 0 & 1 & 0  \\<br /> <br />
 \end{array} <br />
is not a primtive string, since it's made out of <br />
\begin{array}{*{20}c}<br />
   1 & 0  \\<br /> <br />
 \end{array} <br />

    Take <br />
\begin{array}{*{20}c}<br />
   1 & 1 & 0  \\<br /> <br />
 \end{array} <br />
for instance, this is a primitive string of bits of length 3. Next note that if we 'move' the places by 1 to the right ( and the last one goes to the first, a sort of circular permutation) we get: <br />
\begin{array}{*{20}c}<br />
   0 & 1 & 1  \\<br /> <br />
 \end{array} <br />
which is another primitive string of length 3, and if we do it again we get: <br />
\begin{array}{*{20}c}<br />
   1 & 0 & 1  \\<br /> <br />
 \end{array} <br />
which is again a primitive string. Note also that if we do it again we get to the initial one.

    So this suggests that we can partition the set of primitive strings of length n into sets of n elements in which each of the primitive strings is obtained by applying the operation -the operation has a name but it's on the tip of my tongue, oh well, I'll call it Circular permutation- we have just used repeatedly to a certain primtive string. (clearly an equivalence relation)

    First, it's easy to see that this operation applied to a primitive string generates another ( suppose the contrary and you'll get a contradiction by using a method similar to the one below.)

    We have to show that indeed we have sets of n different strings, always.

    So, suppose we have a primitive string of length n, which we will assoctiate with a function <br />
\delta :\mathbb{Z} \to \left\{ {0,1} \right\}<br />
were we have: <br />
\delta \left( i \right) = \left\{ \begin{gathered}<br />
  {\text{what's in the place }}i\left( {\bmod .n} \right){\text{ if }}i\left( {\bmod .n} \right) \ne 0 \hfill \\<br />
  {\text{what's in the place n if }}i\left( {\bmod .n} \right) = 0 \hfill \\ <br />
\end{gathered}  \right.<br />

    Suppose that applying our operation repeatedly s<n times we get to the same initial string, which is equivalent to the condition: <br />
\delta \left( {i + s} \right) = \delta \left( i \right)<br />
then <br />
\delta \left( {i + s \cdot m} \right) = \delta \left( i \right);\forall m \in \mathbb{Z}<br />

    Now consider <br />
M= {\text{min}}\left\{ {k \in \mathbb{Z}^ +  /\delta \left( i \right) = \delta \left( {i + k} \right);\forall i \in \mathbb{Z}} \right\}<br />
, and the integer division: <br />
n = M \cdot q + r<br />
; <br />
q,r \in \mathbb{Z}/0 \leqslant r < M<br />
, since <br />
n \in \left\{ {k \in \mathbb{Z}^ +  /\delta \left( i \right) = \delta \left( {i + k} \right);\forall i \in \mathbb{Z}} \right\}<br />
we get: <br />
\delta \left( i \right) = \delta \left[ {i + \underbrace {\left( {M \cdot q + r} \right)}_n \cdot h} \right] = \delta \left( {i + r \cdot h} \right);\forall h \in \mathbb{Z}<br />
, hence, if r is not 0 we have: <br />
r \in \left\{ {k \in \mathbb{Z}^ +  /\delta \left( i \right) = \delta \left( {i + k} \right);\forall i \in \mathbb{Z}} \right\} \wedge r < M<br />
which is a contradiction, hence r=0 and <br />
\left. M \right|n<br />

    But this implies that our primitive string is a concatenation of M smaller, and equal, strings of length M, thus it's not a primitive string: CONTRADICTION

    Now if <br />
\xi <br />
represents a string of length n, let <br />
D \xi <br />
be the string of length n resulting from doing the operation on <br />
\xi <br />
.

    We've just seen that, for any primitive string of length n, <br />
\varepsilon <br />
, <br />
D^i \varepsilon  \ne \varepsilon<br />
for all <br />
0 < i < n<br />
(1)

    So consider that for a primitive string we have that <br />
D^0 \xi ;...;D^{n - 1} \xi <br />
are not all different, that is <br />
D^i \xi  = D^j \xi <br />
for some n>j>i\geq{0}, then <br />
D^i \xi  = D^j \xi  = D^{j - i} \left( {D^i \xi } \right)<br />
and we get a contradiction by using (1), since we know that <br />
D^i \xi <br />
is also a primitive bit string of length n

    Therefore the claim is proven since we have <br />
f\left( n \right) = n \cdot S<br />
where S is the number of equivalence classes.
    Last edited by PaulRS; February 9th 2009 at 09:22 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    that's an interesting combinatorial approach PaulRS. the problem has also an algebraic solution:

    Fact: the number of monic irreducible polynomials of degree n over a finite field with p elements, where p is prime, is: \frac{1}{n}\sum_{d \mid n} \mu \left(\frac{n}{d} \right)p^d.

    i encourage anyone who's new to algebra (and number theory) to think about this beautiful result and see if they can prove it!
    Last edited by NonCommAlg; February 9th 2009 at 08:13 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by NonCommAlg View Post
    that's an interesting combinatorial approach PaulRS. the problem has also an algebraic solution:

    Fact: the number of irreducible polynomials of degree n over a finite field with p elements, where p is prime, is: \frac{1}{n}\sum_{d \mid n} \mu \left(\frac{n}{d} \right)p^d.

    i encourage anyone who's new to algebra (and number theory) to think about this beautiful result and see if they can prove it!
    Here is a hint to this: Show x^{p^n} - x = \prod_j p_j(x) --> then compare degrees.
    Where the product if over all monic irreducible polynomials of order dividing n.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 16th 2011, 12:27 AM
  2. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 18th 2010, 03:15 AM
  3. Recurrence Relation HELP
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 3rd 2009, 02:18 PM
  4. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 15th 2009, 07:20 PM
  5. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 16th 2008, 09:02 AM

Search Tags


/mathhelpforum @mathhelpforum