Coefficiente binomiale

[axpgn]

Ho un paio di esercizietti di cui ho trovato la soluzione, ve li propongo ...

1) Dimostrare che $((2n),(n))$ è un numero pari

2) Dimostrare che $n+1$ è un fattore di $((2n),(n))$


Cordialmente, Alex

[sandroroma]

Per l'es.1 mi è venuta in mente una dimostrazione di tipo combinatorio ma sinceramente non so
valutare quanto sia valida...Le combinazioni richieste sono tutte quelle che si ottengono scegliendo
n elementi distinti dai 2n dati. Ora accade che ad ogni gruppo di n elementi scelti ne corrisponde
un altro pure di n elementi che sono quelli rimasti dei 2n dati. Pertanto per ogni scelta si ottiene
una coppia di possibili combinazioni. E questo permette di concludere che le combinazioni totali
sono in numero pari.

[axpgn]

Please, metti sotto spoiler ...

[giammaria2]

Do un'altra dimostrazione del punto 1.

Pensando al triangolo di Tartaglia, possiamo scrivere
$((2n),(n))=((2n-1),(n-1))+((2n-1),(n))$
I due addendi sono uguali fra loro, quindi il primo membro è il loro doppio e perciò pari.

[axpgn]

@giammaria
Questa è la seconda soluzione che avevo trovato per il primo, la prima è un pelino più complicata ...

[Erasmus_First]

"giammaria":[...] dimostrazione del punto 1.

Pensando al triangolo di Tartaglia, possiamo scrivere
$((2n),(n))=((2n-1),(n-1))+((2n-1),(n))$
I due addendi sono uguali fra loro, quindi il primo membro è il loro doppio e perciò pari.

Bellissima!
Io avevo pensato alla dimostrazione per induzione (pure molto facile ... ma meno sbrigativa e meno elegante di quella di giammaria). La scrivo di seguito.
Per comodità di scrittura indico con $C(n, k)$ il coefficiente binomiale "$n$ sopra $k$".
Pensandoci meglio ... la dimostrazione che segue non è nemmeno "per induzione", nel senso che non è necessario che $C(2n, n)$ sia pari per dimostrare che è senz'altro pari $C[2(n+1), (n+1)]$.

Si sa che in generale $C(2n,n)$ è intero per ogni $n$ naturale e che vale $C(2n,n) = ((2n)!)/(n!)^2$.
Si verifica immediatamente che $C(2n, n)$ è pari per $n = 1$ e per $n = 2$: $C(2, 1) = 2$; $C(4, 2) = 6$.
Dimostro che $C[2(n+1), (n+1)]$ è pari per ogni $n$ intero maggiore di 1 [cioè per $(n+1) ≥ 3$].
Risulta infatti:
$C[2(n+1), (n+1)] = C(2n, n)· (2(n+1)·(2n+1))/(n+1)^2 = 2(C(2n, n)·(2n+1))/(n+1)$.
Siccome $C[2(n+1), (n+1)]$ è intero e $(2n+1)$ non è divisibile per $(n+1)$, $C(2n, n)$ deve essere divisibile per $(n+1)$ [V. nota (*)]; e quindi $C[2(n+1), (n+1)]$ è il doppio di un numero intero.
[size=90]
(*) [Nota] E' dunque dimostrato anche il punto 2).[/size]

______

[axpgn]

Mi pare ci sia un problema nel primo passaggio ... en passant, hai dimostrato anche il secondo punto ...

[Erasmus_First]

"axpgn":Mi pare ci sia un problema nel primo passaggio ... en passant, hai dimostrato anche il secondo punto ...

Vero. Ma ancor prima di accorgermi di quest'ultimo tuo intervento ho modificato (e tenuto conto del fatto che en passant si dimostra anche il punto 2).
[Purtroppo, opero – ormai! – lentissimamente.
Ciao ciao.
_______

[orsoulx]

"axpgn": ... en passant, hai dimostrato anche il secondo punto ...

Direi che la relazione utilizzata da Erasmus non dimostri né il punto (1), né il punto (2). Dimostra, invece, che se è vera (2) allora è vera (1) e, più interessante, un'altra proprietà:
3) $ 2n-1 $ divide $ ((2n),(n)) $.
Nasce allora un problema, a mio avviso, più intrigante:
$ ((2n), (n)) $ è divisibile per $ 2 $, per $ n+1 $ e per $ 2n-1 $. Per quali valori di $ n $ è divisibile per il loro prodotto $ 2(n+1)(2n-1) $?

Una dimostrazione di (2) potrebbe essere la seguente:

Dalla relazione iterativa, vera per ogni $ 0 $ ((2n),(n))=((2n),(n-1)) (n+1)/n $ che, essendo $ n+1 $ ed $ n $ primi fra loro, dimostra la (2)

Ciao

[axpgn]

L'esposizione di Erasmus era poco chiara, come ho detto, poi non ho più approfondito ...

Riporto le mie ...

1) Nella prima soluzione che ho trovato utilizzo, per comodità, il triangolo di Tartaglia; la riga $2n$ del triangolo ha un numero di elementi dispari e $((2n),(n))$ è quello spaiato centrale mentre tutti gli altri sono accoppiati, cioè il primo è uguale all'ultimo, il secondo è uguale al penultimo, ecc., quindi la loro somma è un numero pari; dato che la somma di tutti gli elementi di una riga ennesima è $2^n$ ecco che $((2n),(n))$ essendo la differenza di due numeri pari, è pari anch'esso.
La seconda che ho trovato era quella di giammaria.

2) Ho utilizzato questa identità $((n),(r))=n/r((n-1),(r-1))=$ che applicata al nostro caso da $((2n+1),(n+1))=(2n+1)/(n+1)((2n),(n))$; ora siccome i quattro termini sono tutti interi e dato che $n+1$ è coprimo di $2n+1$ allora necessariamente $n+1|((2n),(n))$

Alla tua ci penserò ...

Cordialmente, Alex