Dimostrazione per induzione...
ciao a tutti... 
volevo cercare di fare una piccola dimostrazione riguardo un equivalenza del coefficente binomiale.Riporto la breve definizione:
Qualunque siano $\alpha in R$ e $k in N-{1}$ indichiamo ora con $p(\alpha,k)$ il prodotto dei $k$ numeri che si ottengono sottraendo da $\alpha$ rispettivamente $0,1...K-1$. Orbene il rapporto dei numeri $p(\alpha,k)$ e $k!$ si chiama coefficiente binomiale.Nel caso $\alpha=n in N $ si ha $(n(n-1)...(n-k+1))/(k!)$ è equivalente a $ (n!)/(k!(n-k)!)$. In tutto ciò.... l'intento della mia dimostrazione è solo questo:
tesi:$p(n,k)(n-k)! =n!$
Dim
per n=1 essendo $k in N-{1}$ $(n-k)!n=0!*1=1$
Supponiamo $n(n-1)...(n-k+1)1...(n-k)=1...n$
$(n+1)(n+1-1)...(n+1+1-k)1...(n+1-k)=1...(n+1)$
$(n+1)n...(n+2-k)1...(n+1-k)=1...(n+1)$
Io nn sono "portato per la matematica"
la mia domanda è ho dimostrato effettivamente qualcosa ( è una valida dimostrazione... per quanto facile)???
volevo cercare di fare una piccola dimostrazione riguardo un equivalenza del coefficente binomiale.Riporto la breve definizione:Qualunque siano $\alpha in R$ e $k in N-{1}$ indichiamo ora con $p(\alpha,k)$ il prodotto dei $k$ numeri che si ottengono sottraendo da $\alpha$ rispettivamente $0,1...K-1$. Orbene il rapporto dei numeri $p(\alpha,k)$ e $k!$ si chiama coefficiente binomiale.Nel caso $\alpha=n in N $ si ha $(n(n-1)...(n-k+1))/(k!)$ è equivalente a $ (n!)/(k!(n-k)!)$. In tutto ciò.... l'intento della mia dimostrazione è solo questo:
tesi:$p(n,k)(n-k)! =n!$
Dim
per n=1 essendo $k in N-{1}$ $(n-k)!n=0!*1=1$Supponiamo $n(n-1)...(n-k+1)1...(n-k)=1...n$
$(n+1)(n+1-1)...(n+1+1-k)1...(n+1-k)=1...(n+1)$
$(n+1)n...(n+2-k)1...(n+1-k)=1...(n+1)$
Io nn sono "portato per la matematica"
la mia domanda è ho dimostrato effettivamente qualcosa ( è una valida dimostrazione... per quanto facile)???
Risposte
Il teorema che ti proponi di dimostrare è sicuramente falso, quindi non hai dimostrato nulla.
Che sia falso te ne accorgi da quanto hai scritto prima dell'enunciato: infatti da $p(n,k)=(n!)/(k! (n-k)!)$ segue immediatamente che:
$n! >= (n!)/(k!) = p(n,k) (n-k)!$
(il $>=$ dipende dal fatto che $k!>=1$) e, se $k>1$, la precedente disuguaglianza diventa stretta ossia:
$n! > p(n,k) (n-k)!$.
Che sia falso te ne accorgi da quanto hai scritto prima dell'enunciato: infatti da $p(n,k)=(n!)/(k! (n-k)!)$ segue immediatamente che:
$n! >= (n!)/(k!) = p(n,k) (n-k)!$
(il $>=$ dipende dal fatto che $k!>=1$) e, se $k>1$, la precedente disuguaglianza diventa stretta ossia:
$n! > p(n,k) (n-k)!$.
ma infatti $n(n-1)...(n-k+1) != (n!)/(k!(n-k)!)$ ovvero $p(n,k) != (n!)/(k!(n-k)!)$ .Io ho premesso che $(n(n-1)...(n-k+1))/(k!) = (n!)/(k!(n-k)!)$...... 
Allora scusa, ho frainteso i simboli. 
Ad ogni modo, non credo che ci sia bisogno di dimostrare qualcosa per induzione.
Infatti, per fissati $k<=n \in NN$, la proprietà $p(n,k)*(n-k)! =n!$ discende direttamente dalla definizione di fattoriale, applicando la proprietà associativa della moltiplicazione ai fattori $n-k,n-k-1,\ldots, 2,1$ dentro il prodotto che definisce $n!$.
Ad ogni modo, non credo che ci sia bisogno di dimostrare qualcosa per induzione.
Infatti, per fissati $k<=n \in NN$, la proprietà $p(n,k)*(n-k)! =n!$ discende direttamente dalla definizione di fattoriale, applicando la proprietà associativa della moltiplicazione ai fattori $n-k,n-k-1,\ldots, 2,1$ dentro il prodotto che definisce $n!$.
@Gugo82 Mi pare che l'autore definisca $p(\alpha,k)=\alpha(\alpha-1)\cdots(\alpha-k+1)$ - dunque la sua tesi dovrebbe essere giusta.
Sul senso della dimostrazione sono molto dubbioso - l'induzione si usa per evitare perifrasi del tipo
" il prodotto dei k numeri che si ottengono sottraendo da α rispettivamente 0,1...K-1." e in generale i "puntini".
Se si ammettono ragionamenti del genere l'induzione non ha molto senso
La cosa avrebbe senso se si definisse $\p(\alpha,k)$ ricorsivamente, cioe'
$p(\alpha,0):=1$, $p(\alpha,k+1):=p(\alpha,k)(\alpha-k)$
Se anche il fattoriale (come dovrebbe ) e' definito ricorsivamente:
$0!:=1$, $(n+1)!:=n!(n+1)$,
allora l'eguaglianza
$p(n,k)(n-k)! =n!$ per $n\geq0$ e $0\leq k\leq n$
e' un teorema e si deve per forza dimostrare per induzione
EDIT Scusa Gugo - scrivevo in contemporanea
EDIT 2 Chiaramente c'era $(n-k)!$ e non $k!$ (lho corretto)
Sul senso della dimostrazione sono molto dubbioso - l'induzione si usa per evitare perifrasi del tipo
" il prodotto dei k numeri che si ottengono sottraendo da α rispettivamente 0,1...K-1." e in generale i "puntini".
Se si ammettono ragionamenti del genere l'induzione non ha molto senso
La cosa avrebbe senso se si definisse $\p(\alpha,k)$ ricorsivamente, cioe'
$p(\alpha,0):=1$, $p(\alpha,k+1):=p(\alpha,k)(\alpha-k)$
Se anche il fattoriale (come dovrebbe ) e' definito ricorsivamente:
$0!:=1$, $(n+1)!:=n!(n+1)$,
allora l'eguaglianza
$p(n,k)(n-k)! =n!$ per $n\geq0$ e $0\leq k\leq n$
e' un teorema e si deve per forza dimostrare per induzione
EDIT Scusa Gugo - scrivevo in contemporanea
EDIT 2 Chiaramente c'era $(n-k)!$ e non $k!$ (lho corretto)
Provo a scrivere la dimostrazione della proprieta' (che non e' banalissima mi pare)
Bisogna arrivarci per gradi.
Prima di tutto vediamo che ogni $k$ si ha
(1) $P(n+1,k+1)=(n+1)p(n,k)$
(notiamo che (1) diventa $0=0$ se $k$ supera $n$ - anche questo si dimostra ...)
DIM(induzione su $k$)
Caso $k=0$
Devo dimostrare $P(n+1,1)=(n+1) P(n,0)$. A destra ho (n+1) in quanto $P(n,0)=1$
A sinistra ho $P(n+1,0+1)=P(n+1,0)(n+1)=n+1$. Quindi la formula vale
Passo induttivo
Supponiamo che (1) valga per $k$. Allora
$P(n+1,k+2)=P(n+1,k+1)(n+1-(k+1))=(n+1)P(n,k)(n-k)=(n+1)P(n,k+1)$
(il primo e il terzo "$=$" sono le definizioni ricorsive di $P$ - quello in mezzo l'ipotesi induttiva)
Quindi il passo induttivo e' vero
Ne segue che la (1) vale.
Passiamo a verificare che per ogni $n$
(2) $P(n,n)=n!$
DIM (per induzione su $n$)
Passo $n=0$. Devo verificare $P(0,0)=0!$ che vale per le varie definizioni.
Passo induttivo, Suppongo la (2) vera pr $n$. Allora
$P(n+1,n+1)=(n+1)P(n,n)=(n+1)n!=(n+1)!$
( ho usato prima la (1) e poi l'ipotesi induttiva e infine la definizione ricorsiva del fattoriale)
Dimostriamo infine che per ogni $n,k$ interi con $0\leq k\leq n$ si ha
(3) $P(n,k)(n-k)! = n!$
DIM. Fisso $k\geq0$ e dimostro per induzione su $n$ che la (3) vale per ogni $n\geq k$
Passo iniziale $n=k$. Devo verificare che $P(k,k)0! =k!$ - questa e' conseguanza di (2).
Passo induttivo. Suppongo la (3) valida per $n$. Allora
$P(n+1,k)(n+1-k)! =(n+1)P(n,k-1)(n+1-k)(n-k)!
$\quad = (n+1)P(n,k-1)(n-(k-1))(n-k)! $
$\quad =(n+1)P(n,k)(n-k)! $
$\quad =(n+1)n! =(n+1)!$
(usando nell'ordine la (2), la definizione ricorsiva di $P$, l'ipotesi induttiva e la definizione ricorsiva del fattoriale)
Tutto questo per la precisione
(cioe' per evitare i puntini 
)
Bisogna arrivarci per gradi.
Prima di tutto vediamo che ogni $k$ si ha
(1) $P(n+1,k+1)=(n+1)p(n,k)$
(notiamo che (1) diventa $0=0$ se $k$ supera $n$ - anche questo si dimostra ...)
DIM(induzione su $k$)
Caso $k=0$
Devo dimostrare $P(n+1,1)=(n+1) P(n,0)$. A destra ho (n+1) in quanto $P(n,0)=1$
A sinistra ho $P(n+1,0+1)=P(n+1,0)(n+1)=n+1$. Quindi la formula vale
Passo induttivo
Supponiamo che (1) valga per $k$. Allora
$P(n+1,k+2)=P(n+1,k+1)(n+1-(k+1))=(n+1)P(n,k)(n-k)=(n+1)P(n,k+1)$
(il primo e il terzo "$=$" sono le definizioni ricorsive di $P$ - quello in mezzo l'ipotesi induttiva)
Quindi il passo induttivo e' vero
Ne segue che la (1) vale.
Passiamo a verificare che per ogni $n$
(2) $P(n,n)=n!$
DIM (per induzione su $n$)
Passo $n=0$. Devo verificare $P(0,0)=0!$ che vale per le varie definizioni.
Passo induttivo, Suppongo la (2) vera pr $n$. Allora
$P(n+1,n+1)=(n+1)P(n,n)=(n+1)n!=(n+1)!$
( ho usato prima la (1) e poi l'ipotesi induttiva e infine la definizione ricorsiva del fattoriale)
Dimostriamo infine che per ogni $n,k$ interi con $0\leq k\leq n$ si ha
(3) $P(n,k)(n-k)! = n!$
DIM. Fisso $k\geq0$ e dimostro per induzione su $n$ che la (3) vale per ogni $n\geq k$
Passo iniziale $n=k$. Devo verificare che $P(k,k)0! =k!$ - questa e' conseguanza di (2).
Passo induttivo. Suppongo la (3) valida per $n$. Allora
$P(n+1,k)(n+1-k)! =(n+1)P(n,k-1)(n+1-k)(n-k)!
$\quad = (n+1)P(n,k-1)(n-(k-1))(n-k)! $
$\quad =(n+1)P(n,k)(n-k)! $
$\quad =(n+1)n! =(n+1)!$
(usando nell'ordine la (2), la definizione ricorsiva di $P$, l'ipotesi induttiva e la definizione ricorsiva del fattoriale)
Tutto questo per la precisione
(cioe' per evitare i puntini )
[OT puntinistico]
VG, sono d'accordo sull'evitare puntini, giacché possono in linea di principio essere sostituiti con qualunque cosa (in proposito c'è tutta una bella discussione su Wittgenstein, Lezioni sui Fondamenti della Matematica).
Però qui mi pare si stia abusando di scarso buon senso.
In $NN$ abbiamo già definito un prodotto e sappiamo già che esso gode della proprietà commutativa, associativa, etc... (nel senso che le abbiamo dimostrate).
Sappiamo che l'associatività rende possibile definire in maniera non ambigua il prodotto di $n \in NN, n>=2$ numeri naturali $x_1,\ldots, x_n$ fissati, proprio perchè ovunque si scelga di "piazzare" un paio di parentesi $()$ il risultato non cambia; tale prodotto si denota col simbolo $\prod_(i=1)^n x_i$ (in cui non figurano puntini!).
Inoltre, la commutatività ci garantisce che se fissiamo una permutazione $\sigma:\{1,\ldots ,n\} \to \{1,\ldots ,n\}$, allora risulta $prod_(i=1)^n x_(sigma(i))=\prod_(i=1)^n x_i$.
Ora, per definizione poniamo $n! :=\prod_(i=1)^n i$ (di modo che $n!$ è, come al solito, il prodotto di tutti i numeri naturali non maggiori di $n$; non ho usato una definizione ricorsiva perchè non ce n'è bisogno).
Applicando la proprietà associativa per "raggruppare" i primi $n-k$ (qui $k<=n$; se $k=n$ non c'è bisogno di raggruppare nulla) fattori del prodotto che definisce $n!$ si ottiene:
$n! = (prod_(i=n-k+1)^n i)*(\prod_(i=1)^(n-k) i)=(prod_(i=n-k+1)^n i)*(n-k)!$
e questo è tutto, dato che si è posto per definizione $p(n,k):=prod_(i=n-k+1)^n i$.
[/OT]
VG, sono d'accordo sull'evitare puntini, giacché possono in linea di principio essere sostituiti con qualunque cosa (in proposito c'è tutta una bella discussione su Wittgenstein, Lezioni sui Fondamenti della Matematica).
Però qui mi pare si stia abusando di scarso buon senso.
In $NN$ abbiamo già definito un prodotto e sappiamo già che esso gode della proprietà commutativa, associativa, etc... (nel senso che le abbiamo dimostrate).
Sappiamo che l'associatività rende possibile definire in maniera non ambigua il prodotto di $n \in NN, n>=2$ numeri naturali $x_1,\ldots, x_n$ fissati, proprio perchè ovunque si scelga di "piazzare" un paio di parentesi $()$ il risultato non cambia; tale prodotto si denota col simbolo $\prod_(i=1)^n x_i$ (in cui non figurano puntini!
).Inoltre, la commutatività ci garantisce che se fissiamo una permutazione $\sigma:\{1,\ldots ,n\} \to \{1,\ldots ,n\}$, allora risulta $prod_(i=1)^n x_(sigma(i))=\prod_(i=1)^n x_i$.
Ora, per definizione poniamo $n! :=\prod_(i=1)^n i$ (di modo che $n!$ è, come al solito, il prodotto di tutti i numeri naturali non maggiori di $n$; non ho usato una definizione ricorsiva perchè non ce n'è bisogno).
Applicando la proprietà associativa per "raggruppare" i primi $n-k$ (qui $k<=n$; se $k=n$ non c'è bisogno di raggruppare nulla) fattori del prodotto che definisce $n!$ si ottiene:
$n! = (prod_(i=n-k+1)^n i)*(\prod_(i=1)^(n-k) i)=(prod_(i=n-k+1)^n i)*(n-k)!$
e questo è tutto, dato che si è posto per definizione $p(n,k):=prod_(i=n-k+1)^n i$.
[/OT]
Certo ma, a rigore la definizione di produttoria e' ricorsiva e tutte le sue proprieta' dovrebbero passare per l'induzione.
Non c'e' nessun modo rigoroso di definire $n!$ senza la ricorsione.
Ho effettivamente estremizzato la mia risposta, ma credo che "alla radice" i miei ragionamenti siano il modo piu' corretto di afforntare
la questione.
Quando avro' tempo leggero' il passo di Wittgenstein
EDIT (Parziale retromarcia) Mi dirai che vale la pena di definire una volta per tutte la produttoria, dimostrare le sue proprieta' e poi usarla - forse hai ragione;
io comunque trovo istruttivo dimostrare direttamente le proprieta' sopra e capire volta per volta cosa si sta usando.
Non c'e' nessun modo rigoroso di definire $n!$ senza la ricorsione.
Ho effettivamente estremizzato la mia risposta, ma credo che "alla radice" i miei ragionamenti siano il modo piu' corretto di afforntare
la questione.
Quando avro' tempo leggero' il passo di Wittgenstein
EDIT (Parziale retromarcia) Mi dirai che vale la pena di definire una volta per tutte la produttoria, dimostrare le sue proprieta' e poi usarla - forse hai ragione;
io comunque trovo istruttivo dimostrare direttamente le proprieta' sopra e capire volta per volta cosa si sta usando.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo