# 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:

• @MaxAlekseyev, thank you for comment! Сould you please make the necessary corrections? I'm trying to understand what's wrong, but I cannot. Commented Sep 30, 2021 at 13:54
• In other words, $f(n,m)$ is the maximal power of $m$ which divides $n$? Commented Sep 30, 2021 at 13:58
• @FedorPetrov, thank you for comment! You are absolutely right. Commented Sep 30, 2021 at 14:04
• I think we should start like this: $S(n,m)=\sum_{l=0}^{m-1}(\sum_{k=0}^{m^{n-1}-1}a(mk+l,m))$. This gives $S(n,m)=mS(n-1,m)+\sum_{k=0}^{m^{n-1}-1}a(km-f(k,m),m)$ Commented Sep 30, 2021 at 14:31
• @Notamathematician: I've edited your question accordingly. Commented Sep 30, 2021 at 21:19

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.

• Thank you for answer! Do you have any ideas about the case $m=2$? Commented Oct 1, 2021 at 10:59
• What is about the case $m=2$? Commented Oct 1, 2021 at 12:57
• I mean why is this an exception when we get Bell numbers instead of the values of the recurrence relation? Commented Oct 1, 2021 at 13:31
• Very strange, my pari program gives me Bell numbers. Can you please double check result from computing? Commented Oct 1, 2021 at 14:51
• @Notamathematician: You are correct - please see the updated answer. Commented Oct 1, 2021 at 23:13

$$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).