teoria binomiale

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: teoria binomiale

Messaggio da fph »

Questa era l'idea che ha suggerito anche RiccardoKelso, che non si riesce a far funzionare proprio per il motivo che hai detto tu. Quello che stai cercando di fare, però, è ridimostrare tutto da zero senza usare il ragionamento induttivo che hai fatto nel tuo post sopra: quello produceva davvero un fattore $k!$.

Come ti dicevo, quel ragionamento è già quasi tutto il lavoro; ora devi solo sistemare le cose in modo che quella buffa induzione su due parametri funzioni. Chiama $P(k,n)$ l'enunciato $k! \mid \frac{n!}{(n-k)!}$; quali ipotesi induttive ti servono per dimostrare $P(k,n)$? Quali sono i valori di k,n per cui non riesci a ricondurti a due "casi più bassi"? Riesci a fare a mano questi casi?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Nadal21

Re: teoria binomiale

Messaggio da Nadal21 »

Guarda, ci ho provato ma non riesco a mostrare che fissato $n$ se vale per $k$ allora vale per $k+1$ con quella differenza, tu comee suggerisci di fare?
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: teoria binomiale

Messaggio da fph »

Aumentare $k$ direttamente è difficile, hai ragione. Il modo che ho in testa io è questo: parti facendo un'induzione su $k$; quindi, puoi dare per buono $P(n,h)$ per ogni $n$ e ogni $h<k$, e devi dimostrare $P(n,k)$ per ogni $n$ (e un certo $k$ fissato). Ora, dimostriamo $P(n,k)$ con un'altra induzione, questa volta su $n$: il caso base è $P(0,k)$ (o se gli zeri ti spaventano puoi partire da $P(k,k)$ che è altrettanto ovvio), e questa volta puoi usare sia $P(n-1,k)$ che $P(n-1,k-1)$ senza timore, visto che vengono dalle due ipotesi induttive.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Nadal21

Re: teoria binomiale

Messaggio da Nadal21 »

Ok grazie, penso di aver capito!!
Claudio.
Messaggi: 698
Iscritto il: 29 nov 2009, 21:34

Re: teoria binomiale

Messaggio da Claudio. »

Oppure si può usare questa, che si dimostra semplicemente facendo i calcoli ( la regola del triangolo di Tartaglia o di Pascal):
$ \displaystyle \binom{n+1}{k+1}=\binom{n}{k+1}+\binom{n}{k}$
Adesso basta dire che $\binom{0}{0}$ e $\binom{n}{n}$ sono interi e la tesi segue per induzione.
Nadal21

Re: teoria binomiale

Messaggio da Nadal21 »

Dimostriamo la tesi per induzione su $n$ con $k$ fissato.

Passo Induttivo: supponiamo che fino a un $k$ fissato si sia dimostrato $\forall k\leq h<n$ che è vero $k!\mid h(h-1)\cdots (h-k+1)$ . Mostriamolo per $n$.
Consideriamo ora la seguente uguaglianza:

$ n(n-1)(n-2)\cdots (n-k+1) - (n-1)(n-2)\cdots (n-k) = k(n-1)(n-2)\cdots(n-k+1) $

Per hp induttiva ho $k!\mid (n-1)(n-2)\cdots (n-k)$, e inoltre per hp induttiva $(k-1)!\mid (n-1)(n-2)\cdots (n-k+1)$: poiché questa quantità è moltiplicata per $k$ nell'RHS allora quest'ultimo sarà pure multiplo di $k!$. Poiché l'uguaglianza coinvolge solo numeri interi si ha che siccome $k!$ divide due dei tre termini dell'espressione, allora dividerà anche il terzo, in particolare dunque
$k!\mid n(n-1)\cdots (n-k+1)$
che è quanto si voleva dimostrare.

Passo Base: mostriamo che $\forall k$ è vero che $\binom{k!}{(k-1)!} \in \mathbb{N}$

$\binom{k!}{(k-1)!}=\dfrac{k!}{(k-1)!\cdot 1!}=k \in \mathbb{N}$ CVD.
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: teoria binomiale

Messaggio da fph »

Ti manca la parte di induzione su $k$. Altrimenti non puoi usare nella dimostrazione $(k-1)! \mid (n-1)(n-2)\dotsm(n-k+1)$, perché non viene da nessuna delle ipotesi induttive che hai già dimostrato.

(anche l'idea di Claudio funziona, by the way, ed è più semplice di quella che avevo in mente io. :)
Ma anche lì va capito bene su cosa si fa induzione e in che ordine: per esempio secondo me i passi base che ha scritto lui non sono sufficienti per concludere.)
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Claudio.
Messaggi: 698
Iscritto il: 29 nov 2009, 21:34

