Идентичность хоккейной клюшки

Треугольник Паскаля, строки с 0 по 7. Тождество клюшки подтверждается, например: для n =6, r =2: 1+3+6+10+15=35.

В комбинаторной математике тождество хоккейной клюшки ^[1] Рождественский чулок , ^[2] тождество бумеранга , тождество Ферма или теорема Чу , ^[3] утверждает, что если $n\geq r\geq 0$ являются целыми числами, то

{\binom {r}{r}}+{\binom {r+1}{r}}+{\binom {r+2}{r}}+\cdots +{\binom {n}{r}}={\binom {n+1}{r+1}}.

Название происходит от графического изображения тождества на треугольнике Паскаля : когда слагаемые, представленные при суммировании, и сама сумма выделены, выявленная форма отдаленно напоминает эти объекты (см. хоккейную клюшку , рождественский чулок ).

Составы

Используя сигма-нотацию , тождество утверждает

\sum _{i=r}^{n}{i \choose r}={n+1 \choose r+1}\qquad {\text{ for }}n,r\in \mathbb {N} ,\quad n\geq r

или, что то же самое, зеркальное изображение путем замены $j\to i-r$ :

\sum _{j=0}^{n-r}{j+r \choose r}=\sum _{j=0}^{n-r}{j+r \choose j}={n+1 \choose n-r}\qquad {\text{ for }}n,r\in \mathbb {N} ,\quad n\geq r.

Доказательства

Создание доказательства функции

Позволять $X=1+x$ . Тогда по формуле частных сумм для геометрической прогрессии находим, что

X^{r}+X^{r+1}+\dots +X^{n}={\frac {X^{r}-X^{n+1}}{1-X}}={\frac {X^{n+1}-X^{r}}{x}}

.

Далее по биномиальной теореме также находим, что

$X^{r+k}=(1+x)^{r+k}=\sum _{i=0}^{r+k}{\binom {r+k}{i}}x^{i}$ .

Обратите внимание, что это означает коэффициент $x^{r}$ в $X^{r+k}$ дается ${\binom {r+k}{r}}$ .

Таким образом, коэффициент $x^{r}$ в левой части нашего первого уравнения можно получить суммированием коэффициентов $x^{r}$ из каждого члена, что дает

$\sum _{k=0}^{n-r}{\binom {r+k}{r}}$

Аналогично находим, что коэффициент $x^{r}$ в правой части определяется коэффициентом $x^{r+1}$ в $X^{n+1}-X^{r}$ , что

${\binom {n+1}{r+1}}-{\binom {r}{r+1}}={\binom {n+1}{r+1}}$

Таким образом, мы можем сравнить коэффициенты $x^{r}$ в каждой части уравнения, чтобы найти, что

$\sum _{k=0}^{n-r}{\binom {r+k}{r}}={\binom {n+1}{r+1}}$

Индуктивные и алгебраические доказательства

И индуктивное, и алгебраическое доказательство используют тождество Паскаля :

{n \choose k}={n-1 \choose k-1}+{n-1 \choose k}.

Индуктивное доказательство

Это тождество можно доказать методом математической индукции по $n$ .

Базовый вариант Позволять $n=r$ ;

\sum _{i=r}^{n}{i \choose r}=\sum _{i=r}^{r}{i \choose r}={r \choose r}=1={r+1 \choose r+1}={n+1 \choose r+1}.

Индуктивный шаг Предположим, для некоторых $k\in \mathbb {N} ,k\geqslant r$ ,

\sum _{i=r}^{k}{i \choose r}={k+1 \choose r+1}

Затем

\sum _{i=r}^{k+1}{i \choose r}=\left(\sum _{i=r}^{k}{i \choose r}\right)+{k+1 \choose r}={k+1 \choose r+1}+{k+1 \choose r}={k+2 \choose r+1}.

Алгебраическое доказательство

Мы используем телескопический аргумент, чтобы упростить вычисление суммы:

