Induksjon oppgave

[hallapaadeg]

Hei lurer på denne oppgaven. Skal vise med induksjon at:


$\sum_{k=1}^{n} k \binom{n}{k}= n 2^{n-1}$, for $n \geq 1$

Lurer på hva jeg gjør feil.. Begynner med $n = 1$ og det stemmer.

Skal gå fra $n = m$ til $n = m+1$

Tenker at $\sum_{k = 1}^{m + 1} k \binom{m+1}{k} = \sum_{k=1}^{m}k \binom{m}{k}+ \sum_{k = m+1}^{m+1} k \binom{m+1}{k} $


Slik at jeg prøver å få: $m 2^{m-1} + \sum_{k = m+1}^{m+1} k \binom{m+1}{k} = (m+1)2^{m}$

men det klarer jeg ikke. lurer på hva jeg gjør feil her håper noen kan hjelpe, takk

[Nebuchadnezzar]

Gir det et nytt forsøk. Problemet ditt er at du vil ende opp med

$
\begin{align*}
\text{VS}
& = \sum_{k=1}^{m+1} k \binom{ m + 1}{k} \\
& = (m+1) \binom{m+1}{m+1} + \sum_{k=1}^{m} k \binom{ m + 1}{k}
\end{align*}
$

Hvor jeg har trekt ut det $m+1$'te leddet ut av summen slik som deg. Merk at den siste summen IKKE er lik $m 2^{m-1}$ (ser ut som du har antatt det). Ser du hvorfor? For å skrive om summen må du ta i bruk følgende binomiske identitet

$ \hspace{1cm}
\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}
$

Deretter skifte indeksene slik at du kan benytte deg av induksjonshypotesen.