0
$\begingroup$

Let $f(n)$ be an arbitrary function such that $f(n)\in\mathbb{Z}$.

Let $b(n)$ be an integer sequence such that $$b(2^m(2n+1))=\sum\limits_{k=0}^{m}f(m-k)b(2^kn), b(0)=1$$

Let $s(n,m)$ be an integer sequence such that $$s(n,m)=\sum\limits_{k=0}^{2^n-1}b(2^mk)$$

I conjecture that $$s(n,m) = s(n+1,m-1) - \sum\limits_{k=0}^{m-1}f(m-k-1)s(n,k), s(0,m)=1$$

If we rewrite the formula, it will allow us to simplify the summation: $$s(n,m)=s(n-1,m+1)+\sum\limits_{k=0}^{m}f(m-k)s(n-1,k), s(0,m)=1$$

This allows us to compute $f(n)$ if $s(n,0)$ is known: $$f(n)=s(1,n)-1-\sum\limits_{k=0}^{n-1}f(k)$$

Here is the PARI prog to verify these conjectures:

f(n)=n
s1(n)=my(v, v1); v=vector(2^n,i,0); v[1]=1; for(i=1,#v-1,my(A=valuation(i,2), B=i\2^(A+1)); v[i+1]=sum(j=0,A,f(A-j)*v[2^j*B+1])); v1=[1]; for(i=1,n,v1=concat(v1,sum(j=0,2^i-1,v[j+1]))); v1
s2(n)=my(v, v1); v=vector(n+1,i,1); v1=v; v2=vector(n+1,i,0); v2[1]=1; for(i=1,n,for(j=1,n-i+1,v1[j]=v[j+1]+sum(k=1,j,f(j-k)*v[k])); v=v1; v2[i+1]=v[1];); v2
test1(n)=s1(n)==s2(n)
f1(n)=my(A, B, v); A=vector(n+2,i,numbpart(i)); B=vector(n+2,i,if(i==1,A,vector(n-i+3,j,(j==1)))); v=vector(n+1,i,0); v[1]=A[2]-A[1]; for(i=2,n+1,for(j=2,i,B[j][i-j+2]=B[j-1][i-j+3]-sum(k=1,j-1,v[j-k]*B[k][i-j+2])); v[i]=B[i][2]-sum(j=1,i-1,v[j])-1); v
s3(n)=my(A=f1(n), v, v1); v=vector(n+1,i,1); v1=v; v2=vector(n+1,i,0); v2[1]=1; for(i=1,n,for(j=1,n-i+1,v1[j]=v[j+1]+sum(k=1,j,A[j-k+1]*v[k])); v=v1; v2[i+1]=v[1];); v2
test2(n)=my(A=s2(n), v); v=vector(n+1,i,A[i]==numbpart(i)); vecsum(v)==n+1

Here $f(n)=n$ gives $s(n,0)$ equals A036765, i.e., number of ordered rooted trees with n non-root nodes and all outdegrees <= three. Also $s(n,0)$ equals A000041, i.e., the number of partitions of n (the partition numbers) gives $f(n)$ equals A176950 multiplied by $(-1)^n$. For other results, see this topic on the dxdy scientific forum. It is very convenient to view the names and the first few terms of the sequence from the OEIS there. To do this, just hover the mouse over the link.

Is there a way to prove it?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ The recurrence for $b$ needs a base case. I suspect you're assuming $b(0) = 1$. $\endgroup$
    – Peter Taylor
    Commented May 23, 2023 at 8:54
  • $\begingroup$ @PeterTaylor, thank you for comment! Done. $\endgroup$
    – Notamathematician
    Commented May 23, 2023 at 9:16
  • 1
    $\begingroup$ Define $B_n(x)=\sum_{m=0}^{\infty}b(2^mn)x^m$ and $F(x)=\sum_{m=0}^{\infty}f(m)x^m$ also note $\frac{1}{n}\sum_{k=0}^{n-1}e^{2\pi ikt/n}=[n\mid k]$ now use the latter identity for when $n$ is a power of $2$ and reduce your problem to a set of differential equations... $\endgroup$
    – Ethan Splaver
    Commented May 27, 2023 at 1:56

0

Reset to default

You must log in to answer this question.