Skip to main content
added 2282 characters in body
Source Link
Notamathematician
  • 4.9k
  • 2
  • 11
  • 24

This answer was deleted and then updated.

Let $$g(n,m)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}\binom{i+j}{j}\binom{n-i+m-j}{m-j}\alpha^i\beta^j$$ I conjecture that $$g(n,m)=\binom{n+m}{m}f(n,m)$$ Here is the PARI prog to verify this conjecture:

f(n, m) = if(n==0 || m==0, (m==0)*(1 - a^(n+1))/(1-a)+(n==0)*(1 - b^(m+1))/(1-b)-(n==0 && m==0), a*n/(n+m)*f(n-1, m)+b*m/(n+m)*f(n, m-1)+1)
g(n, m) = sum(i=0, n, sum(j=0, m, binomial(i+j,j)*binomial(n-i+m-j,m-j)*a^i*b^j))
test(n, m) = g(n, m)==binomial(n+m, m)*f(n, m)
n=6; x=sum(i=0, n, sum(j=0, n, test(i, j)))

ButHere is therethe proof of a way to proveuser with the nickname svv on a scientific forum dxdy.ru (here is the link to the topic):

Let $$g(n,m)=\binom{n+m}{m}f(n,m)$$ Then we have $$g(n,m)=\alpha\,g(n-1,m)+\beta\,g(n,m-1)+\binom{n+m}{m}$$ If we make a little change $$g(n,m)=[n\geqslant 0]\cdot[m\geqslant 0]\cdot\left(\alpha\,g(n-1,m)+\beta\,g(n,m-1)+\binom{n+m}{m}\right)$$ where square brackets denote Iverson brackets, then the basic conditions given for $f(n,0)$ and $f(0,m)$ holds.

From the recurrence relation and $g(0,0)=1$ it? follows that $g(n,m)$ as a polynomial of $\alpha,\beta$ for $n,m\geqslant 0$ has degree $n$ by $\alpha$ and degree $m$ by $\beta$: $$g(n,m)=\sum\limits_{i=0}^n \sum\limits_{j=0}^m c_{n,m}^{i,j} \alpha^i \beta^j$$

Substitute this into a recurrence relation and equate the coefficients at the same degrees of $\alpha$ and $\beta$. Then we have $$c_{n,m}^{i,j}=\begin{cases}\binom{n+m}{m}&\text{if}\;i=j=0\\c_{n-1,m}^{i-1,j}+c_{n,m-1}^{i,j-1}&\text{otherwise}\end{cases}$$

Note that the differences between the first lower and first upper indices are the same in all terms: $n-i=(n-1)-(i-1)$. Similarly, the differences between the second lower and second upper indices are the same. This suggests using (maybe temporarily) other coefficients, more invariant, so to speak, instead of $c$: $$d_{p,q}^{i,j}=c_{p+i,q+j}^{i,j},\quad c_{n,m}^{i,j}=d_{n-i,m-j}^{i,j}$$

Then we have $$d_{p,q}^{i,j}=\begin{cases}\binom{p+q}{q}&\text{if}\;i=j=0\\d_{p,q}^{i-1,j}+d_{p,q}^{i,j-1}&\text{otherwise}\end{cases}$$

If the conditions had the form $$d_{p,q}^{i,j}=\begin{cases}1&\text{if}\;i=j=0\\d_{p,q}^{i-1,j}+d_{p,q}^{i,j-1}&\text{otherwise}\end{cases}$$ then the solution would be $$d_{p,q}^{i,j}=\binom{i+j}{j}$$ For the proof, see this answer.

Due to the linearity of the recurrence relation, if now $d_{p,q}^{0,0}$ is multiplied by the coefficient $\binom{p+q}{q}$, that is, take $d_{p,q}^{0,0}=\binom{p+q}{q}$, all other $d_{p,q}^{i,j}$ will be multiplied by the same coefficient, so we get $$d_{p,q}^{i,j}=\binom{i+j}{j}\binom{p+q}{q}$$ Returning to $c_{n,m}^{i,j}$, we get the explicit form $$c_{n,m}^{i,j}=\binom{i+j}{j}\binom{n-i+m-j}{m-j}$$ and the desired formula.

This answer was deleted and then updated.

Let $$g(n,m)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}\binom{i+j}{j}\binom{n-i+m-j}{m-j}\alpha^i\beta^j$$ I conjecture that $$g(n,m)=\binom{n+m}{m}f(n,m)$$ Here is the PARI prog to verify this conjecture:

