Recurrence for the sum Let $m\geq 2$ be a fixed integer.
Let
$$f(n):=\begin{cases}
mf\left(\frac{n}{m}\right),&\text{if $n\mod m = 0$;}\\
1,&\text{otherwise}
\end{cases}$$
then if we have
$$a(n):=\begin{cases}
1,&\text{if $n=0$;}\\
a\left(\frac{n}{m}\right)+a\left(n-f\left(\frac{n}{m}\right)\right),&\text{if $n\mod m = 0$;}\\
a\left(\left\lfloor\frac{n}{m}\right\rfloor\right),&\text{otherwise}
\end{cases}$$
and also
$$s(n):=\sum\limits_{k=0}^{m^n-1}a(k).$$
In particular, $s(0) = 1$ and $s(1) = m$.
I conjecture that for $m > 2$
$$s(n)=(m+3)s(n-1)-(2m+1)s(n-2).$$
For a case $m=2$ we get Bell numbers.
Is there a way to prove it?
Similar questions:

*

*Sum with Stirling numbers of the second kind

*Pair of recurrence relations with $a(2n+1)=a(2f(n))$

*Sequence that sums up to INVERTi transform applied to the ordered Bell numbers

*Sequences that sums up to second differences of Bell and Catalan numbers
 A: Let $n=m^tk$ where $m\nmid k$. Then $f(n)=m^t$. 
Furthermore, if $t>0$, then $f(n/m)=m^{t-1}$ and $n-f(n/m)=m^{t-1}(mk-1)$. It follows that $a(n)=a(m^{t-1}k)+a(m^{t-1}(mk-1))$ and further by induction on $t$,
$$
(\star)\qquad a(n)=\sum_{i=0}^t \binom{t}{i} a\big(m^ik-\frac{m^i-1}{m-1}\big).
$$

CASE $m>2$. In this case, formula $(\star)$ reduces to
$$a(n) = a(k)+(2^t-1)a(k-1).$$
Let's analyze $s(n)$.
It is clear that for any $\ell\not\equiv 0\pmod{m}$, we have
$$\sum_{k=0\atop k\equiv \ell\pmod{m}}^{m^n-1} a(k) = s(n-1)$$
and correspondingly
$$\sum_{k=0\atop k\equiv 0\pmod{m}}^{m^n-1} a(k) = s(n) - (m-1)s(n-1)$$
Now we are ready to derive a recurrence for $s(n)$ by grouping the summation indices based on the power $m^t$ they contain:
\begin{split}
s(n) &= 1 + \sum_{t=0}^{n-1} \sum_{k=1\atop k\not\equiv 0\pmod{m}}^{m^{n-t}-1} \left(a(k) + (2^t-1)a(k-1)\right) \\
&=1 +\sum_{t=0}^{n-1} \left((m-1)s(n-t-1) + (2^t-1)((m-2)s(n-t-1) + s(n-t)-(m-1)s(n-t-1))\right) \\
&=1 +\sum_{t=0}^{n-1} \left((m-2^t)s(n-t-1) + (2^t-1)s(n-t)\right) \\
&=2 - 2^n + \sum_{t=1}^n (2^{t-1}+m-1)s(n-t).
\end{split}
Restating the above recurrence in terms of the generating function $S(x):=\sum_{n\geq 0} s(n)x^n$, we have
$$S(x) = \frac{2}{1-x} - \frac{1}{1-2x} + \left(\frac{x}{1-2x} + \frac{(m-1)x}{1-x}\right)S(x).$$
That is,
$$S(x) = \frac{1-3x}{1 - (m+3)x + (2m+1)x^2},$$
from where the required recurrence follows instantly.

CASE $m=2$. In this case, formula $(\star)$ takes form:
$$a(n)=a(k)+\sum_{i=1}^t \binom{t}{i} a(2^{i-1}(k-1)).$$
It further follows that for $n=2^{t_1}(1+2^{1+t_2}(1+\dots(1+2^{1+t_\ell}))\dots)$ with $t_j\geq 0$, we have
\begin{split}
a(n) &= \sum_{i_1=0}^{t_1} \binom{t_1}{i_1} \sum_{i_2=0}^{t_2+i_1} \binom{t_2+i_1}{i_2} \sum_{i_3=0}^{t_3+i_2} \dots \sum_{i_\ell=0}^{t_\ell+i_{\ell-1}} \binom{t_\ell+i_{\ell-1}}{i_\ell} \\
&=\prod_{j=1}^\ell (\ell+2-j)^{t_j}.
\end{split}
Grouping the summands in $s(n)$ by the number of unit bits, we have
\begin{split}
s(n) &= \sum_{\ell=0}^n\ \sum_{t_1+t_2+\dots+t_{\ell}\leq n-\ell}\  \prod_{j=1}^\ell (\ell+2-j)^{t_j}\\
&= \sum_{\ell=0}^n\ \sum_{t_1+t_2+\dots+t_{\ell}+t_{\ell+1} = n-\ell}\ \prod_{j=1}^{\ell+1} (\ell+2-j)^{t_j}\\
&=\sum_{\ell=0}^n [x^{n-\ell}]\ \prod_{j=1}^{\ell+1} \frac1{1-jx} \\
&=\sum_{\ell=0}^n S(n+1,\ell+1) \\
&=B_{n+1},
\end{split}
where $S(n+1,\ell+1)$ are Stirling numbers of second kind, and $B_{n+1}$ is Bell number.
A: $$S(n)=\sum_{k=0}^{m^n-1} a(k)=\sum_{l=0}^{m-1}\sum_{k=0}^{m^{n-1}-1} a(km+l)$$....$(0)$
Using, the recurrence relations we simplify this to
$$S(n)=mS(n-1)+\sum_{k=0}^{m^{n-1}-1}a(km-f(k))$$.... $(1)$
By similar treatment as $(0)$ and again using the recurrence relations we further simplify it to
$$S(n)=(m+1)S(n-1)-S(n-2)+\sum_{k=0}^{m^{n-2}-1}a(km^2-mf(k))$$...$(2)$
Now, using $(1)$ for $S(n-1)$ with $(2)$ we get the following
$$S(n)=(m+3)S(n-1)-(2m+1)S(n-2)+T(n-2)$$
Where, $$T(n-2)=\sum_{k=0}^{m^{n-2}-1} a\left(km-f(k)-f(km-f(k))\right)-a(km-f(k)$$
Now, the terms for $k$ s.t $m \nmid k$, simplifies to $a(km-2)-a(km-1)=0$ for $m>2$.
So, we are left with $$T(n-3)=\sum_{k=0}^{m^{n-3}-1} a(km^3-m^2f(k)-mf(km-f(k))-a(km^2-mf(k))$$. It can be simplified as the terms inside are divisible by $m$. And then the terms corresponding to $k, m \nmid k$ cancels. (It can be seen that the first term becomes the 2nd term in the next step).
