Замкнутая форма через рекурсию (ищу док.-во)

[kthxbye]

Пусть задана рекурсия

$$f(n,m)=\frac{\alpha n}{n+m} f(n-1, m) + \frac{\beta m}{n+m} f(n, m-1)+1$$

с начальными условиями

$$f(n,0)=\frac{1-\alpha^{n+1}}{1-\alpha}, f(0,m)=\frac{1-\beta^{m+1}}{1-\beta}$$

Пусть также

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

Я предполагаю, что

$$g(n,m)=\binom{n+m}{m}f(n,m)$$

Вот простенькая программка на PARI для проверки:

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

Существует ли способ как-нибудь это доказать?

[svv]

Перепишем рекуррентную формулу для $f(n,m)$ в терминах $g(n,m)=\binom{n+m}{m}f(n,m)$. Для этого надо обе её части домножить на $\binom{n+m}{m}$. Получится (по-моему, более простая) формула
$g(n,m)=\alpha\,g(n-1,m)+\beta\,g(n,m-1)+\binom{n+m}{m}$
с начальными условиями
$g(n,0)=\frac{1-\alpha^{n+1}}{1-\alpha},\quad g(0,m)=\frac{1-\beta^{m+1}}{1-\beta}$

Остаётся проверить, что этим условиям удовлетворяет
$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$

[kthxbye]

svv, все бы хорошо, да только вот замкнутая форма нам как бы неизвестна и ищется путь, по которому ее можно получить через баловство с рекуррентным соотношением. Я просто отметил, что она существует, т.е. есть к чему идти. А проверить, что удовлетворяет - это, наверное, каждый может.

[svv]

svv в сообщении #1592316 писал(а):

с начальными условиями
$g(n,0)=\frac{1-\alpha^{n+1}}{1-\alpha},\quad g(0,m)=\frac{1-\beta^{m+1}}{1-\beta}$

Это получается автоматически, если считать, что:
$\bullet$ $g(n,m)=0$ при $n<0$ или $m<0$;
$\bullet$ $g(n,m)=\alpha\,g(n-1,m)+\beta\,g(n,m-1)+\binom{n+m}{m}$ справедливо при всех $n,m\geqslant 0$.
В частности, $g(0,0)=\alpha\cdot 0+\beta\cdot 0+\binom{0}{0}=1$.
(Мне так нравится больше. Но Вы можете использовать старые начальные условия.)

Из рекуррентного соотношения и $g(0,0)=1$ следует, что $g(n,m)$ как полином от $\alpha,\beta$ при $n,m\geqslant 0$ имеет степень $n$ по $\alpha$ и степень $m$ по $\beta$:
$g(n,m)=\sum\limits_{i=0}^n \sum\limits_{j=0}^m c_{n,m}^{i,j} \alpha^i \beta^j\quad\quad(*)$
Если хоть одно из условий $0\leqslant i \leqslant n$ и $0\leqslant j \leqslant m$ не выполнено, считаем, что $c_{n,m}^{i,j}=0$.

Подставим $(*)$ в рекуррентное соотношение и приравняем коэффициенты при одинаковых степенях $\alpha$ и $\beta$. Получим, что при $0\leqslant i \leqslant n$ и $0\leqslant j \leqslant m$
$c_{n,m}^{i,j}=\begin{cases}\binom{n+m}{m}&\text{если}\;i=j=0\\c_{n-1,m}^{i-1,j}+c_{n,m-1}^{i,j-1}&\text{в противном случае}\end{cases}$
А что делать дальше, я расскажу завтра.

[kthxbye]

svv, благодарю вас за то, что вы решили уделить вопросу больше времени и занялись им в подходящем ключе. Заинтригован и ожидаю продолжения.

На англоязычном вопроснике мне тоже посоветовали переписать рекуррентную формулу, и указали, что якобы тогда уже попроще будет крутить генеративными функциями, но что и куда приспособить я так, увы, и не догадался.

[svv]

Замечаем, что в формуле
$c_{n,m}^{i,j}=c_{n-1,m}^{i-1,j}+c_{n,m-1}^{i,j-1}$
разности между первым нижним и первым верхним индексами одинаковы во всех членах: $n-i=(n-1)-(i-1)$. Аналогично, одинаковы разности между вторым нижним и вторым верхним индексами. Это наводит на мысль вместо $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}$

Тогда имеем при $0\leqslant p,q,i,j$
$d_{p,q}^{i,j}=\begin{cases}\binom{p+q}{q}&\text{если}\;i=j=0\\d_{p,q}^{i-1,j}+d_{p,q}^{i,j-1}&\text{в противном случае}\end{cases}$
(как и в случае с $c_{n,m}^{i,j}$, коэффициент $d_{p,q}^{i,j}$ считается нулевым, если хоть один индекс отрицательный). Эти соотношения связывают между собой только $d$ с одними и теми же нижними индексами $p,q$, иначе говоря, для каждого набора нижних индексов получаем независимую подзадачу (в чём и был смысл введения $d$).

