Return to Answer

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). $$ For $m>2$, this reduces to $$a(n) = a(k)+(2^t-1)a(k-1).$$

First, let's analyze $s(n)$ for $m>2$.

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.

Second, let's consider the case $m=2$. Here 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.

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.

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). $$ For $m>2$, this reduces to $$a(n) = a(k)+(2^t-1)a(k-1).$$

First, let's analyze $s(n)$ for $m>2$.

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.

Second, let's consider the case $m=2$. Here 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^{t_2}(1+\dots(1+2^{t_\ell}))\dots)$ with $t_1\geq 0$ and $t_j>0$ for $j>1$, we have \begin{split} a(n) &= \sum_{i_1=0}^{t_1} \binom{t_1}{i_1} \sum_{i_2=0}^{t_2-1+i_1} \binom{t_2-1+i_1}{i_2} \sum_{i_3=0}^{t_3-1+i_2} \dots \sum_{i_\ell=0}^{t_\ell-1+i_{\ell-1}} \binom{t_\ell-1+i_{\ell-1}}{i_\ell} \\ &=(\ell+1)\prod_{j=1}^\ell (\ell+2-j)^{t_j-1}. \end{split}

Setting up $e_1:=t_1$ and $e_j:=t_j-1$ for $j>1$, and grouping the summands in $s(n)$ by the number of unit bits, we have \begin{split} s(n) &= \sum_{\ell=0}^n \sum_{e_1+e_2+\dots+e_{\ell}\leq n-\ell} \prod_{j=1}^\ell (\ell+2-j)^{e_j}\\ &= \sum_{\ell=0}^n \sum_{e_1+e_2+\dots+e_{\ell}+e_{\ell+1} = n-\ell} (\ell+1)\prod_{j=1}^{\ell+1} (\ell+2-j)^{e_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.

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). $$ For $m>2$, this reduces to $$a(n) = a(k)+(2^t-1)a(k-1).$$

First, let's analyze $s(n)$ for $m>2$.

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.

Second, let's consider the case $m=2$. Here 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.

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). $$ For $m>2$, this reduces to $$a(n) = a(k)+(2^t-1)a(k-1).$$

First, let's analyze $s(n)$ for $m>2$.

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.

Second, let's consider the case $m=2$. Here 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^{t_2}(1+\dots(1+2^{t_\ell}))\dots)$ with $t_1\geq 0$ and $t_j>0$ for $j>1$, we have $$a(n) = \sum_{i_1=0}^{t_1} \binom{t_1}{i_1} \sum_{i_2=0}^{t_2-1+i_1} \binom{t_2-1+i_1}{i_2} \sum_{i_3=0}^{t_3-1+i_2} \binom{t_3-1+i_2}{i_3} \dots \sum_{i_\ell=0}^{t_\ell-1+i_{\ell-1}} \binom{t_\ell-1+i_{\ell-1}}{i_\ell}$$ $$=(\ell+1)\prod_{j=1}^\ell (\ell+2-j)^{t_j-1}.$$

Setting up $e_1:=t_1$ and $e_j:=t_j-1$ for $j>1$, and grouping the summands in $s(n)$ by the number of unit bits, we have \begin{split} s(n) &= \sum_{\ell=0}^n \sum_{e_1+e_2+\dots+e_{\ell}\leq n-\ell} \prod_{j=1}^\ell (\ell+2-j)^{e_j}\\ &= \sum_{\ell=0}^n \sum_{e_1+e_2+\dots+e_{\ell}+e_{\ell+1} = n-\ell} (\ell+1)\prod_{j=1}^{\ell+1} (\ell+2-j)^{e_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} That is, when $m=2$, $s(n)$ equals the $(n+1)$-st Bell number.

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). $$ For $m>2$, this reduces to $$a(n) = a(k)+(2^t-1)a(k-1).$$

First, let's analyze $s(n)$ for $m>2$.

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.

Second, let's consider the case $m=2$. Here 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^{t_2}(1+\dots(1+2^{t_\ell}))\dots)$ with $t_1\geq 0$ and $t_j>0$ for $j>1$, we have \begin{split} a(n) &= \sum_{i_1=0}^{t_1} \binom{t_1}{i_1} \sum_{i_2=0}^{t_2-1+i_1} \binom{t_2-1+i_1}{i_2} \sum_{i_3=0}^{t_3-1+i_2} \dots \sum_{i_\ell=0}^{t_\ell-1+i_{\ell-1}} \binom{t_\ell-1+i_{\ell-1}}{i_\ell} \\ &=(\ell+1)\prod_{j=1}^\ell (\ell+2-j)^{t_j-1}. \end{split}

Setting up $e_1:=t_1$ and $e_j:=t_j-1$ for $j>1$, and grouping the summands in $s(n)$ by the number of unit bits, we have \begin{split} s(n) &= \sum_{\ell=0}^n \sum_{e_1+e_2+\dots+e_{\ell}\leq n-\ell} \prod_{j=1}^\ell (\ell+2-j)^{e_j}\\ &= \sum_{\ell=0}^n \sum_{e_1+e_2+\dots+e_{\ell}+e_{\ell+1} = n-\ell} (\ell+1)\prod_{j=1}^{\ell+1} (\ell+2-j)^{e_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.