Про многочлены Гаусса

[Alexander__]

Условие:

Пусть $m,n \in N_0$, $h_n(x)=(x^n-1)(x^{n-1}-1)...(x-1)$, $h_0(x)=1$.

Доказать, что $g_{m,n}(x)=\frac{h_{m+n}(x)}{h_m(x) h_n(x)}$ -- многочлены с целыми коэффициентами.

---

Как я понимаю, нужно доказать, что $h_{m+n}(x)$ нацело делится одновременно на $h_m(x)$ и $h_n(x)$. Предполагаю, что нужно индукцией по двум аргументам. Верно ли? Или можно проще?

[Leeb]

Да, можно доказать через формулы сокращенного умножения, если вспомнить, что для любых $n$ последовательных натуральных чисел ($k+1,k+2,...,k+n$) можно каждому из них сопоставить число из $1,2,3,...,n$ так, что первое число из сопоставления делится на второе.

[dgwuqtj]

Я бы это доказывал с помощью рекуррентного соотношения на $g_{m, n}$, по аналогии с числами сочетаний.

Leeb в сообщении #1612034 писал(а):

для любых $n$ последовательных натуральных чисел ($k+1,k+2,...,k+n$) можно каждому из них сопоставить число из $1,2,3,...,n$ так, что первое число из сопоставления делится на второе.

Это неверно для тройки $5, 6, 7$ (в смысле, взаимно однозначного соответствия нет).

[Leeb]

Согласен, надо поточнее подсчитать простые сомножители. На суть не влияет, тем не менее.

[dgwuqtj]

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