{\begin{aligned}\sum _{t=\color {blue}0}^{n}{\binom {t}{k}}=\sum _{t=\color {blue}k}^{n}{\binom {t}{k}}&=\sum _{t=k}^{n}\left[{\binom {t+1}{k+1}}-{\binom {t}{k+1}}\right]\\&=\sum _{t=\color {green}k}^{\color {green}n}{\binom {\color {green}{t+1}}{k+1}}-\sum _{t=k}^{n}{\binom {t}{k+1}}\\&=\sum _{t=\color {green}{k+1}}^{\color {green}{n+1}}{\binom {\color {green}{t}}{k+1}}-\sum _{t=k}^{n}{\binom {t}{k+1}}\\&={\binom {n+1}{k+1}}-\underbrace {\binom {k}{k+1}} _{0}&&{\text{by telescoping}}\\&={\binom {n+1}{k+1}}.\end{aligned}}

Комбинаторные доказательства

Доказательство 1

Представьте, что мы распространяем $n$ неотличимые конфеты $k$ различимые дети. Непосредственным применением метода звезд и полос можно получить

{\binom {n+k-1}{k-1}}

способы сделать это. Альтернативно, мы можем сначала дать $0\leqslant i\leqslant n$ конфеты старшему ребенку, так что мы по сути дарим $n-i$ конфеты для $k-1$ дети и снова, со звездами, полосами и двойным счетом , у нас есть

{\binom {n+k-1}{k-1}}=\sum _{i=0}^{n}{\binom {n+k-2-i}{k-2}},

который упрощается до желаемого результата, принимая $n'=n+k-2$ и $r=k-2$ , и заметив, что $n'-n=k-2=r$ :

{\binom {n'+1}{r+1}}=\sum _{i=0}^{n}{\binom {n'-i}{r}}=\sum _{i=r}^{n'}{\binom {i}{r}}.

Доказательство 2

Мы можем сформировать комитет размером $k+1$ из группы $n+1$ люди в

{\binom {n+1}{k+1}}

пути. Теперь мы раздаем номера $1,2,3,\dots ,n-k+1$ к $n-k+1$ принадлежащий $n+1$ люди. Затем мы можем разделить процесс формирования комитета на $n-k+1$ исчерпывающие и непересекающиеся дела по члену комитета с наименьшим номером, $x$ . Обратите внимание, что существуют только $k$ люди без номеров, то есть мы должны выбрать хотя бы одного человека с номером, чтобы сформировать комитет из $k+1$ люди. В общем, в случае $x$ , человек $x$ находится в комитете и лиц $1,2,3,\dots ,x-1$ не входят в комитет. Остальные члены комитета затем могут быть выбраны в

{\binom {n-x+1}{k}}

пути. Теперь мы можем суммировать значения этих $n-k+1$ непересекающихся случаях и, используя двойной счет , получаем

{\binom {n+1}{k+1}}={\binom {n}{k}}+{\binom {n-1}{k}}+{\binom {n-2}{k}}+\cdots +{\binom {k+1}{k}}+{\binom {k}{k}}.

См. также

Личность Паскаля
Треугольник Паскаля
Треугольник Лейбница
Личность Вандермонда
Формула Фаульхабера для сумм произвольных многочленов.

Ссылки

^ CH Jones (1996) Обобщенные идентичности хоккейной клюшки и N-мерная ходьба по блокам. Ежеквартальный журнал Фибоначчи 34 (3), 280–288.
^ В., Вайсштейн, Эрик. «Теорема о рождественском чулке» . mathworld.wolfram.com . Проверено 1 ноября 2016 г. {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Меррис, Рассел (2003). Комбинаторика (2-е изд.). Хобокен, Нью-Джерси: Wiley-Interscience. п. 45. ИСБН 0-471-45849-Х . OCLC 53121765 .

Внешние ссылки

[1] CH Jones (1996) Обобщенные идентичности хоккейной клюшки и N-мерная ходьба по блокам. Ежеквартальный журнал Фибоначчи 34 (3), 280–288.

[2] В., Вайсштейн, Эрик. «Теорема о рождественском чулке» . mathworld.wolfram.com . Проверено 1 ноября 2016 г. {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )

[3] Меррис, Рассел (2003). Комбинаторика (2-е изд.). Хобокен, Нью-Джерси: Wiley-Interscience. п. 45. ИСБН 0-471-45849-Х . OCLC 53121765 .

[1]

[2]

[3]