Re: teoria binomiale

Messaggio da Claudio. »

fph ha scritto:...
(anche l'idea di Claudio funziona, by the way, ed è più semplice di quella che avevo in mente io. :)
Ma anche lì va capito bene su cosa si fa induzione e in che ordine: per esempio secondo me i passi base che ha scritto lui non sono sufficienti per concludere.)
Beh effettivamente bisogna precisare che bisogna usare una sorta di induzione forte. Ossia prendi come ipotesi che $ \binom nk $ sia intero per ogni $0\le k\le n$ e usando la formula mostri che $\binom {n+1}k$ è intero per $0< k<n+1$. I casi $\binom n n $ e $\binom n 0$ mi pare vadano trattati separatamente, ma chiaramente non sono un problema.
Fbuonarroti
Messaggi: 30
Iscritto il: 01 gen 2016, 15:05

Re: teoria binomiale

Messaggio da Fbuonarroti »

Metto una dimostrazione senza induzione:
Riscriviamoci il tutto come $ \dfrac { n(n-1)...(n-k+1)}{k!} $ , questo è un polinomio in $ n $ con radici $ 1,2,3 ... k-1 $.
Ora, se $ n < k $ è chiaro che il tutto fa $ 0 $ perché $ n $ è radice del polinomio.
Se $ n>k $ allora si ha un prodotto di $ k $ interi consecutivi divisi per $ k! $ e questo è certamente un intero
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: teoria binomiale

Messaggio da fph »

Fbuonarroti ha scritto: Se $ n>k $ allora si ha un prodotto di $ k $ interi consecutivi divisi per $ k! $ e questo è certamente un intero
È proprio di questo "certamente" che stiamo cercando una dimostrazione... :)
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: teoria binomiale

Messaggio da Gerald Lambeau »

Provo io: consideriamo un primo $p$ che divide $k!$, come sappiamo $\displaystyle v_p(k!)=\sum_{i=1}^{\infty} \left\lfloor\frac{k}{p^i}\right\rfloor$.
Proviamo a calcolare $v_p$ del prodotto generico di $k$ interi consecutivi.
I multipli di $p$ sono almeno $\displaystyle \left\lfloor\frac{k}{p}\right\rfloor$, e dobbiamo contarli ciascuno una volta sola ad aumentare l'esponente.
I multipli di $p^2$ sono almeno $\displaystyle \left\lfloor\frac{k}{p^2}\right\rfloor$, e dobbiamo contarli nuovamente una volta sola perché sono già stati contanti una volta nel conto precedente.
Lo stesso ragionamento si ripete per i multipli di $p^3, p^4, \dots$.
In generale, se $P=a(a+1)\cdot\dots\cdot(a+k-1)$ allora $\displaystyle v_p(P) \ge \sum_{i=1}^{\infty} \left\lfloor\frac{k}{p^i}\right\rfloor=v_p(k!)$, da cui $k! \mid P$, come voluto.
"If only I could be so grossly incandescent!"
Fbuonarroti
Messaggi: 30
Iscritto il: 01 gen 2016, 15:05

Re: teoria binomiale

Messaggio da Fbuonarroti »

Proviamo a dimostrarlo!
Prendiamo $ k $ interi consecutivi, allora sicuramente saranno congrui a $ 0,1..., k-1 ( k ) $ in qualche ordine, visto che è presente un intero congruo a $ 0 ( k ) $ il prodotto di questi $ k $ interi è divisibile per $ k $.
Ora chiediamoci se lo stesso prodotto sia divisibile per $ k-1 $ , ci basterebbero $ k-1 $ interi perché fosse vero, ma ne abbiamo $ k $ quindi vale anche per il caso $ k-1 $.
Con lo stesso ragionamento $ k $ elementi sono divisibili per $ k $ e per tutti i numeri minori di $ k $ e quindi per $ k! $
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: teoria binomiale

Messaggio da Gerald Lambeau »

Fbuonarroti, la tua non torna (lo so perché feci anch'io lo stesso errore in un altro esercizio): se dimostri che un numero è divisibile per un insieme di numeri, al massimo puoi dire che è divisibile per il loro minimo comune multiplo, ma non per il loro prodotto.
"If only I could be so grossly incandescent!"
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: teoria binomiale

Messaggio da jordan »

Probabilmente a qualcuno puo' interessare questo
The only goal of science is the honor of the human spirit.
Rispondi