Dubbi sul principio di induzione

[oleg.fresi]

Ho questa proposizione da dimostrare per induzione: $P(n)= n^2>2n+1$ con $n>2$.
Scrivo la $P(n+1)=(n+1)^2>2(n+1)+1$. Ora sfrutto l'ipotesi $n^2+2n+1>2n+1 + (2n+1)$. Adesso manipolo l'espressione cercando di ottenere la tesi: $n^2+2n+1>2(n+1)+2n$. Da qui non saprei come procedere per ottenere l'$1$ che compare nella tesi. Potreste aiutarmi per favore?

[axpgn]

$2n+1+(2n+1)>2n+1+2$ per $n>2$

[oleg.fresi]

Ma il termine $2n+1+2$ come lo hai ricavato?

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Devi dimostrare che $(n+1)^2> 2(n+1)+1$ quindi se apri il prodotto del termine a destra hai $2n+2+1$.

[oleg.fresi]

Bene, adesso mi è chiaro. Ma se $(n+1)^2>2n+2+1$ e $(n+1)^2>2n+1+(2n+1)$ allora perchè
$2n+1+(2n+1)>2n+1+2$ ?

[axpgn]

$ 2n+1+(2n+1)>2n+1+2\ ->\ (2n+1)>2\ -> \ 2n>1\ ->\ n>1/2$

E questo è vero per ogni $n$ naturale e quindi anche per $n>2$


Ma poi cosa sarebbe quel "se … allora … " ? È una cosa incomprensibile … hai mischiato ipotesi e tesi e passaggi intermedi …

E per fortuna che ti è chiaro …

[oleg.fresi]

Si, è vero che mi sono confuso mischinado un po tutto. Ma una volta giunti a $n>1/2$, la dimostrazione non è conclusa. Qual'è il passaggio chiave per risolverla?

[axpgn]

Veramente?

Ipotesi passo induttivo: $n^2>2n+1$

Aggiungo $2n+1$ ad entrambi i membri per ottenere $n^2+2n+1>2n+1+2n+1$ ovvero $(n+1)^2>2n+1+2n+1$

