Come dimostro per induzione?

Qui si parla di libri, film, fumetti, documentari, software di argomento matematico o scientifico.
Rispondi
Avatar utente
lama luka
Messaggi: 326
Iscritto il: 05 feb 2009, 22:21
Località: cittadino del mondo

Come dimostro per induzione?

Messaggio da lama luka »

Salve, l'altro giorno stavo cercando di inventare un problema da proporre alle gare, ritenendo interessante il procedimento che stavo adottando sono andato avanti per poi arrivare ad una conlucione che mi ha distrutto il problema rendendolo "banale" per chi ha fatto almeno una gara di matematica nella vita.. In soldoni, ho ricavato che:
$ n! = \sum_{k=0}^n \binom{n}{k}\cdot !(n-k) $, adesso, pensandoci, la dimostrazione <a parole> è abbastanza immediata e quindi mi sono sforzato di voler dimostrare la formula per induzione, ma son rimasto a fissarla amorevolemente per un'oretta buona.. Mi chiedevo dunque se e in che modo si potesse dimostrare per induzione (nb. ero in spiaggia sotto il sole quindi è possibilissimo che non mi sia accorto di un modo 'semplice', in tal caso non fustigatemi, please :) )..

Comunque la 'spiegazone/dimostrazione' che ho dato, per chi fosse interessato, è questa:
Testo nascosto:
Considero un insieme $ A $ di $ n $ elementi, e una funzione biettiva $ f:A\rightarrow A $ (in soldoni, considero una permutazione di A). Adesso, procedo per gradi: scelgo $ 0 $ elementi fissi ($ f(x)=x $), lo posso fare in un solo modo, quindi $ \binom{n}{0} $, i restanti n elementi li posso permutare in $ !n $ modi, in modo che nessuno di questi sia fisso. Adesso considero un elemento $ x_0 $ fisso, tale $ x_0 $ lo posso scegliere in $ \binom{n}{1} $ modi e i restanti n-1 elementi li permuto (senza punti fissi) in $ !(n-1) $ modi. Vado avanti...... Considero $ x_0,\cdots , x_{n-3} $ elementi fissi, li posso scegliere in $ \binom{n}{n-2} $ modi e i restanti li permuto in $ !2 $ modi (cioè $ n-(n-3) $), adesso il caso in cui ne fissi n-1 è equivalente al caso in cui li fisso tutti, per ovvi motivi e dunque ottengo $ \binom{n}{n}\cdot !(n-n)=1 $; a questo punto il numero delle possibili permutazione è dato dalla somma di tutti i casi considerati, quindi $ !(n)\binom{n}{0} + !(n-1)\binom{n}{1}+\cdots +!2 \binom{n}{n-2}+!1\binom{n}{n-1}+!0\binom{n}{n} $ e dunque $ \sum_{k=0}^n \binom{n}{k}\cdots !(n-k) =n! $
Non siamo mica qui a raddrizzare banane col culo !

è Ragionevole!

44 gatti [tex]\equiv 2 \pmod{6}[/tex]

E questo come lo risolvo?-L.Lamanna,G.Grilletti (2009)
Tre anni di quaestio copernicana - C.Càssola, F.M.Antoniali, L.Lamanna (2012)
Cinque anni di Copernicus Math Race - L.Lamanna (2016)

[tex]!n=n! \sum_{k=0}^n \frac{(-1)^k}{k!}[/tex]
Avatar utente
lama luka
Messaggi: 326
Iscritto il: 05 feb 2009, 22:21
Località: cittadino del mondo

Re: Come dimostro per induzione?

Messaggio da lama luka »

A si, per chi non lo sapesse..Con $ !n $ indico le permutazioni senza punti fissi ($ f(x)\neq x \forall x $) di n elementi e $ !n= n!\sum_{k=0}^n \frac{(-1)^k}{k!} $.
Non siamo mica qui a raddrizzare banane col culo !

è Ragionevole!

44 gatti [tex]\equiv 2 \pmod{6}[/tex]

E questo come lo risolvo?-L.Lamanna,G.Grilletti (2009)
Tre anni di quaestio copernicana - C.Càssola, F.M.Antoniali, L.Lamanna (2012)
Cinque anni di Copernicus Math Race - L.Lamanna (2016)

[tex]!n=n! \sum_{k=0}^n \frac{(-1)^k}{k!}[/tex]
Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Re: Come dimostro per induzione?

Messaggio da exodd »

Il metodo c'è, e non è neanche troppo brutto..
Lo scrivo nel prossimo post
* Si scrocchia le dita *
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"
Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Re: Come dimostro per induzione?

Messaggio da exodd »

Passo base: n=1

$1!=\binom{1}{0}\cdot!1+\binom{1}{1}\cdot!0=1$

Passo induttivo:
sappiamo che

$n! = \sum_{k=0}^n \binom{n}{k}\cdot !(n-k)$

vogliamo dimostrare che

$(n+1)! = \sum_{k=0}^{n+1} \binom{n+1}{k}\cdot !(n+1-k)$

Ovvero che

$(n+1) \sum_{k=0}^n \binom{n}{k}\cdot !(n-k)= \sum_{k=0}^{n+1} \binom{n+1}{k}\cdot !(n+1-k)$

O anche

$(n+1) \sum_{k=0}^n \binom{n}{k}\cdot !(n-k)=1+ \sum_{k=0}^{n} \binom{n+1}{k}\cdot !(n+1-k)$

$ \sum_{k=0}^n[(n+1) \binom{n}{k}\cdot !(n-k)-\binom{n+1}{k}\cdot !(n+1-k)]=1$

Esaminiamo ogni elemento della sommatoria

$(n+1) \binom{n}{k}\cdot !(n-k)-\binom{n+1}{k}\cdot !(n+1-k)=$

$(n+1)\frac{n!}{k!(n-k)!}(n-k)!\sum_{k=0}^{n-k} \frac{(-1)^k}{k!}-\frac{(n+1)!}{k!(n+1-k)!}(n+1-k)!\sum_{k=0}^{n+1-k} \frac{(-1)^k}{k!}=$

$\frac{(n+1)!}{k!}[\sum_{k=0}^{n-k} \frac{(-1)^k}{k!}-\sum_{k=0}^{n+1-k} \frac{(-1)^k}{k!}]=$

$\frac{(n+1)!}{k!(n+1-k)!}(-1)^{n+1-k}=(-1)^{n+1-k}\binom{n+1}{k}$

Risostituendo nella sommatoria iniziale

$\sum_{k=0}^n(-1)^{n+1-k}\binom{n+1}{k}=1$

Che è abbastanza nota
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"
Avatar utente
lama luka
Messaggi: 326
Iscritto il: 05 feb 2009, 22:21
Località: cittadino del mondo

Re: Come dimostro per induzione?

Messaggio da lama luka »

Grazie ventimila !! :)
Non siamo mica qui a raddrizzare banane col culo !

è Ragionevole!

44 gatti [tex]\equiv 2 \pmod{6}[/tex]

E questo come lo risolvo?-L.Lamanna,G.Grilletti (2009)
Tre anni di quaestio copernicana - C.Càssola, F.M.Antoniali, L.Lamanna (2012)
Cinque anni di Copernicus Math Race - L.Lamanna (2016)

[tex]!n=n! \sum_{k=0}^n \frac{(-1)^k}{k!}[/tex]
Rispondi