Is there a recursive formula for Euler's Totient function I have been looking for a recursive formula for Euler's totient function or Möbius' mu function to use these relations and try to create a generating function for these arithmetic functions.
 A: Recurrence for the Euler totient function:
$$\phi(n) = n-{\sum_{d|n}}_\limits{d<n} \phi(d)$$
Recurrence for the Möbius function:
$$\mu(n) = -{\sum_{d|n}}_\limits{d<n} \mu(d)$$
Recurrence for the von Mangoldt function:
$$\Lambda(n) = \log(n)-{\sum_{d|n}}_\limits{d<n} \Lambda(d)$$
For the recurrence for the Dirichlet inverse of the Euler totient function:
$$a(n) = \frac{1}{n}-{\sum_{d|n}}_\limits{d<n} a(d)$$
you need to multiply the result with $n$.
Mathematica 8:
(*Recursive formula for Eulers totient function:*)
(*Mathematica*)
Clear[t];
t[1, 1] = 1;
t[n_, k_] := 
 t[n, k] = 
  If[k == 1, n - Sum[t[n, k + i], {i, 1, n - 1}], 
   If[Mod[n, k] == 0, t[n/k, 1], 0], 0]
MatrixForm[Table[Table[t[n, k], {k, 1, 12}], {n, 1, 12}]]


(*Recursive formula for the Möbius function:*)
(*Mathematica*)
(*start*)
Print["Möbius function:"];
 Clear[t, s, n, k, z];
 z = 1;
 nn = 12;
t[1, 1] = 1;
t[n_, k_] := 
 t[n, k] = 
  If[k == 1, -Sum[t[n, k + i]/(i + 1)^(s - 1), {i, 1, n - 1}], 
   If[Mod[n, k] == 0, t[n/k, 1], 0], 0]; MatrixForm[
 Table[Table[Limit[t[n, k], s -> z], {k, 1, nn}], {n, 1, nn}]] (*end*)

See also this answer: https://math.stackexchange.com/a/164829/8530
Recurrence for the Möbius function for complex numbers:
(*start*)Print["Möbius function:"]
Clear[t, s, n, k, z];
z = ZetaZero[-1];
nn = 12;
t[1, 1] = 1;
t[n_, k_] := 
 t[n, k] = 
  If[k == 1, -Sum[t[n, k + i]/(i + 1)^(s - 1), {i, 1, n - 1}], 
   If[Mod[n, k] == 0, t[n/k, 1], 0], 0]; MatrixForm[
 A = Table[
   Table[Limit[t[n, k], s -> z], {k, 1, nn}], {n, 1, nn}] (*end*)]

Clear[t, s, n, k, z];
nn = 12;
z = ZetaZero[1];
MatrixForm[
 B = Table[
   Table[If[n >= k, If[Mod[n, k] == 0, MoebiusMu[n/k]*(n/k)^z, 0], 
     0], {k, 1, nn}], {n, 1, nn}]]
N[A - B]
(*program end*)


Print["compared to:"];
z = N[ZetaZero[1]]; 
N[Table[MoebiusMu[n]*n^z, {n, 1, 12}]]

If you are looking for the ordinary generating function for the Möbius function then this is the closest you can get:
$$\sum_{n=1}^\infty \mu(n)x^n = x - \sum_{a=2}^\infty x^{a} + \sum_{a=2}^\infty \sum_{b=2}^\infty x^{ab} - \sum_{a=2}^\infty \sum_{b=2}^\infty \sum_{c=2}^\infty x^{abc} + \sum_{a=2}^\infty \sum_{b=2}^\infty \sum_{c=2}^\infty \sum_{d=2}^\infty x^{abcd} - \cdots$$
I wrote it into Wikipedia. Möbius function
s = 1;
Table[-Total[
   MoebiusMu[
     Divisors[n][[1 ;; Length[Divisors[n]] - 1]]]/(Divisors[n][
       1 ;; Length[Divisors[n]] - 1])^(s - 1)], {n, 1, 42}]

