La unicidad (al igual que la existencia) ya te la da el teorema de recursión. El teorema de recursión (en la versión que entiendo tienes que usar tú) dice que, dado \[ x_0 \in \Bbb N \] y una función \[ g:\Bbb N \to \Bbb N \], existe una única función \[ f:\Bbb N \to \Bbb N \] tal que \[ f(0)=x_0 \] y \[ f(n+1)=g(f(n)) \].
En tu caso, toma \[ x_0=1 \] y \[ g(n)=m\cdot n \]. Así tienes definida de manera única la función \[ f_m \]. Fíjate que \[ f_m(n)=m^n \].
Si quisieras demostrar la unicidad aparte (aunque como digo, esto normalmente forma parte del enunciado del teorema de recursión) lo puedes hacer por inducción. Supón que \[ f,f' \] son dos funciones que cumplen la definición por recursión. Entonces \[ f(0)=x_0=f'(0) \] (caso base). Para el paso inductivo, supón que \[ f(n)=f'(n) \]. Entonces, \[ f(n+1)=g(f(n))=g(f'(n))=f'(n+1) \]. Luego el principio de inducción nos da que \[ f(n)=f'(n) \] para todo \[ n\in \Bbb N \]. Esto prueba ña unicidad.