f(n, m) = if(n==0 || m==0, (m==0)*(1 - a^(n+1))/(1-a)+(n==0)*(1 - b^(m+1))/(1-b)-(n==0 && m==0), a*n/(n+m)*f(n-1, m)+b*m/(n+m)*f(n, m-1)+1)
g(n, m) = sum(i=0, n, sum(j=0, m, binomial(i+j,j)*binomial(n-i+m-j,m-j)*a^i*b^j))
test(n, m) = g(n, m)==binomial(n+m, m)*f(n, m)
n=6; x=sum(i=0, n, sum(j=0, n, test(i, j)))

But is there a way to prove it?

Let $$g(n,m)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}\binom{i+j}{j}\binom{n-i+m-j}{m-j}\alpha^i\beta^j$$ I conjecture that $$g(n,m)=\binom{n+m}{m}f(n,m)$$ Here is the PARI prog to verify this conjecture:

f(n, m) = if(n==0 || m==0, (m==0)*(1 - a^(n+1))/(1-a)+(n==0)*(1 - b^(m+1))/(1-b)-(n==0 && m==0), a*n/(n+m)*f(n-1, m)+b*m/(n+m)*f(n, m-1)+1)
g(n, m) = sum(i=0, n, sum(j=0, m, binomial(i+j,j)*binomial(n-i+m-j,m-j)*a^i*b^j))
test(n, m) = g(n, m)==binomial(n+m, m)*f(n, m)
n=6; x=sum(i=0, n, sum(j=0, n, test(i, j)))

Here is the proof of a user with the nickname svv on a scientific forum dxdy.ru (here is the link to the topic):

Let $$g(n,m)=\binom{n+m}{m}f(n,m)$$ Then we have $$g(n,m)=\alpha\,g(n-1,m)+\beta\,g(n,m-1)+\binom{n+m}{m}$$ If we make a little change $$g(n,m)=[n\geqslant 0]\cdot[m\geqslant 0]\cdot\left(\alpha\,g(n-1,m)+\beta\,g(n,m-1)+\binom{n+m}{m}\right)$$ where square brackets denote Iverson brackets, then the basic conditions given for $f(n,0)$ and $f(0,m)$ holds.

From the recurrence relation and $g(0,0)=1$ it follows that $g(n,m)$ as a polynomial of $\alpha,\beta$ for $n,m\geqslant 0$ has degree $n$ by $\alpha$ and degree $m$ by $\beta$: $$g(n,m)=\sum\limits_{i=0}^n \sum\limits_{j=0}^m c_{n,m}^{i,j} \alpha^i \beta^j$$

Substitute this into a recurrence relation and equate the coefficients at the same degrees of $\alpha$ and $\beta$. Then we have $$c_{n,m}^{i,j}=\begin{cases}\binom{n+m}{m}&\text{if}\;i=j=0\\c_{n-1,m}^{i-1,j}+c_{n,m-1}^{i,j-1}&\text{otherwise}\end{cases}$$

Note that the differences between the first lower and first upper indices are the same in all terms: $n-i=(n-1)-(i-1)$. Similarly, the differences between the second lower and second upper indices are the same. This suggests using (maybe temporarily) other coefficients, more invariant, so to speak, instead of $c$: $$d_{p,q}^{i,j}=c_{p+i,q+j}^{i,j},\quad c_{n,m}^{i,j}=d_{n-i,m-j}^{i,j}$$

Then we have $$d_{p,q}^{i,j}=\begin{cases}\binom{p+q}{q}&\text{if}\;i=j=0\\d_{p,q}^{i-1,j}+d_{p,q}^{i,j-1}&\text{otherwise}\end{cases}$$

If the conditions had the form $$d_{p,q}^{i,j}=\begin{cases}1&\text{if}\;i=j=0\\d_{p,q}^{i-1,j}+d_{p,q}^{i,j-1}&\text{otherwise}\end{cases}$$ then the solution would be $$d_{p,q}^{i,j}=\binom{i+j}{j}$$ For the proof, see this answer.

Due to the linearity of the recurrence relation, if now $d_{p,q}^{0,0}$ is multiplied by the coefficient $\binom{p+q}{q}$, that is, take $d_{p,q}^{0,0}=\binom{p+q}{q}$, all other $d_{p,q}^{i,j}$ will be multiplied by the same coefficient, so we get $$d_{p,q}^{i,j}=\binom{i+j}{j}\binom{p+q}{q}$$ Returning to $c_{n,m}^{i,j}$, we get the explicit form $$c_{n,m}^{i,j}=\binom{i+j}{j}\binom{n-i+m-j}{m-j}$$ and the desired formula.