A: There is 2 parametric recursion for the Mobius function. Please look at the 
https://oeis.org/A266378
The actual formula is not very simple. Let
$$T(m,n) = \begin{cases} 1, & m=1, n=1 \\
0, & m=1, n \ne 1 \\
T(m, n-1) + T(m-1, n) - T(m-1, n-m), & m \ne 1 \end{cases} .$$
With the aid of $T$ we shall define $a$ by
$$a(n,m) = a(n, m-1)+a(n-1, m)-a(n-1, m-n+1)-\\
a\Big(n-1, \nu(n-1)\Big) \Big(T(n-2, m-1)-T(n-2, m-2)\Big), $$
where $\nu(n)=\dfrac {(n-2)(n-3)} 2$, $a(n,0)=-1$ and $a(n,m)=0$ for $\nu(n)<m<0$.
With these preparations we have $\mu(n) = a(n,\nu(n))$, the Möbius function.
EDITED:
There is very similiar formula for the Euler Totient function:
http://oeis.org/A282283
$$H(n,m) = \begin{cases} 1, & m=0, n=1 \\
0, & m \ne 0, n=1 \\
H(n - 1, n*(n - 1)/2 - m)*(-1)^n - H(n - 1, m), & n > 1 \end{cases} .$$
$$Q(n, m) = H(n, m - 2) - 2*H(n, m - 1) + H(n, m)$$
And then:
$$b(n,m) = b(n - 1, m - n + 1) - b(n - 1, m) - b(n - 1, \nu(n - 1))*Q(n - 1, m))$$
where $\nu(n)=\dfrac {(n*(n-3)+4)} 2$.
With these preparations we have $\phi(n) = b(n,\nu(n))$, the Totient function.
A: The answer to your question depends on what you mean by "generating function". I expect that the type of generating function you have in mind is an ordinary generating function, which takes the form of a power series. Such generating functions work best with sequences that satisfy additive recursive formulas; the classic example is the Fibonacci numbers, which satisfy the recurrence $F_{n+2}=F_{n+1}+F_n$. But the Möbius function and the totient function are fundamentally multiplicative, and I do not imagine that the ordinary generating function for either of them has any simple closed-form expression.
There are at least two alternatives to ordinary generating functions which yield nice results for the $\mu$ and $\varphi$ functions. The first is a Dirichlet series, which has the form
$$
f(s)=\sum_{n=1}^\infty \frac{a_n}{n^s}.
$$
It turns out that the Dirichlet series for $\mu$ is
$$
\frac{1}{\zeta(s)} = \sum_{n=1}^\infty \frac{\mu(n)}{n^s}
$$
and the Dirichlet series for $\varphi$, as Brad mentioned, is
$$
\frac{\zeta(s-1)}{\zeta(s)} = \sum_{n=1}^\infty \frac{\varphi(n)}{n^s}.
$$
Here $\zeta(s)$ is the famous Riemann zeta function.
The second useful type of generating function is a Lambert series, which has the form
$$
f(q) = \sum_{n=1}^\infty a_n\frac{q^n}{1-q^n}.
$$
The Lambert series for $\mu$ and $\varphi$ are particularly simple;
they are given by
$$
\sum_{n=1}^\infty \mu(n)\frac{q^n}{1-q^n} = q
$$
and
$$
\sum_{n=1}^\infty \varphi(n)\frac{q^n}{1-q^n} = \frac{q}{(1-q)^2}.
$$
A: There are two simple recursive formulas you can use for computing $\mu(n)$ and $\varphi(n)$ on $[1,N]$ : 

$$\sum_{k=1}^n \mu(k) \lfloor n/k\rfloor= 1, \qquad \quad\sum_{k=1}^n \varphi(k) \lfloor n/k\rfloor= \frac{n(n+1)}{2}$$

following from $\sum_{d | n} \mu(d)=1_{n= 1}$ and $\sum_{d | n} \varphi(d) = n$
