1
$\begingroup$

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:

$\endgroup$
7
  • $\begingroup$ @MaxAlekseyev, thank you for comment! Сould you please make the necessary corrections? I'm trying to understand what's wrong, but I cannot. $\endgroup$ Sep 30, 2021 at 13:54
  • 3
    $\begingroup$ In other words, $f(n,m)$ is the maximal power of $m$ which divides $n$? $\endgroup$ Sep 30, 2021 at 13:58
  • $\begingroup$ @FedorPetrov, thank you for comment! You are absolutely right. $\endgroup$ Sep 30, 2021 at 14:04
  • 1
    $\begingroup$ 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)$ $\endgroup$
    – Alapan Das
    Sep 30, 2021 at 14:31
  • 1
    $\begingroup$ @Notamathematician: I've edited your question accordingly. $\endgroup$ Sep 30, 2021 at 21:19

2 Answers 2

4
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.