#1 raben 2009-07-24 13:25 Practica 2. Ejercicio 10. iv)
$$\sum_{k=0}^{n}{k.\binom{n}{k}} = n.2^{n-1}$$
HI: \(\sum_{i=0}^{k}{i.\binom{k}{i}} = k.2^{k-1}\)
Quiero probar que \(\sum_{i=0}^{k+1}{i.\binom{k+1}{i}} = (k+1).2^k\)
Podria empezar asi?:
$$\sum_{i=0}^{k+1}{i.\binom{k+1}{i}} =$$
$$\sum_{i=0}^{k}{i.\binom{k+1}{i}} + (k+1)\binom{k+1}{k+1} =$$
$$\sum_{i=1}^{k}{i.\binom{k+1}{i}} + 0 + (k+1)=$$
$$\sum_{i=1}^{k}{i.\left[\binom{k}{i}-\binom{k}{i-1}\right]} + (k+1)=$$
$$\sum_{i=0}^{k}{i.\binom{k}{i}} -\sum_{i=1}^{k}{i.\binom{k}{i-1}} + (k+1)=$$
por hipotesis inductiva....
$$k.2^{k-1} -\sum_{i=1}^{k}{i.\binom{k}{i-1}} + (k+1)=$$
Si hago cambio de indice j = i - 1 en la sumatoria
$$\sum_{i=1}^{k}{i.\binom{k}{i-1}} =$$
$$\sum_{j=0}^{k-1}{(j+1).\binom{k}{j}} =$$
$$\sum_{j=0}^{k-1}{j.\binom{k}{j}} + \sum_{j=0}^{k-1}{\binom{k}{j}} =$$
$$\sum_{j=0}^{k-1}{j.\binom{k}{j}} + k.\binom{k}{k} - k.\binom{k}{k} +\sum_{j=0}^{k-1}{\binom{k}{j}} =$$
$$\color{red}\sum_{j=0}^{k}{j.\binom{k}{j}} - k + \sum_{j=0}^{k-1}{\binom{k}{j}}$$
Entonces
$$k.2^{k-1} -{\color{red}\sum_{i=1}^{k}{i.\binom{k}{i-1}}} + (k+1)=$$
$$k.2^{k-1} -{\color{red}\left[\sum_{j=0}^{k}{j.\binom{k}{j}} - k + \sum_{j=0}^{k-1}{\binom{k}{j}}\right]} + (k+1)=$$
$$k.2^{k-1} -\sum_{j=0}^{k}{j.\binom{k}{j}} + k - \sum_{j=0}^{k-1}{\binom{k}{j}} + (k+1)=$$
usando otra vez la HI
$$k.2^{k-1} -k.2^{k-1} + k - \sum_{j=0}^{k-1}{\binom{k}{j}} + (k+1)=$$
$$k - \sum_{j=0}^{k-1}{\binom{k}{j}} + k+1=$$
$$2k +1 - \sum_{j=0}^{k-1}{\binom{k}{j}} {\color{red}= (k+1)2^k}$$
y tengo que probar esto ultimo...
Sea Q(k): \(\sum_{j=0}^{k-1}{\binom{k}{j}} = 2k +1 - (k+1)2^k\)
*Q(1):
$$\sum_{j=0}^{1-1}{\binom{1}{j}} = \binom{1}{0} = {\color{red}1}$$
$$2.1 +1 - (1+1)2^1 = 3 - 4 = {\color{red}-1}$$
*Q(2):
$$\sum_{j=0}^{2-1}{\binom{2}{j}} = \binom{2}{0} + \binom{2}{1} = 1 + 2 = {\color{red}3}$$
$$2.2 +1 - (2+1)2^2 = 5 - 3.4 = {\color{red}-7}$$
*Q(3):
$$\sum_{j=0}^{3-1}{\binom{3}{j}} = \binom{3}{0} + \binom{3}{1} + \binom{3}{2} = 1 + 3 + 3 = {\color{red}7}$$
$$2.3 +1 - (3+1)2^3 = {\color{red}-25}$$
No creo que se cumpla para ningun k natural, entonces que hice mal?
Que hice mal?
Adjunto lo que postee para que si alguien quiere corregirlo, no tenga que escribir tanto ;D
#3 ValeriaR 2010-07-28 18:36 Hola!
raben escribió:
Practica 2. Ejercicio 10. iv)
$$\sum_{k=0}^{n}{k.\binom{n}{k}} = n.2^{n-1}$$
HI: \(\sum_{i=0}^{k}{i.\binom{k}{i}} = k.2^{k-1}\)
Quiero probar que \(\sum_{i=0}^{k+1}{i.\binom{k+1}{i}} = (k+1).2^k\)
Podria empezar asi?:
$$\sum_{i=0}^{k+1}{i.\binom{k+1}{i}} =$$
$$\sum_{i=0}^{k}{i.\binom{k+1}{i}} + (k+1)\binom{k+1}{k+1} =$$
$$\sum_{i=1}^{k}{i.\binom{k+1}{i}} + 0 + (k+1)=$$
$$\color{red}\sum_{i=1}^{k}{i.\left[\binom{k}{i}-\binom{k}{i-1}\right]} + (k+1)=$$
Ahí está el error, porque entre los dos combinatorios va un +, no un menos.
$$\color{red}\sum_{i=1}^{k}{i.\left[\binom{k}{i}+\binom{k}{i-1}\right]} + (k+1)=$$
Pero aparte de eso la idea venía bien 😛...y de hecho todo el cambio de índices que hiciste después creo que también...la única diferencia es que te queda un más ahí, entonces te cambia lo que te queda al final..
Saludos!
a ver... la cosa es así:
$$P(n)\Rightarrow{P(n+1)}$$
$$\sum_{k=0}^{n+1}{k \displaystyle\binom{n+1}{k}}$$
(notar que si k empieza en 0 o en 1 es indistinto)
$$\sum_{k=1}^n{k[\displaystyle\binom{n}{k}+\displaystyle\binom{n}{k-1}]} +(n+1)$$
$$\sum_{k=1}^n{k \displaystyle\binom{n}{k}} + \sum_{k=1}^n{k \displaystyle\binom{n}{k-1}} + n+1$$
por hipotesis inductiva:
$$n 2^{n-1} + \sum_{k=1}^n{k \displaystyle\binom{n}{k-1}} + n+1 (*)$$
tomo\(\sum_{k=1}^n{k \displaystyle\binom{n}{k-1}}\)
$$\sum_{j=0}^{n-1}{(j+1)}\displaystyle\binom{n}{j}$$
$$(1)\sum_{j=0}^{n-1}{j \displaystyle\binom{n}{j}} + (2)\sum_{j=0}^{n-1}{\displaystyle\binom{n}{j}}$$
$$(2)\sum_{j=0}^{n-1}{\displaystyle\binom{n}{j}} = \sum_{j=0}^n{\displaystyle\binom{n}{j}} - \displaystyle\binom{n}{n}$$
\((1+1)^n = \sum_{j=0}^n{\displaystyle\binom{n}{j}}\) y \(\displaystyle\binom{n}{n} = 1\)
entonces \((2) = 2^n - 1\)
$$(1)\sum_{j=0}^{n-1}{j \displaystyle\binom{n}{j}} = \sum_{j=0}^{n}{j \displaystyle\binom{n}{j}} - n\displaystyle\binom{n}{n}$$
$$n2^{n-1}-n$$
finalmente (1) + (2) queda \(n2^{n-1}-n + 2^n - 1\)
vuelvo a \((*) = n2^{n-1}+n2^{n-1}-n+2^n-1+n+1\)
finalmente me queda \(2.n2^{n-1}+2^n\)