Exercicis de principis de demostració

El valor.

$2^{7} = 128$

La desigualtat. Es compleix que $128 > 7$, 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 $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 fórmula.

$1 + 2 + \cdots + 8 = \frac{8\cdot9}{2} = 36$

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^{8} = 256$

La desigualtat. Es compleix que $256 > 8$, 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 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 fórmula.

$1 + 2 + \cdots + 9 = \frac{9\cdot10}{2} = 45$

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^{9} = 512$

La desigualtat. Es compleix que $512 > 9$, 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 el producte de dos senars és senar.

El mètode adequat és Prova directa, perquè substituint les definicions i factoritzant surt sol.

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 + 10 = \frac{10\cdot11}{2} = 55$

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^{10} = 1024$

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