Suma de coeficientes binomiales con aumento$n$

Question

¿Existe alguna fórmula para calcular$$\binom{n}{1} + \binom{n+1}{2} + \binom{n+2}{3} + ... + \binom{n+m}{m+1}$ $

He intentado el método iterativo, pero existe algún método de tiempo constante.

Answer 1

Vamos a añadir en un valor inicial de $1 = \binom{n}{0}$. La relación fundamental

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

hace que la suma telescopio:

$$\eqalign{ &\color{Blue}{\binom{n}{0} + \binom{n}{1}} &+\binom{n+1}{2} &+ \binom{n+2}{3} + \cdots &+ \binom{n+m}{m+1} \\ & =\color{Blue}{\binom{n+1}{1}} & +\color{Blue}{\binom{n+1}{2}} &+ \binom{n+2}{3} + \cdots &+ \binom{n+m}{m+1} \\ & &=\color{Blue}{\binom{n+2}{2}} & +\color{Blue}{\binom{n+2}{3}}+ \cdots &+ \binom{n+m}{m+1} \\ & & & = \cdots \\ & & & = \color{Blue}{\binom{n+m}{m}} &+\color{Blue}{ \binom{n+m}{m+1}} \\ & & & &= \binom{n+m+1}{m+1}. }$$

Restando el $1$ agregó originalmente en el da la respuesta, $\binom{n+m+1}{m+1}-1$.

Answer 2

$\binom{n+1}{2} = \binom{n}{1} + \binom{n}{2} = \binom{n}{1} + \frac{n-1}{2} \binom{n}{1}$

$\binom{n+2}{3} = \binom{n+1}{2} + \binom{n+1}{3} = \binom{n+1}{2} + \frac{n-1}{2} \binom{n+1}{2}$

$\binom{n+3}{4} = \binom{n+2}{3} + \binom{n+2}{4} = \binom{n+2}{3} + \frac{n-1}{3} \binom{n+2}{3}$

...

...

$\binom{n+m}{m} = \binom{n+m-1}{m-1} + \binom{n+m-2}{m} = \binom{n+m-1}{m-1} + \frac{n-1}{m-1}\binom{n+m-1}{m-1} $

Comience con$n$ y almacene cada valor a partir de$\binom{n+1}{2}$ para calcular la operación$\binom{n+2}{3}$ [O (1) y así sucesivamente.