# Thread: A Recurrence Relation

1. ## A Recurrence Relation

Define the function $\displaystyle f: \mathbb{N} \longrightarrow \mathbb{N}$ recursively by: $\displaystyle \sum_{d \mid n}f(d)=2^n, \ \forall n \in \mathbb{N}.$ Prove that $\displaystyle f(n)$ is divisible by $\displaystyle n$ for all $\displaystyle n \in \mathbb{N}.$

2. Originally Posted by NonCommAlg
Define the function $\displaystyle f: \mathbb{N} \longrightarrow \mathbb{N}$ recursively by: $\displaystyle \sum_{d \mid n}f(d)=2^n, \ \forall n \in \mathbb{N}.$ Prove that $\displaystyle f(n)$ is divisible by $\displaystyle n$ for all $\displaystyle n \in \mathbb{N}.$
A very small part of the answer

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

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

Fermat's little theorem - Wikipedia, the free encyclopedia

3. First, that recurrence relation determines completely the numbers $\displaystyle f(n)$, and they are in fact given by: $\displaystyle f\left( n \right) = \sum\limits_{\left. d \right|n} {\mu \left( {\tfrac{n} {d}} \right) \cdot 2^d }$ -by Möbius' inversion formula.

Okay, but the path we will take is rather different. Consider the primitive strings of bits of length (*) $\displaystyle 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 $\displaystyle \begin{array}{*{20}c} 1 & 0 & 1 & 0 \\ \end{array}$ is not a primtive string, since it's made out of $\displaystyle \begin{array}{*{20}c} 1 & 0 \\ \end{array}$

Take $\displaystyle \begin{array}{*{20}c} 1 & 1 & 0 \\ \end{array}$ 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: $\displaystyle \begin{array}{*{20}c} 0 & 1 & 1 \\ \end{array}$ which is another primitive string of length 3, and if we do it again we get: $\displaystyle \begin{array}{*{20}c} 1 & 0 & 1 \\ \end{array}$ 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 $\displaystyle n$ into sets of $\displaystyle 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 $\displaystyle n$ different strings, always.

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

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

Now consider $\displaystyle M= {\text{min}}\left\{ {k \in \mathbb{Z}^ + /\delta \left( i \right) = \delta \left( {i + k} \right);\forall i \in \mathbb{Z}} \right\}$, and the integer division: $\displaystyle n = M \cdot q + r$ ; $\displaystyle q,r \in \mathbb{Z}/0 \leqslant r < M$, since $\displaystyle n \in \left\{ {k \in \mathbb{Z}^ + /\delta \left( i \right) = \delta \left( {i + k} \right);\forall i \in \mathbb{Z}} \right\}$ we get: $\displaystyle \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}$, hence, if r is not 0 we have: $\displaystyle 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$ which is a contradiction, hence $\displaystyle r=0$ and $\displaystyle \left. M \right|n$

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

Now if $\displaystyle \xi$ represents a string of length n, let $\displaystyle D \xi$ be the string of length n resulting from doing the operation on $\displaystyle \xi$.

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

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

Therefore the claim is proven since we have $\displaystyle f\left( n \right) = n \cdot S$ where $\displaystyle S$ is the number of equivalence classes.

4. that's an interesting combinatorial approach PaulRS. the problem has also an algebraic solution:

Fact: the number of monic irreducible polynomials of degree $\displaystyle n$ over a finite field with $\displaystyle p$ elements, where $\displaystyle p$ is prime, is: $\displaystyle \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!

5. Originally Posted by NonCommAlg
that's an interesting combinatorial approach PaulRS. the problem has also an algebraic solution:

Fact: the number of irreducible polynomials of degree $\displaystyle n$ over a finite field with $\displaystyle p$ elements, where $\displaystyle p$ is prime, is: $\displaystyle \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 $\displaystyle x^{p^n} - x = \prod_j p_j(x)$ --> then compare degrees.
Where the product if over all monic irreducible polynomials of order dividing $\displaystyle n$.