Esercizio di induzione sul Triangolo di Pascal
Salve a tutti,
sono un neofita del vostro forum, a mio parere uno dei pochi veramente utili e didattici.
Ma vengo al dunque. Ristrutturando a suon di esercizi le mie fondamenta matematiche, mi sono imbattuto in questo problema d'induzione che mi sta dando non poco filo da torcere:
Dimostrare che per ogni n:
$\sum_{k=0}^n ((n),(k))^2$=$((2n),(n))$
dove $((n),(k))$ sta per "n su k", numero di combinazioni di k elementi su n dati. In pratica equivale a dimostrare che, nel triangolo di Pascal (o Tartaglia che dir si voglia), la somma dei quadrati degli elementi dell'n-esima riga è uguale al coefficiente binomiale centrale della 2n-esima (spero di non essermi spiegato in modo fantozziano...). Però non riesco a svolgere il passo induttivo da n ad n+1, ed ho ormai esaurito le idee....se potete darmi un piccolo aiuto "combinatorio" ve ne sono gratissimo!
grazie mille a voi tutti!
Au revoir
sono un neofita del vostro forum, a mio parere uno dei pochi veramente utili e didattici.
Ma vengo al dunque. Ristrutturando a suon di esercizi le mie fondamenta matematiche, mi sono imbattuto in questo problema d'induzione che mi sta dando non poco filo da torcere:
Dimostrare che per ogni n:
$\sum_{k=0}^n ((n),(k))^2$=$((2n),(n))$
dove $((n),(k))$ sta per "n su k", numero di combinazioni di k elementi su n dati. In pratica equivale a dimostrare che, nel triangolo di Pascal (o Tartaglia che dir si voglia), la somma dei quadrati degli elementi dell'n-esima riga è uguale al coefficiente binomiale centrale della 2n-esima (spero di non essermi spiegato in modo fantozziano...). Però non riesco a svolgere il passo induttivo da n ad n+1, ed ho ormai esaurito le idee....se potete darmi un piccolo aiuto "combinatorio" ve ne sono gratissimo!
grazie mille a voi tutti!
Au revoir
Risposte
Passo iniziale:
$P(1)$: $sum_(k=0)^1 ((1),(k))=((1),(0))+((1),(1))=1+1=2=((2),(1))$
Passo induttivo:
$P(n) Rightarrow P(n+1)$: $sum_(k=0)^(n+1) ((n+1),(k))=2^(n+1)=2*2^n=2*sum_(k=0)^(n) ((n),(k))=2*((2n),(n))$
Da qui però (a meno di miei orrori) non mi pare ci sia uguaglianza... ovvero mi sa che non vale:
$2*((2n),(n))=((2n+2),(n+1))$
$P(1)$: $sum_(k=0)^1 ((1),(k))=((1),(0))+((1),(1))=1+1=2=((2),(1))$
Passo induttivo:
$P(n) Rightarrow P(n+1)$: $sum_(k=0)^(n+1) ((n+1),(k))=2^(n+1)=2*2^n=2*sum_(k=0)^(n) ((n),(k))=2*((2n),(n))$
Da qui però (a meno di miei orrori) non mi pare ci sia uguaglianza... ovvero mi sa che non vale:
$2*((2n),(n))=((2n+2),(n+1))$