Идём дальше. Если бы условия имели вид $d_{p,q}^{i,j}=\begin{cases}{\color{magenta}1}&\text{если}\;i=j=0\\d_{p,q}^{i-1,j}+d_{p,q}^{i,j-1}&\text{в противном случае}\end{cases}$
решением было бы $d_{p.q}^{i,j}=\binom{i+j}{i}=\binom{i+j}{j}$. В силу линейности рекуррентного соотношения, если теперь $d_{p,q}^{0,0}$ умножить на коэффициент $\binom{p+q}{q}$, то есть взять $d_{p,q}^{0,0}=\binom{p+q}{q}$, все остальные $d_{p,q}^{i,j}$ умножатся на тот же коэффициент, так что получим
$d_{p,q}^{i,j}=\binom{i+j}{j}\binom{p+q}{q}$

Возвращаясь к $c_{n,m}^{i,j}$, получаем явный вид
$c_{n,m}^{i,j}=\binom{i+j}{j}\binom{n-i+m-j}{m-j}$
и нужную формулу.

[kthxbye]

svv, все замечательно освещено и очень доступно, я бы даже сказал ярко и емко.

Меня терзает единственный вопрос: как из рекуррентного соотношения для $d_{p.q}^{i,j}$ выводится $d_{p.q}^{i,j}=\binom{i+j}{i}=\binom{i+j}{j}$?

[svv]

Здесь я бы просто сослался на всем знакомый треугольник Паскаля. Если «ось $i$» направить вниз, а «ось $j$» направить вправо, получим таблицу, где элемент $d^{0,0}=1$, а остальные $d^{i,j}$ равны сумме верхнего соседа $d^{i-1,j}$ и левого соседа $d^{i,j-1}$.

$$\begin{tabular}{l|c|c|c|c|c|c|c|c} & $...$ & $j=-1$ &$j=0$ & $j=1$ & $j=2$ & $j=3$ & $j=4$ & ... \\ \hline $...$ & $...$ & $...$ & $...$ & $...$ & $...$ & $...$ & $...$ & $...$\\ \hline $i=-1$ & $...$ & $0$ & $0$ & $0$ & $0$ & $0$ & $0$ & $...$\\ \hline $i=0$ & $...$ & $0$ & $\color{magenta}1$ & $1$ & $1$ & $1$ & $1$ & $...$\\ \hline $i=1$ & $...$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $...$\\ \hline $i=2$ & $...$ & $0$ & $1$ & $3$ & $6$ & $10$ & $15$ & $...$\\ \hline $i=3$ & $...$ & $0$ & $1$ & $4$ & $10$ & $20$ & $35$ & $...$\\ \hline $i=4$ & $...$ & $0$ & $1$ & $5$ & $15$ & $35$ & $70$ & $...$\\ \hline $...$ & $...$ & $...$ & $...$ & $...$ & $...$ & $...$ & $...$ & $...$\end{tabular}$$

Элементы с хоть одним отрицательным индексом считаем нулевыми, как и прежде.


То есть, не отвечая прямо на Ваш вопрос, я свожу его к следующему: как доказать, что при такой форме треугольника Паскаля элемент, стоящий в $i$-м столбце и $j$-й строке, равен $\binom{i+j}{j}$ ?

-- Чт май 04, 2023 15:20:57 --

:-)

[kthxbye]

kthxbye в сообщении #1592466 писал(а):

Меня терзает единственный вопрос: как из рекуррентного соотношения для $d_{p.q}^{i,j}$ выводится $d_{p.q}^{i,j}=\binom{i+j}{i}=\binom{i+j}{j}$?

Нашел вот такой ответ на этот вопрос, где рассматривается более общий случай.

С разрешения уважаемого svv опубликовал доказательство на англоязычном вопроснике MathOverflow. Лежит оно вот здесь. С английским у меня не ахти, перевожу через различные переводчики, но автору вопроса ответ судя по всему зашел, т.к. он обозначил его зеленой галочкой (т.е. выбрал его как лучший из возможных). К слову, это мой первый ответ на этом сайте, где я балуюсь в основном различными вопросами которые никому не нужны.

[svv]

Приятно, что всё хорошо получилось.
Скажите, а как на MathOverflow набирают формулы?

[kthxbye]

svv в сообщении #1593182 писал(а):

Скажите, а как на MathOverflow набирают формулы?

Все как и здесь, формула с двух сторон закрывается двумя $ (или 4-мя если центрируется), просто нет тега [math]. Когда я раньше писал там вопросы, то заходил тут к себе в личные сообщения, выбирал "новое сообщение" и писал вопрос там. Потом просто удалял все [math] в блокноте и, собственно, публиковал вопрос на MO. Постепенно я стал запоминать что и как правильно набирать и сейчас делаю это уже на сайте MO вручную.

Вероятно новые пользователи MO изначально гуглят как правильно набирать формулы, а потом уже постепенно набивают руку.

[maxal]

kthxbye в сообщении #1592260 писал(а):

Пусть также

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

Замкнутая формула для $g(n,m)$:

$$g(n,m) = (n+m+1)\binom{n+m}n \int_0^1 (1+(\alpha-1)t)^n (1+(\beta-1)t)^m {\rm d}t,$$

что также даёт

$$f(n,m) = (n+m+1) \int_0^1 (1+(\alpha-1)t)^n (1+(\beta-1)t)^m {\rm d}t.$$