Exercicis de principis de demostració

La fórmula.

$1 + 2 + \cdots + 4 = \frac{4\cdot5}{2} = 10$

Per què és certa (esquema de la inducció). El cas base $n=1$ dona $1\cdot 2/2 = 1$, correcte. I si val per a un $n$ concret, sumant $n+1$ al total surt

$\frac{n(n+1)}{2} + (n+1) = (n+1)\left(\frac{n}{2}+1\right) = \frac{(n+1)(n+2)}{2},$

que és exactament la fórmula amb $n+1$. Com que el cas base val i el pas es pot repetir, val per a tot $n$.

On s'ha fet servir la hipòtesi: a la primera igualtat, i només allà. Si en una prova per inducció no saps assenyalar el punt exacte on l'has aplicada, probablement no és inductiva.

El valor.

$2^{4} = 16$

La desigualtat. Es compleix que $16 > 4$, com afirma l'enunciat.

L'esquema de la prova. Cas base $n=1$: $2 > 1$. Pas inductiu: si $2^{n} > n$, aleshores

$2^{n+1} = 2\cdot 2^{n} > 2n \geq n+1,$

on l'última desigualtat val perquè $n\geq 1$. Observa que el pas fa servir dues coses: la hipòtesi d'inducció i una propietat elemental dels enters positius.

El creixement. La diferència entre les dues quantitats es dispara: a $n=10$ ja és de $1014$. Aquesta és la raó per la qual un algorisme exponencial és inviable i un de lineal no.

La tasca: Refutar que tot nombre senar és primer.

El mètode adequat és Contraexemple, perquè per refutar un universal n'hi ha prou amb un cas: $9$ és senar i no és primer.

Com es decideix. Mira primer si el que et demanen és demostrar o refutar: per refutar un universal només cal un contraexemple que compleixi les hipòtesis i incompleixi la conclusió. Si has de demostrar, mira si l'enunciat depèn d'un enter $n$ i si el cas $n+1$ es pot relacionar amb l'anterior: llavors és inducció. Si no, prova directa, i si la hipòtesi no es deixa fer servir, contraposició o absurd.

Un avís sobre l'absurd: si la teva prova per contradicció no fa servir mai la hipòtesi negada, en realitat tenies una prova directa i queda més clara escrita així.

La fórmula.

$1 + 2 + \cdots + 5 = \frac{5\cdot6}{2} = 15$

Per què és certa (esquema de la inducció). El cas base $n=1$ dona $1\cdot 2/2 = 1$, correcte. I si val per a un $n$ concret, sumant $n+1$ al total surt

$\frac{n(n+1)}{2} + (n+1) = (n+1)\left(\frac{n}{2}+1\right) = \frac{(n+1)(n+2)}{2},$

que és exactament la fórmula amb $n+1$. Com que el cas base val i el pas es pot repetir, val per a tot $n$.

On s'ha fet servir la hipòtesi: a la primera igualtat, i només allà. Si en una prova per inducció no saps assenyalar el punt exacte on l'has aplicada, probablement no és inductiva.

El valor.

$2^{5} = 32$

La desigualtat. Es compleix que $32 > 5$, com afirma l'enunciat.

L'esquema de la prova. Cas base $n=1$: $2 > 1$. Pas inductiu: si $2^{n} > n$, aleshores

$2^{n+1} = 2\cdot 2^{n} > 2n \geq n+1,$

on l'última desigualtat val perquè $n\geq 1$. Observa que el pas fa servir dues coses: la hipòtesi d'inducció i una propietat elemental dels enters positius.

El creixement. La diferència entre les dues quantitats es dispara: a $n=10$ ja és de $1014$. Aquesta és la raó per la qual un algorisme exponencial és inviable i un de lineal no.

La tasca: Demostrar que hi ha infinits primers.

El mètode adequat és Reducció a l'absurd, perquè l'argument clàssic suposa que n'hi ha un nombre finit i construeix un primer nou.

Com es decideix. Mira primer si el que et demanen és demostrar o refutar: per refutar un universal només cal un contraexemple que compleixi les hipòtesis i incompleixi la conclusió. Si has de demostrar, mira si l'enunciat depèn d'un enter $n$ i si el cas $n+1$ es pot relacionar amb l'anterior: llavors és inducció. Si no, prova directa, i si la hipòtesi no es deixa fer servir, contraposició o absurd.

Un avís sobre l'absurd: si la teva prova per contradicció no fa servir mai la hipòtesi negada, en realitat tenies una prova directa i queda més clara escrita així.

La fórmula.

$1 + 2 + \cdots + 6 = \frac{6\cdot7}{2} = 21$

Per què és certa (esquema de la inducció). El cas base $n=1$ dona $1\cdot 2/2 = 1$, correcte. I si val per a un $n$ concret, sumant $n+1$ al total surt

$\frac{n(n+1)}{2} + (n+1) = (n+1)\left(\frac{n}{2}+1\right) = \frac{(n+1)(n+2)}{2},$

que és exactament la fórmula amb $n+1$. Com que el cas base val i el pas es pot repetir, val per a tot $n$.

On s'ha fet servir la hipòtesi: a la primera igualtat, i només allà. Si en una prova per inducció no saps assenyalar el punt exacte on l'has aplicada, probablement no és inductiva.

El valor.

$2^{6} = 64$

La desigualtat. Es compleix que $64 > 6$, com afirma l'enunciat.

L'esquema de la prova. Cas base $n=1$: $2 > 1$. Pas inductiu: si $2^{n} > n$, aleshores

$2^{n+1} = 2\cdot 2^{n} > 2n \geq n+1,$

on l'última desigualtat val perquè $n\geq 1$. Observa que el pas fa servir dues coses: la hipòtesi d'inducció i una propietat elemental dels enters positius.

El creixement. La diferència entre les dues quantitats es dispara: a $n=10$ ja és de $1014$. Aquesta és la raó per la qual un algorisme exponencial és inviable i un de lineal no.

La tasca: Demostrar que $2^{n} > n$ per a tot $n \geq 1$.

El mètode adequat és Inducció, perquè cada cas es dedueix de l'anterior duplicant.

Com es decideix. Mira primer si el que et demanen és demostrar o refutar: per refutar un universal només cal un contraexemple que compleixi les hipòtesis i incompleixi la conclusió. Si has de demostrar, mira si l'enunciat depèn d'un enter $n$ i si el cas $n+1$ es pot relacionar amb l'anterior: llavors és inducció. Si no, prova directa, i si la hipòtesi no es deixa fer servir, contraposició o absurd.

Un avís sobre l'absurd: si la teva prova per contradicció no fa servir mai la hipòtesi negada, en realitat tenies una prova directa i queda més clara escrita així.

La fórmula.

$1 + 2 + \cdots + 7 = \frac{7\cdot8}{2} = 28$

Per què és certa (esquema de la inducció). El cas base $n=1$ dona $1\cdot 2/2 = 1$, correcte. I si val per a un $n$ concret, sumant $n+1$ al total surt

$\frac{n(n+1)}{2} + (n+1) = (n+1)\left(\frac{n}{2}+1\right) = \frac{(n+1)(n+2)}{2},$

que és exactament la fórmula amb $n+1$. Com que el cas base val i el pas es pot repetir, val per a tot $n$.

On s'ha fet servir la hipòtesi: a la primera igualtat, i només allà. Si en una prova per inducció no saps assenyalar el punt exacte on l'has aplicada, probablement no és inductiva.