Evaluar y probar por inducción: $\sum k{n\choose k},\sum \frac{1}{k(k+1)}$

Question

1. $\displaystyle 0\cdot \binom{n}{0} + 1\cdot \binom{n}{1} + 2\binom {n} {2} + \cdots + (n-1) \cdot \binom{n}{n-1}+n\cdot \binom{n}{n}$

2. $\displaystyle\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3}+\frac{1}{3\cdot 4} +\cdots+\frac{1}{(n-1)\cdot n}$

¿Cómo encontrar la suma de estos y probar por inducción? ¿Puede alguien ayudarme a pasar por esto?

Answer 1

Para el primero de ellos, le piden que encuentre

$$\sum\limits_{k=0}^n k{n \choose k}$$

Puesto que los coeficientes binomiales tienen la simetría de $n-k$, podemos poner

$$\sum\limits_{k=0}^n (n-k){n \choose n-k}$$

por lo tanto

$$S_n = \sum\limits_{k=0}^n k{n \choose k}=\sum\limits_{k=0}^n (n-k){n \choose n-k}$$

Pero el lado derecho es

$$n\sum\limits_{k=0}^n {n \choose n-k}-\sum\limits_{k=0}^n k{n \choose n-k}$$

Ahora

$$S_n=n\sum\limits_{k=0}^n {n \choose k}-\sum\limits_{k=0}^n k{n \choose k}$$

o

$$S_n=n\sum\limits_{k=0}^n {n \choose k}-S_n$$

$$S_n=n2^n-S_n$$

$$2 S_n=n2^n$$

$$S_n=n2^{n-1}$$

El segundo se convierte en fácil una vez que haga uso de la propiedad telescópica le has sugerido ya.

Answer 2

La respuesta de lhf ha tratado ya con la segunda cuestión planteada aquí. Aquí está un artículo de Wikipedia al respecto.

He aquí un enfoque probabilístico para la primera pregunta. Cuando lanzas una moneda $n$ veces, la probabilidad de que una "cabeza" aparece exactamente $k$ veces es $\dbinom n k (1/2)^n$. El número promedio de veces que un "jefe" que aparece es por lo tanto $$\left( \binom n 0 \cdot 0 + \binom n 1 \cdot 1 + \binom n 2 \cdot 2 + \cdots + \binom n k \cdot k + \cdots + \binom n \cdot n \right) \left(\frac 1 2 \right)^n.$$ Pero el número promedio de veces que un "jefe" que aparece es obviamente $n/2$. Por lo tanto $$\left( \binom n 0 \cdot 0 + \binom n 1 \cdot 1 + \binom n 2 \cdot 2 + \cdots + \binom n k \cdot k + \cdots + \binom n \cdot n \right) \left(\frac 1 2 \right)^n = \frac n 2.$$ En consecuencia $$\binom n 0 \cdot 0 + \binom n 1 \cdot 1 + \binom n 2 \cdot 2 + \cdots + \binom n k \cdot k + \cdots + \binom n \cdot n = n 2^{n-1} .$$

Answer 3

1) tomar $\displaystyle f(x)= \sum_{i=0}^n\binom{n}{i} x^i=(x+1)^n$. Ahora consideremos $f'(1)$.

2) Utilice que $\frac{1}{(k-1)\cdot k} = \frac{1}{k-1} -\frac{1}{k}$.

Answer 4

Si usted no tiene el uso de la inducción, usted puede hacer esto:

1) $$\sum_k k\binom{n}{k} = \sum_k k \frac{n(n-1)\cdots(n-k+1)}{k!} = n\sum_k \binom{n-1}{k-1} = n \sum_k \binom{n-1}{k} = n2^{n-1}$$ Aquí $k$ ejecuta a través de todos los números enteros y, por convención, $\binom{n}{k}$ se define como cero si $k<0$ o $k > n$. La última igualdad se sigue del hecho de que $\binom{n-1}{k}$ cuenta el $k$-elemento de subconjuntos de a $\{1,\ldots,n-1\}$, lo $\sum_k \binom{n-1}{k}$ cuenta el número de todos los subconjuntos que es $2^{n-1}$.

2) tenga en cuenta que$\frac{1}{k(k+1)} = \frac{1}{k}-\frac{1}{k+1}$, por lo que la suma es un telescopio suma: $$\sum_{k=1}^{n-1} \frac{1}{k(k+1)} = \sum_{k=1}^{n-1}\left( \frac{1}{k} - \frac{1}{k+1}\right) = 1 - \frac{1}{n}$$

Answer 5

Algunas de las distintas maneras de demostrar $\sum_k k\binom{n}{k} = n2^{n-1}$ fueron sugeridas. Voy a añadir una combinatoria de prueba por un doble conteo. Considere la posibilidad de pares $(a,A)$ se $A$ es un subconjunto de a$\{1,\ldots,n\}$$a \in A$. El número de pares es $\sum_k k\binom{n}{k}$ ya que hay $\binom{n}{k}$ maneras de elegir un $k$-elemento subconjunto $A$ y, a continuación, $k$ posibilidades para elegir $a \in A$. Por otro lado, puede que el primer elija $a \in \{1,\ldots,n\}$ y, a continuación, agregue cualquier subconjunto de los restantes $n-1$ elementos para hacer de $A$, por lo $n2^{n-1}$ posibilidades. Comparando los dos resultados muestra que $\sum_k k\binom{n}{k} = n2^{n-1}$.