Lògica, raonament i demostració. Pràctica

3 Demostració

Exercici 24.

Donat un enter positiu n, proveu directament que n3-n és sempre múltiple de 3.

Solució: Observa primer que n(n2-1)=n(n+1)(n-1). Aquest tres factors són tres nombres naturals consecutius i, per tant, un d’ells serà un múltiple de 3. Com a conseqüència n3-n és sempre múltiple de 3.  

Exercici 25.

Demostreu directament que per a cada terna de nombres reals positius a,b i c es compleix que

ab+c+ba+c+ca+b1.

Solució: Considerem a>0,b>0 i c>0. Aleshores podem escriure les tres expressions següents:

M =ab+c+ba+c+ca+b
N =aa+c+cb+c+ba+b
P =ca+c+bb+c+aa+b

Es clar que N+P=3 i 3MM+N+P. Aleshores es té 2MN+P i, per tant, M32>1.

Una altra forma de provar aquesta desigualtat és aplicant el fet que la mitjana aritmètica és més gran que la hipergeomètrica. En efecte, podem escriure ara d’aquesta manera:

M =ab+c+aa+c+aa+b
N =bb+c+ba+c+ba+b
P =cb+c+ca+c+ca+b

Sumant tenim:

M+N+P=ab+c+ba+c+ca+b+3 (3.1)

Ara bé,

M+N+P=a+b+cb+c+a+b+ca+c+a+b+ca+b

Aplicant el que hem dit abans:

12(b+c)+(a+c)+(a+b)331b+c+1a+c+1a+b.

Per tant, es té

a+b+cb+c+a+b+ca+c+a+b+ca+b=
32(b+c)+(a+c)+(a+b)3(1b+c+1a+c+1a+b)
3231b+c+1a+c+1a+b1b+c+1a+c+1a+b92.

D’aquí i (3.1), surt

ab+c+ba+c+ca+b+392,

i, per tant,

ab+c+ba+c+ca+b32.

Exercici 26.

Proveu cap a enrere que per a qualssevol nombres reals negatius, a<b implica a2>b2.

Solució: La prova cap enrere surt de la tesi, i, per tant, podem fer es següent:

a2>b2 Tesi
|a|>|b| Prenent arrels quadrades
-a>-b a,b són negatius
a<b Multiplicant per -1 i surt l’hipòtesi

De fet, això que hem escrit s’havia d’haver pensat mentalment perquè la demostració real és una prova directa: Si a<b, multiplicant per -1, es té -a>-b i -a,-b són positius. Per tant, (-a)2>(-b)2 o sigui, a2>b2.  

Exercici 27.

Proveu per contrarecíproc que per a qualssevol n,m, si mn és senar, llavors m i n són senars.

Solució: Si fessim la prova directa seria prendre com hipòtesi que mn és senar i hem d’arribar a veure que m i n també ho són. En canvi, per contrarecíproc serà prendre com hipòtesi que no és el cas que m i n siguin senars i hem d’arribar a provar que mn no és senar.

Si no és el cas que m i n siguin senars, vol dir que m és parell o n és parell. Suposem per exemple que m és parell. Aleshores existeix k tal que m=2k. Per tant, mn=2kn i kn. Aleshores mn és parell com voliem demostrar.  

Exercici 28.

Proveu per reducció a l’abssurd que els únics enters consecutius no negatius a,b i c que compleixen a2+b2=c2 són 3,4 i 5.

Solució: Suposem que 3,45 no són els únics enters consecutius no negatius que compleixen a2+b2=c2. Això és equivalent a suposar que existeixen enters no negatius n,n+1 i n+2 i n3 tals que

n2+(n+1)2=(n+2)2

Ara bé, fent operacions, s’obté l’equació n2-2n-3=0, què té com a solucions 3 i -1. Per tant, arribem a un absurd perquè hem suposat que n3. Com a conseqüència, hem provat el que volíem.  

Exercici 29.

Siguin a,b i c enters. Suposem que hi ha un nombre enter d que da i db, però que d no divideix c. Demostreu per reducció a l’absurd que l’equació ax+by=c no té cap solució que x i y siguin enters.

Solució: Suposem que ax+by=c té una solució tal que x i y són enters. Com d divideix a i també b, aleshores existeixen enters m i n tals que a=md i b=nd. Aleshores, es té

mdx+ndy=c

Dividint per d, s’obté

mx+ny=cd

Però això és absurd perquè mx+ny és enter i, per tant, també cd i això no és possible perquè d no divideix c.  