deleted 50 characters in body
Source Link
Notamathematician
  • 4.9k
  • 2
  • 11
  • 24

This answer was deleted and then updated.

Let $$g(n,m,k)=\sum\limits_{i=0}^{m}\binom{n+i}{i}\binom{m-i+k}{k}\beta^i$$ $$h(n,m)=\sum\limits_{k=0}^{n}b(k,m,n-k)\alpha^k$$$$g(n,m)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}\binom{i+j}{j}\binom{n-i+m-j}{m-j}\alpha^i\beta^j$$ I conjecture that $$h(n,m)=\binom{n+m}{m}f(n,m)$$$$g(n,m)=\binom{n+m}{m}f(n,m)$$ Here is the PARI prog to verify this conjecture:

f(n, m) = if(n==0 || m==0, (m==0)*(1 - a^(n+1))/(1-a)+(n==0)*(1 - b^(m+1))/(1-b)-(n==0 && m==0), a*n/(n+m)*f(n-1, m)+b*m/(n+m)*f(n, m-1)+1)
g(n, m, k) = sum(i=0, mn, binomialsum(n+ij=0, i)*binomial(m-i+k, k)*b^i)
hbinomial(ni+j, mj) = sum*binomial(k=0, n, g(k-i+m-j, m, n-kj)*a^k*a^i*b^j))
test(n, m) = hg(n, m)==f==binomial(nn+m, m)*binomial*f(n+mn, m)
n=6; x=sum(i=0, n, sum(j=0, n, test(i, j)))

But is there a way to prove it?

This answer was deleted and then updated.

Let $$g(n,m,k)=\sum\limits_{i=0}^{m}\binom{n+i}{i}\binom{m-i+k}{k}\beta^i$$ $$h(n,m)=\sum\limits_{k=0}^{n}b(k,m,n-k)\alpha^k$$ I conjecture that $$h(n,m)=\binom{n+m}{m}f(n,m)$$ Here is the PARI prog to verify this conjecture:

f(n, m) = if(n==0 || m==0, (m==0)*(1 - a^(n+1))/(1-a)+(n==0)*(1 - b^(m+1))/(1-b)-(n==0 && m==0), a*n/(n+m)*f(n-1, m)+b*m/(n+m)*f(n, m-1)+1)
g(n, m, k) = sum(i=0, m, binomial(n+i, i)*binomial(m-i+k, k)*b^i)
h(n, m) = sum(k=0, n, g(k, m, n-k)*a^k)
test(n, m) = h(n, m)==f(n, m)*binomial(n+m, m)
n=6; x=sum(i=0, n, sum(j=0, n, test(i, j)))

But is there a way to prove it?

This answer was deleted and then updated.

Let $$g(n,m)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}\binom{i+j}{j}\binom{n-i+m-j}{m-j}\alpha^i\beta^j$$ I conjecture that $$g(n,m)=\binom{n+m}{m}f(n,m)$$ Here is the PARI prog to verify this conjecture:

f(n, m) = if(n==0 || m==0, (m==0)*(1 - a^(n+1))/(1-a)+(n==0)*(1 - b^(m+1))/(1-b)-(n==0 && m==0), a*n/(n+m)*f(n-1, m)+b*m/(n+m)*f(n, m-1)+1)
g(n, m) = sum(i=0, n, sum(j=0, m, binomial(i+j,j)*binomial(n-i+m-j,m-j)*a^i*b^j))
test(n, m) = g(n, m)==binomial(n+m, m)*f(n, m)
n=6; x=sum(i=0, n, sum(j=0, n, test(i, j)))

But is there a way to prove it?

Post Undeleted by Notamathematician
deleted 193 characters in body
Source Link
Notamathematician
  • 4.9k
  • 2
  • 11
  • 24

This answer was deleted and then updated.

