Simulacre d'examen de principis de demostració

La tasca: Demostrar que la suma de dos parells és parella.

El mètode adequat és Prova directa, perquè surt directament de la definició, substituint i factoritzant.

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 tasca: Demostrar que si $n^{2}$ és parell llavors $n$ és parell.

El mètode adequat és Contraposició, perquè la hipòtesi és difícil de fer servir; la contraposada («$n$ senar implica $n^2$ senar») és immediata.

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 tasca: Demostrar que la suma dels $n$ primers enters val $n(n+1)/2$.

El mètode adequat és Inducció, perquè és un enunciat per a tot $n$ amb una estructura que relaciona cada cas amb l'anterior.

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 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 tasca: Refutar que $n^{2} + n + 41$ és primer per a tot $n$.

El mètode adequat és Contraexemple, perquè amb $n = 41$ el valor és divisible per $41$.

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 tasca: Demostrar que si $x$ és irracional llavors $1/x$ també ho és.

El mètode adequat és Contraposició, perquè si $1/x$ fos racional, $x$ també ho seria; és la contraposada.

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 tasca: Demostrar que tot enter més gran que $1$ és producte de primers.

El mètode adequat és Inducció, perquè cal inducció forta, perquè els factors poden ser qualsevol valor menor.

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 tasca: Demostrar que no hi ha cap racional amb quadrat igual a $3$.

El mètode adequat és Reducció a l'absurd, perquè mateix esquema que amb l'arrel de dos: suposar-ho i contradir la irreductibilitat.

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 + 1 = \frac{1\cdot2}{2} = 1$

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^{12} = 4096$

La desigualtat. Es compleix que $4096 > 12$, 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.

El valor.

$2^{24} = 16777216$

La desigualtat. Es compleix que $16777216 > 24$, 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.

El valor.

$2^{36} = 68719476736$

La desigualtat. Es compleix que $68719476736 > 36$, 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.