Adesso noto che $2n+1+2n+1>2n+1+2$ (la dimostrazione l'ho postata prima)

Ma allora le due disequazioni (vere) precedenti mi dicono che $(n+1)^2>2n+1+2n+1>2n+1+2$ ovvero che l'espressione di sinistra è maggiore di quella di destra cioè $(n+1)^2>2n+1+2$

Ma questa è la tesi! Quindi l'ho dimostrata.

[oleg.fresi]

Perfetto axpgn, adesso mi è chiara. Grazie tante! Volevo però chiarire un altro dubbio: quando si applica il principio di induzione per verificare una proposizione, si verifica inizialmente per dei casi base. Quindi per esempio data una $P(n)$ dimostro che è vera per $n=0$, $n=1$ poi però per $n=2$ non è più vera mentre per $n=3$ è vera e lo è anche per $n=4$ e $n=5$. Da qui in poi spero che sia sempre vera e quindi dimostro $P(n+1)$. La mia domanda è: chi mi garantisce che, per esempio per $n=273$ $P(n)$ è vera? Infatti, se io non avessi provato a sostituire $1,2,3,4,5$ al posto di $n$, ma avessi ciecamente posto $P(n+1)$, non mi sarei mai accorto che per $n=2$ questa è falsa.

[axpgn]

Per $n=0$ e $n=1$ quella proposizione è falsa.

[@melia]

Quando per n=0 e n=1 una certa proposizione è vera, poi non lo è per n=2 e torna ad esserlo per n>2 quando cerchi la veridicità di P(n+1) in qualche modo ti uscirà la condizione $n!=2$

[oleg.fresi]

Adesso è chiaro. Grazie tante!

[oleg.fresi]

Visto che siamo in tema, vorrei porre un'altra domanda. Si può dimostrare per induzione che
$\sum_{i=1}^N k^2=(n(n+1)(2n+1))/6$. Qui l'induzione mi permette di dimostare se è vero. Ma se io avessi semplicemente $\sum_{i=1}^N k^2$ come farei a dedurre che è uguale a $(n(n+1)(2n+1))/6$ ?

[axpgn]

Il principio di induzione serve per dimostrare proposizioni non per trovarle ...

[oleg.fresi]

Certamente, ma se io avessi voluto trovare quella, senza conoscerla a priori, come avrei dovuto operare?

[axpgn]

Non esiste metodo per scoprire ogni cosa, non so quante volte te l'ho detto ...

Occorre intuito, capacità, conoscenza, lavoro, fatica, costanza, impegno, talento, sperimentazione, ecc.

[oleg.fresi]

Ok, ho capito. Chissa chi l'avra scoperta.

[gugo82]

"ZfreS":Visto che siamo in tema, vorrei porre un'altra domanda. Si può dimostrare per induzione che
$\sum_{i=1}^N k^2=(n(n+1)(2n+1))/6$. Qui l'induzione mi permette di dimostare se è vero. Ma se io avessi semplicemente $\sum_{i=1}^N k^2$ come farei a dedurre che è uguale a $(n(n+1)(2n+1))/6$ ?

Innanzitutto, la formula scritta non significa nulla (perché quella corretta è $\sum_{i=1}^N i^2 = (N(N+1)(2N+1))/6$.

Fatte le correzioni di rito, chiedi cosa fare se non avessi il secondo membro: beh, ti metteresti a fare ricerca...

Attenzione: post lungo (ma bellino, IMHO... Potrebbe essere riciclato per fare un po' di laboratorio di Matematica in un biennio scientifico).

Comincia a tabulare dei dati:
\begin{matrix}
N & \mapsto & \sum_{i=1}^N i^2 \\
1 & \mapsto & 1 \\
2 & \mapsto & 5 \\
3 & \mapsto & 14 \\
4 & \mapsto & 30 \\
5 & \mapsto & 55 \\
6 & \mapsto & 91 \\
7 & \mapsto & 140 \\
8 & \mapsto & 204 \\
9 & \mapsto & 285 \\
10 & \mapsto & 385 \\
11 & \mapsto & 506 \\
12 & \mapsto & 650 \\
13 & \mapsto & 819 \\
\end{matrix}
ed osserva la seconda colonna: non si vede nessuna regolarità (a parte una crescita non troppo veloce).
A questo punto, cominci a smanettare... Ad esempio, prova a scomporre i numeri della seconda colonna in fattori primi:
\begin{matrix}
N & \mapsto & \sum_{i=1}^N i^2 & \text{in fattori primi}\\
1 & \mapsto & 1 & 1\\
2 & \mapsto & 5 & 5 \\
3 & \mapsto & 14 & 2\cdot 7 \\
4 & \mapsto & 30 & 2\cdot 3 \cdot 5 \\
5 & \mapsto & 55 & 5\cdot 11 \\
6 & \mapsto & 91 & 7\cdot 13 \\
7 & \mapsto & 140 & 2^2 \cdot 5 \cdot 7 \\
8 & \mapsto & 204 & 2^2 \cdot 3 \cdot 17 \\
9 & \mapsto & 285 & 3\cdot 5\cdot 19 \\
10 & \mapsto & 385 & 5\cdot 7 \cdot 11 \\
11 & \mapsto & 506 & 2\cdot 11 \cdot 23 \\
12 & \mapsto & 650 & 2\cdot 5^2 \cdot 13 \\
13 &\mapsto & 819 & 3^2 \cdot 7 \cdot 13
\end{matrix}
nemmeno qui c'è regolarità... Ma qualcosa che si ripete c'è: infatti, osserva i numeri in rosso:
\begin{matrix}
N & \mapsto & \sum_{i=1}^N i^2 & \text{in fattori primi}\\
1 & \mapsto & 1 & 1\\
2 & \mapsto & 5 & {\color{red} 5} \\
3 & \mapsto & 14 & 2\cdot {\color{red} 7} \\
4 & \mapsto & 30 & 2\cdot 3 \cdot 5 \\
5 & \mapsto & 55 & 5\cdot {\color{red} 11} \\
6 & \mapsto & 91 & 7\cdot {\color{red} 13} \\
7 & \mapsto & 140 & 2^2 \cdot 5 \cdot 7 \\
8 & \mapsto & 204 & 2^2 \cdot 3 \cdot {\color{red} 17} \\
9 & \mapsto & 285 & 3\cdot 5\cdot {\color{red} 19} \\
10 & \mapsto & 385 & 5\cdot 7 \cdot 11 \\
11 & \mapsto & 506 & 2\cdot 11 \cdot {\color{red} 23} \\
12 & \mapsto & 650 & 2\cdot \underbrace{\color{red} 25}_{=5^2} \cdot 13 \\
13 &\mapsto & 819 & 3^2 \cdot 7 \cdot 13
\end{matrix}
Ah, caspita! Quelli in rosso sono numeri dispari!!!
E mica numeri dispari qualsiasi: infatti $5=2*2+1$, $7=2*3+1$, $11=2*5+1$, etc... Insomma, nella riga di $N$ in cui compare qualche numero dispari rosso, il numero dispari rosso che compare è del tipo $2*N+1$.

Ma com'è possibile che questa regolarità non sia così tanto regolare? Insomma, perché alcune righe vengono saltate? C'è qualcosa che si può fare per rimediare?
Innanzitutto, dopo ogni coppia di righe consecutive in cui c'è un numero rosso segue una riga in cui non c'è nessun numero rosso... A ben vedere tra i numeri dispari rossi mancano ${\color{red} 3}$ ${\color{red} 9}$, ${\color{red} 15}$, ${\color{red} 21}$, ${\color{red} 27}$, cioè mancano i multipli dispari di $3$!
Ah, ma questa è comunque una regolarità... E allora, cerchiamo di sfruttarla.

Moltiplichiamo tutta la seconda colonna per $3$ e vediamo cosa accade nella terza, mettendo in ultimo i numeri rosso:
\begin{matrix}
N & \mapsto & 3\cdot \sum_{i=1}^N i^2 & \text{in fattori}\\
1 & \mapsto & 3 & 1 \cdot \color{red} 3\\
2 & \mapsto & 15 & 3 \cdot {\color{red} 5} \\
3 & \mapsto & 42 & 2 \cdot 3 \cdot {\color{red} 7} \\
4 & \mapsto & 90 & 2 \cdot 5 \cdot \underbrace{\color{red} 9}_{=3^2} \\
5 & \mapsto & 165 & 3 \cdot 5 \cdot {\color{red} 11} \\
6 & \mapsto & 273 & 3 \cdot 7 \cdot {\color{red} 13} \\
7 & \mapsto & 420 & 2^2 \cdot 7 \cdot \underbrace{\color{red} 15}_{=3\cdot 5} \\
8 & \mapsto & 612 & 2^2 \cdot 3^2 \cdot {\color{red} 17} \\
9 & \mapsto & 855 & 3^2 \cdot 5\cdot {\color{red} 19} \\
10 & \mapsto & 1155 & 5 \cdot 11 \cdot \underbrace{\color{red} 21}_{=3\cdot 7} \\
11 & \mapsto & 1518 & 2 \cdot 3 \cdot 11 \cdot {\color{red} 23} \\
12 & \mapsto & 1950 & 2 \cdot 3\cdot 13 \cdot \underbrace{\color{red} 25}_{=5^2} \\
13 &\mapsto & 2457 & 7 \cdot 13 \cdot \underbrace{\color{red} 27}_{=3^3}
\end{matrix}
Da questa tabella intuiamo che, se proprio c'è una regola, potrebbe essere una roba del tipo:
\[
3\cdot \sum_{i=1}^N i^2 = \text{robaccia} \cdot (2N+1)\; ,
\]
e però ancora ci manca da determinare cosa può essere la $"robaccia"$.

Torniamo ad osservare attentamente la tabella con i numeri in rosso, per determinare la presenza di altre regolarità: abbiamo:
\begin{matrix}
N & \mapsto & 3\cdot \sum_{i=1}^N i^2 & \text{in fattori}\\
1 & \mapsto & 3 & 1 \cdot \color{red} 3\\
2 & \mapsto & 15 & 3 \cdot {\color{red} 5} \\
3 & \mapsto & 42 & 2 \cdot 3 \cdot {\color{red} 7} \\
4 & \mapsto & 90 & 2 \cdot 5 \cdot {\color{red} 9} \\
5 & \mapsto & 165 & 3 \cdot 5 \cdot {\color{red} 11} \\
6 & \mapsto & 273 & 3 \cdot 7 \cdot {\color{red} 13} \\
7 & \mapsto & 420 & 2^2 \cdot 7 \cdot {\color{red} 15} \\
8 & \mapsto & 612 & 2^2 \cdot 3^2 \cdot {\color{red} 17} \\
9 & \mapsto & 855 & 3^2 \cdot 5\cdot {\color{red} 19} \\
10 & \mapsto & 1155 & 5 \cdot 11 \cdot {\color{red} 21} \\
11 & \mapsto & 1518 & 2 \cdot 3 \cdot 11 \cdot {\color{red} 23} \\
12 & \mapsto & 1950 & 2 \cdot 3\cdot 13 \cdot {\color{red} 25} \\
13 &\mapsto & 2457 & 7 \cdot 13 \cdot {\color{red} 27}
\end{matrix}
e già qualcosa di evidente c'è... Ma se esplicitiamo le potenze e coloriamo di arancione alcuni numeri la si vede meglio:
\begin{matrix}
N & \mapsto & 3\cdot \sum_{i=1}^N i^2 & \text{in fattori}\\
1 & \mapsto & 3 & {\color{orange} 1} \cdot \color{red} 3\\
2 & \mapsto & 15 & 3 \cdot {\color{red} 5} \\
3 & \mapsto & 42 & 2 \cdot {\color{orange} 3} \cdot {\color{red} 7} \\
4 & \mapsto & 90 & 2 \cdot 5 \cdot {\color{red} 9} \\
5 & \mapsto & 165 & 3 \cdot {\color{orange} 5} \cdot {\color{red} 11} \\
6 & \mapsto & 273 & 3 \cdot 7 \cdot {\color{red} 13} \\
7 & \mapsto & 420 & 4 \cdot {\color{orange} 7} \cdot {\color{red} 15} \\
8 & \mapsto & 612 & 4 \cdot 9 \cdot {\color{red} 17} \\
9 & \mapsto & 855 & 5 \cdot {\color{orange} 9} \cdot {\color{red} 19} \\
10 & \mapsto & 1155 & 5 \cdot 11 \cdot {\color{red} 21} \\
11 & \mapsto & 1518 & 2 \cdot 3 \cdot {\color{orange} 11} \cdot {\color{red} 23} \\
12 & \mapsto & 1950 & 2 \cdot 3\cdot 13 \cdot {\color{red} 25} \\
13 &\mapsto & 2457 & 7 \cdot {\color{orange} 13} \cdot {\color{red} 27}
\end{matrix}
Ah, caspita! Quelli in arancione sono numeri della prima colonna!!!
Insomma, nella riga di $N$ in cui compare qualche numero arancione, il numero arancione coincide con $N$.

Ma com'è possibile che questa regolarità non sia così tanto regolare? Insomma, perché alcune righe vengono saltate? C'è qualcosa che si può fare per rimediare?
A guardar bene, le righe coi numeri arancioni si alternano a righe senza numeri di tale colore. E però, nelle righe che non contengono numeri arancioni, sono presenti numeri che, moltiplicati per $2$, forniscono quelli nella prima colonna.
Allora, come fatto sopra, moltiplichiamo per $2$ la seconda e la terza colonna, ordiniamo i fattori nella terza ed otteniamo questa nuova tabella:
\begin{matrix}
N & \mapsto & 6\cdot \sum_{i=1}^N i^2 & \text{in fattori}\\
1 & \mapsto & 3 & {\color{orange} 1} \cdot 2\cdot \color{red} 3\\
2 & \mapsto & 15 & {\color{orange} 2}\cdot 3 \cdot {\color{red} 5} \\
3 & \mapsto & 42 & {\color{orange} 3} \cdot 4 \cdot {\color{red} 7} \\
4 & \mapsto & 90 & {\color{orange} 4} \cdot 5 \cdot {\color{red} 9} \\
5 & \mapsto & 165 & {\color{orange} 5} \cdot 6 \cdot {\color{red} 11} \\
6 & \mapsto & 273 & {\color{orange} 6} \cdot 7 \cdot {\color{red} 13} \\
7 & \mapsto & 420 & {\color{orange} 7} \cdot 8 \cdot {\color{red} 15} \\
8 & \mapsto & 612 & {\color{orange} 8} \cdot 9 \cdot {\color{red} 17} \\
9 & \mapsto & 855 & {\color{orange} 9} \cdot 10 \cdot {\color{red} 19} \\
10 & \mapsto & 1155 & {\color{orange} 10} \cdot 11 \cdot {\color{red} 21} \\
11 & \mapsto & 1518 & {\color{orange} 11} \cdot 12 \cdot {\color{red} 23} \\
12 & \mapsto & 1950 & {\color{orange} 12} \cdot 13 \cdot {\color{red} 25} \\
13 &\mapsto & 2457 & {\color{orange} 13} \cdot 14 \cdot {\color{red} 27}
\end{matrix}
Da questa tabella intuiamo che, se proprio c'è una regola, potrebbe essere una roba del tipo:
\[
6\cdot \sum_{i=1}^N i^2 = N \cdot \text{robaccia} \cdot (2N+1)\; ,
\]
e però, cavolo!, è facile intuire che la $"robaccia"$ è $N+1$: infatti, i secondi fattori (quelli non evidenziati da nessun colore particolare) sono i successivi dei numeri arancioni.
Dunque, se proprio una regola c'è, essa deve essere del tipo:
\[
6\cdot \sum_{i=1}^N i^2 = N \cdot (N+1) \cdot (2N+1)\; ,
\]
da cui la congettura:
\[
\sum_{i=1}^N i^2 = \frac{N \cdot (N+1) \cdot (2N+1)}{6}
\]
valida per ogni $N in NN$.

Poi, che questa congettura, la quale ben si adatta ai primi tredici casi, valga del tutto in generale si dimostra usando, ad esempio, il PIM.

[oleg.fresi]

Wow gugo, davvero bella la dimostrazione! Proverò a sperimentare con qualche altra formula seguendo un ragionamento simile. Grazie!

[gugo82]

"ZfreS":Wow gugo, davvero bella la dimostrazione!

Non è una dimostrazione!

Casomai, ti ho mostrato come, senza sapere nulla, si può ricavare dai dati una congettura.


P.S.: Sai cos'è una congettura?
E cos'è un teorema?
Ed una dimostrazione?

[oleg.fresi]

Si, certamente, una dimostrazione in senso lato.