Let $$a(n,m)=\sum\limits_{i=0}^{m-1}\binom{n+i-1}{i}\beta^i$$ $$b(n,m,k)=\left(\sum\limits_{i=0}^{m-1}\binom{n+i-1}{i}\binom{m-i+k}{k}\beta^i\right)+\sum\limits_{j=1}^{k+1}\binom{n+m-2}{m-1}\beta^{m+j-1}$$$$g(n,m,k)=\sum\limits_{i=0}^{m}\binom{n+i}{i}\binom{m-i+k}{k}\beta^i$$ $$c(n,m)=a(n,m)\alpha^n+\sum\limits_{k=1}^{n}b(n-k+1,m,k)\alpha^{n-k}$$$$h(n,m)=\sum\limits_{k=0}^{n}b(k,m,n-k)\alpha^k$$ I conjecture that for $n\geqslant0$, $m>0$ $$c(n,m)=\binom{n+m}{m}f(n,m)$$$$h(n,m)=\binom{n+m}{m}f(n,m)$$ Here is the PARI prog to verify this conjecture:

f(n, m) = if(n==0 || m==0, (n==0m==0)*(1 - a^(n+1))/(1-a)+(m==0n==0)*(1 - b^(n+1m+1))/(1-b)-(n==0 && m==0), a*n/(n+m)*f(n-1, m)+b*m/(n+m)*f(n, m-1)+1)
a1(n, m) = sum(i=0, m-1, binomial(n+i-1, i)*b^i)
b1g(n, m, k) = sum(i=0, m-1, binomial(n+i-1, i)*binomial(m-i+k, k)*b^i) + sum(j=1, k+1, binomial(n+m-2, m-1)*b^(m+j-1))
ch(n, m) = a1(n, m)*a^n + sum(k=1k=0, n, b1g(n-k+1k, m, k)*a^(n-k)*a^k)
test(n, m) = ch(n, m)==binomial==f(n, m)*binomial(n+m, m)*f
n=6; x=sum(i=0, n,m sum(j=0, n, test(i, j)))

But is there a way to prove it?

Let $$a(n,m)=\sum\limits_{i=0}^{m-1}\binom{n+i-1}{i}\beta^i$$ $$b(n,m,k)=\left(\sum\limits_{i=0}^{m-1}\binom{n+i-1}{i}\binom{m-i+k}{k}\beta^i\right)+\sum\limits_{j=1}^{k+1}\binom{n+m-2}{m-1}\beta^{m+j-1}$$ $$c(n,m)=a(n,m)\alpha^n+\sum\limits_{k=1}^{n}b(n-k+1,m,k)\alpha^{n-k}$$ I conjecture that for $n\geqslant0$, $m>0$ $$c(n,m)=\binom{n+m}{m}f(n,m)$$ Here is the PARI prog to verify this conjecture:

f(n, m) = if(n==0 || m==0, (n==0)*(1 - a^(n+1))/(1-a)+(m==0)*(1 - b^(n+1))/(1-b), a*n/(n+m)*f(n-1, m)+b*m/(n+m)*f(n, m-1)+1)
a1(n, m) = sum(i=0, m-1, binomial(n+i-1, i)*b^i)
b1(n, m, k) = sum(i=0, m-1, binomial(n+i-1, i)*binomial(m-i+k, k)*b^i) + sum(j=1, k+1, binomial(n+m-2, m-1)*b^(m+j-1))
c(n, m) = a1(n, m)*a^n + sum(k=1, n, b1(n-k+1, m, k)*a^(n-k))
test(n, m) = c(n, m)==binomial(n+m,m)*f(n,m)

But is there a way to prove it?

This answer was deleted and then updated.

Let $$g(n,m,k)=\sum\limits_{i=0}^{m}\binom{n+i}{i}\binom{m-i+k}{k}\beta^i$$ $$h(n,m)=\sum\limits_{k=0}^{n}b(k,m,n-k)\alpha^k$$ I conjecture that $$h(n,m)=\binom{n+m}{m}f(n,m)$$ Here is the PARI prog to verify this conjecture:

f(n, m) = if(n==0 || m==0, (m==0)*(1 - a^(n+1))/(1-a)+(n==0)*(1 - b^(m+1))/(1-b)-(n==0 && m==0), a*n/(n+m)*f(n-1, m)+b*m/(n+m)*f(n, m-1)+1)
g(n, m, k) = sum(i=0, m, binomial(n+i, i)*binomial(m-i+k, k)*b^i)
h(n, m) = sum(k=0, n, g(k, m, n-k)*a^k)
test(n, m) = h(n, m)==f(n, m)*binomial(n+m, m)
n=6; x=sum(i=0, n, sum(j=0, n, test(i, j)))

But is there a way to prove it?

Post Deleted by Notamathematician
Source Link
Notamathematician
  • 4.9k
  • 2
  • 11
  • 24
Loading