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 08: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 07: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
    9
    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 15th 2011, 11:27 PM
  2. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 18th 2010, 02:15 AM
  3. Recurrence Relation HELP
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 3rd 2009, 01:18 PM
  4. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 15th 2009, 06:20 PM
  5. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 16th 2008, 08:02 AM

Search Tags


/mathhelpforum @mathhelpforum