Доказать что любой многочлен q(n) удовлетворяет л.р.с.

[Sleep3r]

Доказать что любой многочлен q(n) степени r удовлетворяет линейному рекуррентному соотношению

$q(n+r+1)=\binom{r+1}{1}q(n+r)-\binom{r+1}{2}q(n+r-1)+...+(-1)^r\binom{r+1}{r+1}q(n)$

Ясно, что решать нужно методом математической индукции, но никак не получается доказать переход. Расписывал на факториалы, домножал, но не получалось.

[grizzly]

Sleep3r в сообщении #1273809 писал(а):

Ясно, что решать нужно методом математической индукции

А как делали? Индукцию по $r?$ И пытались расписывать $q(n+(r+1)+1)$ через $q((n+1)+r+1)?$ (что раскладывается по предположению для всех $n$) и в итоге никакие подобные не удаётся свести? Или как-то иначе?

[arseniiv]

Можно, кстати, понимать записанное как утверждение, что $r$-я конечная разность (с шагом 1) этого многочлена равна нулю. Правда, доказывать, что это действительно она, придётся ровно тем же образом, по индукции — но хотя бы какой-то смысл появляется.

[DeBill]

А где то - то ли в ПРР, то ли в Олимпиадном - эта задача уже обсуждалась раньше. И даже было предложено целых три решения...

-- 11.12.2017, 03:56 --

Только там были, вроде, одночлены (но, по линейности, эт то же самое).

[Sleep3r]

grizzly в сообщении #1273812 писал(а):

Sleep3r в сообщении #1273809 писал(а):

Ясно, что решать нужно методом математической индукции

А как делали? Индукцию по $r?$ И пытались расписывать $q(n+(r+1)+1)$ через $q((n+1)+r+1)?$ (что раскладывается по предположению для всех $n$) и в итоге никакие подобные не удаётся свести? Или как-то иначе?

А зачем индукция по r, если r - заданная степень?

[arseniiv]

Заданная не заданная, а доказать всё равно нужно для всех натуральных $r$. А по $n$ индукцию устраивать странно: оно может быть и целым, и рациональным, и вещественным…

[Sleep3r]

arseniiv в сообщении #1274126 писал(а):

Заданная не заданная, а доказать всё равно нужно для всех натуральных $r$. А по $n$ индукцию устраивать странно: оно может быть и целым, и рациональным, и вещественным…

Ок, но я все равно не понимаю, как здесь индуцировать. Правило треугольника не помогает.

[arseniiv]

Ну, база-то хоть получилась (для нуля или единицы — на ваше усмотрение)? Выпишите, как должен выглядеть переход, вдруг какая-нибудь деталь откроется.

(Оффтоп)

Sleep3r в сообщении #1274137 писал(а):

индуцировать

Необычное словоупотребление.

[Sleep3r]

arseniiv в сообщении #1274150 писал(а):

Ну, база-то хоть получилась (для нуля или единицы — на ваше усмотрение)? Выпишите, как должен выглядеть переход, вдруг какая-нибудь деталь откроется.

(Оффтоп)

Sleep3r в сообщении #1274137 писал(а):

индуцировать

Необычное словоупотребление.

При r=0 база: q(n+1)=q(n), что очевидно истинно, т.к r=0=degq

[arseniiv]

Угу. Ну теперь попробуйте переход — пока не обязательно для произвольного $r$, для нескольких первых — от 0 к 1, от 1 к 2. Частные случаи могут прояснить то, что было не видно за общими формулами. (Хотя бывает и наоборот, но попробовать никогда не вредно.)

[grizzly]

Sleep3r
И вспомните совет выше: проверяйте только для одночленов максимальной степени. Тогда многочлен у Вас автоматически будет следовать из предыдущего шага индукции плюс линейности формулы.