Sommatoria con coefficiente binomiale

[anto_zoolander]

Qualcuno mi aiuta a dimostrare per induzione che:

$sum_{k=0}^{n}$\(\displaystyle \binom{n}{k} \)$=2^n, forallninNN$

Ho provato a scrivere il tutto per esteso ma patate

Più che altro non riesco ad usare le ipotesi per $p(n+1)$

[axpgn]

Prova col Triangolo di Tartaglia ...

[dissonance]

O con la formula \((a+b)^n=\sum_{k=0}^n {n \choose k}a^kb^{n-k}\), scegliendo opportunamente $a$ e $b$.

[Palliit]

@axpgn: sono curioso, metti in spoiler ?

@dissonance: la richiesta era di dimostrare per induzione

Io farei così (metto il doppio spoiler per chi vuol vedere solo l'inizio):

$ sum_{k=0}^{n+1} $\( \displaystyle \binom{n+1}{k} \)$=sum_{k=0}^{n} $\( \displaystyle \binom{n+1}{k} \)$ +1=sum_{k=0}^{n} (n+1)/(n+1-k)$\( \displaystyle \binom{n}{k} \)$ +1" "=sum_{k=0}^{n} [1+k/(n+1-k)]$\( \displaystyle \binom{n}{k} \)$ +1=$

$=" "sum_{k=0}^{n} $\( \displaystyle \binom{n}{k} \)$ +sum_{k=0}^{n} k/(n+1-k)$\( \displaystyle \binom{n}{k} \)$ +1" "=" "2^n+sum_{k=1}^{n} k/(n+1-k)*(n"!")/(k"!"(n-k)"!")+1" "=$

$=" "2^n+sum_{k=1}^{n} (n"!")/((k-1)"!"(n-k+1)"!")+1" "=" "2^n+sum_{k=1}^{n} $\( \displaystyle \binom{n}{k-1} \)$+1" "=$

$=" "2^n+sum_{j=0}^{n-1} $\( \displaystyle \binom{n}{j} \)$+1" "=" "2^n+sum_{j=0}^{n} $\( \displaystyle \binom{n}{j} \)$" "=" "2^n+2^n" "=" "2^(n+1)$

ma sicuramente esiste un metodo più economico.

[axpgn]

@Palliit

È una versione informale ...

La tesi è che la somma dei numeri di ogni riga $n$ del triangolo è pari a $2^n$ (se assumiamo che la prima riga sia $n=0$, altrimenti se partiamo a contare da $1$ sarà pari a $2^(n-1)$).
Per il passo base userei la versione forte (per evitare ambiguità), e cioè $P(0)=2^0=1$ (la prima riga è composta solo dall'uno) ed anche $P(1)=2^1=2=1+1$.
Per il passo induttivo, possiamo notare che ogni numero interno della riga $n+1$ è la somma dei due numeri "sovrastanti" nella riga $n$ perciò gli "interni sopra" compaiono due volte negli "interni sotto", gli "uni sopra" compaiono solo una volta ma vanno aggiunti i due "uni sotto" perciò la riga "n+1" somma il doppio della riga "n".
Ma dato che i numeri di ogni riga $n$ sono tutti i valori che può assumere $((n),(k))$ al variare di $k$ da zero a $n$, ecco dimostrato il passo induttivo e con esso la tesi.


Non ho scritto quello che ha messo dissonance perchè mi pare di aver capito (da un altro post) che la conoscesse gia ...

Cordialmente, Alex

[anto_zoolander]

Intanto grazie a tutti

"dissonance":O con la formula \((a+b)^n=\sum_{k=0}^n {n \choose k}a^kb^{n-k}\), scegliendo opportunamente $a$ e $b$.

Si con il binomio di Newton l'avevo già dimostrata scegliendo $a=b=1$, volevo farlo per induzione.
Più che altro per una relazione tra questa somma e un insieme delle parti


@Pallit ora me la guardo per bene