Exercici 30.

Proveu per inducció:

  1. 1.

    Si n és un nombre enter no negatiu, llavors k=0nkk!=(n+1)!-1.

  2. 2.

    Si n, llavors (1+x)n1+nx per a tot x i x>-1.

Solució: (1) Construïm una prova d’inducció sobre n, sent P(n)=k=0nkk!=(n+1)!-1”.

Cas base:

P(1) és k=01kk!=(1+1)!-1 i, això és veritat perquè 00!+11!=1.

Hipòtesi d’inducció:

Suposem que P(n) és certa, o sigui que k=0nkk!=(n+1)!-1.

Tesi:

Hem de demostrar que P(n+1)=k=0n+1kk!=(n+2)!-1” és certa.

En efecte, aplicant l’hipòtesi d’inducció, es té

k=0n+1kk! =k=0nkk!+(n+1)(n+1)!
=(n+1)!-1+(n+1)(n+1)!
=(1+n+1)(n+1)!-1
=(n+2)!-1

que és el que volíem veure.

Conclusió:

Pel principi d’inducció sobre n, deduïm que P(n) és certa per a tot n.

(2) Construïm una prova d’inducció sobre n, sent P(n)= “Si n, llavors (1+x)n1+nx per a tot x i x>-1”.

Cas base:

P(1) és evident que és vertadera.

Hipòtesi d’inducció:

Suposem que P(n) és certa, o sigui que si n, llavors (1+x)n1+nx per a tot x i x>-1.

Tesi:

Hem de demostrar que P(n+1)=“Si n, llavors (1+x)n+11+(n+1)x per a tot x i x>-1” és certa.

En efecte, aplicant l’hipòtesi d’inducció, es té

(1+x)n+1 =(1+x)n(1+x)
=(1+nx)(1+x)
=1+x+nx+nx2
=1+(n+1)x+nx2
1+(n+1)x

que és el que volíem veure.

Conclusió:

Pel principi d’inducció sobre n, deduïm que P(n) és certa per a tot n.

Exercici 31.

Proveu que el residu del quadrat de qualsevol nombre enter quan es divideix per 4 és 0 o 1.

Solució: Tot nombre enter n és o parell o bé senar. Aquesta idea proporciona l’estratègia de la demostració: construïr una prova per casos:

(1) Si n és parell, aleshores n=2k, on k. Llavors, n2=4k2 què és múltiple de 4 i, per tant, quan es divideix per 4 el residu val 0.

(2) si n és senar, aleshores n=2k+1, on k. Llavors, n2=4k2+4k+1=4(k2+k)+1 què quan es divideix per 4 el residu val 1.  

Exercici 32.

Demostreu que per a cada nombre real x, si |x-3|>3 llavors x2>6x.

Solució: Per definició de valor absolut, |x-3|=x-3 si x-30, i |x-3|=-(x-3) si x-3<0. Construïm una prova per casos:

(1) Si x-30, aleshores |x-3|=x-3>3 i, per tant, x>6. D’aquí, s’obté x2>6x.

(2) Si x-3<0, aleshores |x-3|=-x+3>3 i, per tant, x<0. D’aquí, s’obté x2>6x.  

Exercici 33.

És cert que per a cada enter positiu n es compleix que n2-n+17 és un nombre primer?

Solució: Si pensem que l’enunciat és fals hem de trobar un contraexemple per provar-ho. En efecte, si prenem n=17, aleshores n2-n+17=289 que no és primer.  

Exercici 34.

(Algoritme de la divisió) Si a,b, proveu que existeixen enters q,r i són únics per els quals a=bq+r, sent 0r<b.

Solució: Sabem que a,b. Primer hem de provar l’existència, buscant aquests nombres enters que compleixen la propietat. Considerem el conjunt de múltiples positius b: B={kb:k}. Com el conjunt dels nombres naturals està ben ordenat per la relació , tot subconjunt té mínim. Per tant, existeix un natural n de B tal que nba<(n+1)b. Això és equivalent a 0a-nb<b, i si ara prenem r=a-nb i q=n es compleix la propietat.

Finalment, hem de demostrar la unicitat. Suposem que existeixen r i q que compleixen a=bq+r, sent 0r<b. Aleshores, es té

bq+r =bq+r
r-r =(q-q)b

i això vol dir que r-r és múltiple de b. Llavors, com 0r<b i 0r<b, s’obté 0|r-r|<b, i com a conseqüència, |r-r|=0 o sigui r=r. Aleshores, també q=q.