Esercizio sul principio di induzione
Buonasera, ho svolto il seguente esercizio che consiste nel dimostrare che, per ogni \(\displaystyle n\ge 1 \),
\(\displaystyle \sum_{k=0}^n k\binom{n}{k}=n*2^{n-1}\),
non riporto le proprietà del principio di induzione, per passo induttivo si ha
\(\displaystyle \sum_{k=0}^{n+1} k\binom{n+1}{k}=\sum_{k=0}^n k\binom{n}{k}+\sum_{k=-1}^n k\binom{n}{k-1}=n*2^{n-1}+n*2^{n-2}\).
Grazie per la risposta !
A presto
\(\displaystyle \sum_{k=0}^n k\binom{n}{k}=n*2^{n-1}\),
non riporto le proprietà del principio di induzione, per passo induttivo si ha
\(\displaystyle \sum_{k=0}^{n+1} k\binom{n+1}{k}=\sum_{k=0}^n k\binom{n}{k}+\sum_{k=-1}^n k\binom{n}{k-1}=n*2^{n-1}+n*2^{n-2}\).
Grazie per la risposta !
A presto
Risposte
E il termine di indice $n+1$ che fine ha fatto?
Ciao galles90,
Si richiede di dimostrare che si ha:
[tex]\displaystyle \sum_{k=0}^n k \binom{n}{k} = \sum_{k=1}^n k \binom{n}{k} = n 2^{n-1}[/tex] $ qquad qquad \AA n \ge 1 $
(la somma può partire da $k = 1 $ in quanto ovviamente il contributo del termine con $ k = 0 $ è nullo).
Per $n = 1 $ è senz'altro vera perché
[tex]\displaystyle \sum_{k=0}^1 k \binom{1}{k} = 0 + 1 = 1 = 1 \cdot 2^{1 - 1}[/tex]
Ma sei sicuro di dover per forza fare uso del principio di induzione?
Altrimenti è più semplice ricordare che
[tex]\displaystyle \binom{n}{k} = \frac{n}{k} \binom{n - 1}{k - 1}[/tex]
e che ponendo $a = b = 1 $ nel binomio di Newton si ottiene
[tex]\displaystyle 2^n = \sum_{k=0}^n \binom{n}{k} \implies 2^{n - 1} = \sum_{k=0}^{n - 1} \binom{n - 1}{k}[/tex]
Dunque si ha:
[tex]\displaystyle \sum_{k=0}^n k \binom{n}{k} = \sum_{k=1}^n k \binom{n}{k} = \sum_{k=1}^n n \binom{n - 1}{k - 1} = n \sum_{k=1}^n \binom{n - 1}{k - 1} = n \sum_{j=0}^{n - 1} \binom{n - 1}{j} = n2^{n - 1}[/tex]
Si richiede di dimostrare che si ha:
[tex]\displaystyle \sum_{k=0}^n k \binom{n}{k} = \sum_{k=1}^n k \binom{n}{k} = n 2^{n-1}[/tex] $ qquad qquad \AA n \ge 1 $
(la somma può partire da $k = 1 $ in quanto ovviamente il contributo del termine con $ k = 0 $ è nullo).
Per $n = 1 $ è senz'altro vera perché
[tex]\displaystyle \sum_{k=0}^1 k \binom{1}{k} = 0 + 1 = 1 = 1 \cdot 2^{1 - 1}[/tex]
Ma sei sicuro di dover per forza fare uso del principio di induzione?
Altrimenti è più semplice ricordare che
[tex]\displaystyle \binom{n}{k} = \frac{n}{k} \binom{n - 1}{k - 1}[/tex]
e che ponendo $a = b = 1 $ nel binomio di Newton si ottiene
[tex]\displaystyle 2^n = \sum_{k=0}^n \binom{n}{k} \implies 2^{n - 1} = \sum_{k=0}^{n - 1} \binom{n - 1}{k}[/tex]
Dunque si ha:
[tex]\displaystyle \sum_{k=0}^n k \binom{n}{k} = \sum_{k=1}^n k \binom{n}{k} = \sum_{k=1}^n n \binom{n - 1}{k - 1} = n \sum_{k=1}^n \binom{n - 1}{k - 1} = n \sum_{j=0}^{n - 1} \binom{n - 1}{j} = n2^{n - 1}[/tex]
Buonasera grazie ad entrambi per le risposte, ora rispondo solo ad otto96, invece ad pilloeffe voglio rileggermi la risposta che mi ha dato.
L'indice dove lo devo riportare sola sulla sommatoria, oppure sulla sommatoria e nel coefficiente binomiale.
Ciao
L'indice dove lo devo riportare sola sulla sommatoria, oppure sulla sommatoria e nel coefficiente binomiale.
Ciao
Solo nella sommatoria manca l'$n+1$-esimo termine, nel coefficiente binomiale è giusto che vada via perché lo dice la formula.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo