Lista de Exercícios 4: Soluções

1 ListadeExerc cios4: solu esSequ nciaseIndu oMatem ticaUFMG/ICEx/DCCDCC111 Matem ticaDiscretaCi nciasExatas& merosracionaisQ enumer vel,ouseja, p oss velatribuir(asso ciar)acadan meroracionalumn ,osn merosracionaisp ositivosest orepresentadosnaformadeumparordenadoonde oprimeiron andodon meroracional1 parordenado(1,1) p oss velasso ciaron meronatural1e,seguindoosentidodassetas,a tribuiropr ximon meronaturalde nindoassimumasequ nciadeenumera meroracionalp ositivopq,qual on meronaturalcorresp ondente? ..(1,6) (2,6) (3,6) (4,6) (5,6) (6,6).. (1,5) (2,5) (3,5) (4,5) (5,5) (6,5).. (1,4) (2,4) (3,4) (4,4) (5,4) (6,4).. (1,3) (2,3) (3,3) (4,3) (5,3) (6,3).. (1,2) (2,2) (3,2) (4,2) (5,2) (6,2).. (1,1) (2,1) (3,1) (4,1) (5,1) (6,1)..Resposta:Deacordocomoenunciadoaci ma,aenumera odosn merosracionaisir o correrdaformaapresentadaaseguir(on meronaturalasso ciadoacadan meroracionalest entrecolchetes).

2 (1,6) (2,6) (3,6) (4,6) (5,6) (6,6)..[21] (1,5) (2,5) (3,5) (4,5) (5,5) (6,5)..[11][20] (1,4) (2,4) (3,4) (4,4) (5,4) (6,4)..[10][12][19] (1,3) (2,3) (3,3) (4,3) (5,3) (6,3)..[4][9][13][18] (1,2) (2,2) (3,2) (4,2) (5,2) (6,2)..[3][5][8][14][17] (1,1) (2,1) (3,1) (4,1) (5,1) (6,1)..[1][2][6][7][15][16]1a2a3a4a5a6aD iagonaisPontosaobservar: On meroracionalp ositivopq representadop eloparordenado(p, q);1 Asomados ndicespeqdosparesordenadosaolongodecadad iagonal enasumparordenado, ,(1,1), ,assomasdos ndicesvalem3,4,5,etc; Naprimeiradiagonaltemosumparordenado,nas egundadois,naterceiratr caqueemcadadiagonaltemos(p+q) 1paresordenados; Quandoasomap+q umn mero mpar,aenumera oo corredebaixoparacimae,quando par,o corredecimaparabaixo; Paracalcularon meronaturalkasso ciadoaon meroracional(p, q)temosquesab erquantosparesordenadosexistemnasdiagona isanteriores diagonalondeseencontraopar(p, q).

3 Essa asomade1a(p+q) 2,representadap orS:S [(p+q) 2] [(p+q) 1]2. Finalmente,deve-sedeterminarosentidodaen umera o(debaixoparacima,ouvice-versa)paraopar( p, q):se(p+q) mod 2 = 0//(p+q) umn meropar, ,adiagonal dedescida?ent ok S+p//Sim,devemossomaraSovalordep,que ok S+q//N o,devemossomaraSovalordeq,que otermoquecresce. mseObservequequandoosentidodaenumera o decimaparabaixoaolongodadiagonal,on meropdevesersomadoaSparadeterminarap osi ocorretadaenumera oforocontr rio,on orindu omatem ticaque12+ 22+..+n2=n(n+ 1)(2n+ 1)6, n :Prova(p orindu omatem tica):(a)Passobase:Paran= 1,12= 1en(n+1)(2n+1)6=1 2 36= verdadeiro.(b)Passoindutivo:seaf rmula verdadeiraparan=k, k 1ent odeveserverdadeiraparan=k+1. Hip teseindutiva:12+ 22+..+k2=k(k+ 1)(2k+ 1)6, k 1 Deve-semostrarque:12+ 22+..+k2+ (k+ 1)2=(k+ 1)(k+ 2)(2k+ 3)6 Sab e-seque:12+ 22+..+k2+ (k+ 1)2=k(k+ 1)(2k+ 1)6+ (k+ 1)2=k(k+ 1)(2k+ 1) + 6(k+ 1)26=(k+ 1)[k(2k+ 1) + 6(k+ 1)]6=(k+ 1)[2k2+k+ 6k+ 6]6=(k+ 1)(2k2+ 7k+ 6)6=(k+ 1)(k+ 2)(2k+ 3) orindu omatem ticaque1 + 3 + 5 +.

4 + (2n 1) =n2, n :Prova(p orindu omatem tica):(a)Passobase:Paran= 1,1 = verdadeiro.(b)Passoindutivo:seaf rmula verdadeiraparan=k, k 1ent odeveserverdadeiraparan=k+1. Hip teseindutiva:1 + 3 + 5 +..+ (2k 1) =k2, k 1 Deve-semostrarque:1 + 3 + 5 +..+ (2k 1) + (2k+ 1) = (k+ 1)2, k 1 Sab e-seque:1 + 3 + 5 +..+ (2k 1) + (2k+ 1) =k2+ (2k+ 1)= (k+ 1) orindu omatem ticaque13+ 23+..+n3= (1 + 2 +..+n)2, n :Essaprovap o deserdivididaemduaspartes:(i)provadosoma t riodoladodireitoesubstitui op elaf rmulafechada,e(ii)provadosomat e-sequeasoma1 + 2 +..+n, n 1,valen(n+1)2(estaprovap o deserobtidap orindu omatem tica).Assim,temosque13+ 23+..+n3=n2(n+ 1)24, n (p orindu omatem tica):(a)Passobase:Paran= 1,13=12(1+1) verdadeiro.(b)Passoindutivo:seaf rmula verdadeiraparan=k, k 1ent odeveserverdadeiraparan=k+1. Hip teseindutiva:13+ 23+..+k3=k2(k+ 1)24, k 1 Deve-semostrarque:13+ 23+..+k3+ (k+ 1)3=(k+ 1)2(k+ 2)24, k 1 Sab e-seque:13+ 23+.

5 +k3+ (k+ 1)3=k2(k+ 1)24+ (k+ 1)3=k2(k+ 1)24+ (k+ 1)(k+ 1)2=k2(k+ 1)24+4(k+ 1)(k+ 1)24=(k+ 1)2(k2+ 4k+ 4)4=(k+ 1)2(k+ 2) orindu omatem ticaque2 1 + 2 2 + 2 3 +..+ 2n=n2+n, n :Prova(p orindu omatem tica):(a)Passobase:Paran= 1,2 1=2e12+ 1 = verdadeiro.(b)Passoindutivo:seaf rmula verdadeiraparan=k, k 1ent odeveserverdadeiraparan=k+1. Hip teseindutiva:2 1 + 2 2 + 2 3 +..+ 2k=k2+k=k(k+ 1), k 1 Deve-semostrarque:2 1 + 2 2 +..+ 2k+ 2(k+ 1) = (k+ 1)2+ (k+ 1)= (k+ 1)[(k+ 1) + 1]= (k+ 1)(k+ 2), k 1 Sab e-seque:2 1 + 2 2 +..+ 2k+ 2(k+ 1) =k(k+ 1) + 2(k+ 1)=k2+k+ 2k+ 2=k2+ 3k+ 2= (k+ 1)(k+ 2) orindu omatem ticaquen 1 i=1i(i+ 1) =n(n 1)(n+ 1)3, inteirosn :Prova(p orindu omatem tica):(a)Passobase:Paran= 2, n 1i=1i(i+ 1) = 1i=1i(i+ 1) = 1(1 + 1) = 2en(n 1)(n+1)2=2 1 33= verdadeiro.(b)Passoindutivo:seaf rmula verdadeiraparan=k, k 2ent odeveserverdadeiraparan=k+1. Hip teseindutiva:k 1 i=1i(i+ 1) =k(k 1)(k+ 1)3 Deve-semostrarque:k i=1i(i+ 1) =k(k+ 1)(k+ 2)3 Sab e-seque:k i=1i(i+ 1) =k 1 i=1i(i+ 1) +k(k+ 1)=k(k 1)(k+ 1)3+k(k+ 1)4=k(k 1)(k+ 1) + 3k(k+ 1)3=k(k+ 1)[(k 1) + 3]3=k(k+ 1)(k+ 2) rmulafechadaparaasoma11 2+12 3+13 4+.

6 +1n(n+ 1) inteirosn 1eproveoseuresultadop orindu omatem :Prova(p orindu omatem tica):Somandoosprimeirostermosesimpli candotemosque:11 2+12 3=2311 2+12 3+13 4=3411 2+12 3+13 4+14 5=45oquelevaaconjecturaqueparato dososinteirosp ositivosn,11 2+12 3+13 4+..+1n(n+ 1)=nn+ 1(a)Passobase:Paran= 1,11 2=12,que ovalordaf verdadeiro.(b)Passoindutivo:seaf rmula verdadeiraparan=k, k 1ent odeveserverdadeiraparan=k+1. Hip teseindutiva:11 2+12 3+13 4+..+1k(k+ 1)=kk+ 1 Deve-semostrarque:11 2+12 3+13 4+..+1k(k+ 1)+1(k+ 1)(k+ 2)=k+ 1k+ 2 Sab e-seque:11 2+12 3+13 4+..+1k(k+ 1)+1(k+ 1)(k+ 2)=kk+ 1+1(k+ 1)(k+ 2)=k(k+ 2) + 1(k+ 1)(k+ 2)=k2+ 2k+ 1(k+ 1)(k+ 2)=(k+ 1)2(k+ 1)(k+ 2)=k+ 1k+ rmulafechadaparaopro duto(1 12)(1 13)(1 14)..(1 1n)5 inteirosn 2eproveoseuresultadop orindu omatem :Sejaasup osi oque(1 12)(1 13)(1 14)..(1 1n)=n i=2(1 1i)=1n inteirosn osi o (p orindu omatem tica):(a)Passobase:Paran= 2, 2i=2(1 1i) = (1 12) =12eaf verdadeiro.

7 (b)Passoindutivo:seaf rmula verdadeiraparan=k, k 2ent odeveserverdadeiraparan=k+1. Hip teseindutiva:(1 12)(1 13)(1 14)..(1 1k)=k i=2(1 1i)=1k Deve-semostrarque:(1 12)(1 13)(1 14)..(1 1k)(1 1k+ 1)=k+1 i=2(1 1i)=1k+ 1 Sab e-seque:k+1 i=2(1 1i)=k i=2(1 1i) (1 1k+ 1)=(1k) (1 1k+ 1)=(1k) ((k+ 1) 1k+ 1)=1k+ rmulafechadaparaasoma11 3+13 5+..+1(2n 1) (2n+ 1) inteirosn 1eproveoseuresultadop orindu omatem :Sejaasup osi oque11 3+13 5+..+1(2n 1) (2n+ 1)=n2n+ 1 inteirosn (p orindu omatem tica):(a)Passobase:Paran= 1,1(2n 1) (2n+1)=1(2 1 1) (2 1+1)=11 3=13eaf rmulafechadavale12 1+1= verdadeiro.(b)Passoindutivo:seaf rmula verdadeiraparan=k, k 1ent odeveserverdadeiraparan=k+1. Hip teseindutiva:11 3+13 5+..+1(2k 1) (2k+ 1)=k2k+ 16 Deve-semostrarque:11 3+13 5+..+1(2(k+ 1) 1) (2(k+ 1) + 1)=k+ 12(k+ 1) + 1ouequivalentemente,11 3+13 5+..+1(2k+ 1) (2k+ 3)=k+ 12k+ 3 Sab e-seque:11 3+..+1(2k 1)(2k+ 1)+1(2k+ 1)(2k+ 3)=k2k+ 1+1(2k+ 1)(2k+ 3)=k(2k+ 3)(2k+ 1)(2k+ 3)+1(2k+ 1)(2k+ 3)=2k2+ 3k+ 1(2k+ 1)(2k+ 3)=(2k+ 1)(k+ 1)(2k+ 1)(2k+ 3)=k+ 12k+ rmulafechadaparaasoman i=21(i 1)i, inteirosn 2eproveoseuresultadop orindu omatem :Sejaasup osi oquen i=21(i 1)i= 1 1n inteirosn osi o (p orindu omatem tica):(a)Passobase:Paran= 2,osdoisladosdaequa verdadeiro.

8 (b)Passoindutivo:seaf rmula verdadeiraparan=k, k 2ent odeveserverdadeiraparan=k+1. Hip teseindutiva:k i=21(i 1)i= 1 1k, k 2. Deve-semostrarque:k+1 i=21(i 1)i= 1 1k+ 1, k e-seque:k+1 i=21(i 1)i=k i=21(i 1)i+1k(k+ 1)= 1 1k+(1k 1k+ 1)= 1 1k+ (n)usandoindu omatem tica:P(n):Qualquern merointeirop ositivon 8p o deserescritocomoasomade3'se5' :Prova(p orindu omatem ticafraca):(a)Passobase:P(n0) =P(8):Paran0= 8,temosque8 = 3 + 5eopredicadoP verdadeiro.(b)Passoindutivo:seaf rmula verdadeiraparan=kent odeveserverdadeiraparan=k+ 1, ,P(k) P(k+ 1). Sup onhaqueaf rmulasejaverdadeiraparan=k, ,P(k) :k= 3a+ 5b,paraa 0eb 0.[hip teseindutiva] Deve-semostrarqueP(k+ 1) :k+ 1 = 3a + 5b ,paraa 0eb + 1:(i)b6= 0: p oss velsubstituirum5p ordois3'squando feitaasomade:k+ 1 = 3a+ 5b+ 1= 3a+ 5(b 1) + 5 + 1= 3a+ 2 3 + 5(b 1)= 3a + 5b (ii)b= 0:Nestecaso,devehaverp elomenostr s3'sparatermosvaloresden ,temos:k+ 1 = 3a+ 1= 3(a 3) + 3 3 + 1= 3a + 2 5= 3a + 5b [Istoeraoquedeviaserprovado.]

9 ] p oss velterqualquervalordep :Prova(p orindu omatem ticaforte):(a)Passobase:Paraosseguintesv aloresdep ostagemp p oss velusarap + 7 + 4197 + 4 + 4 + 4204 + 4 + 4 + 4 + 4217 + 7 + 7 Assim,opassobase verdadeiro.(b)Passoindutivo:Vamossup orqueparato dosinteirosp,18 p < k,psejaumvalordep ostagemquep o deserobtidoap osi otamb m or4temosumquo ostagemp [18,21]temostamb ,kp o deserexpressocomoumvalordep ostagempentre18e21somandodeumfatorm pmod 4paraumvalordep [18,21].Isto lidocomo:k congruentecompm dulo4,oquesigni caqueexisteumvalordep [18,21]quequandodivididop or4deixaomesmorestoquekquandodivididop orindu omatem ticaquen2<2n,parato dosinteirosn :Prova(p orindu omatem tica):(a)Passobase:Paran= 5,adesigualdade52<25 ,opassobase verdadeiro.(b)Passoindutivo:seaa rma o verdadeiraparan=k, k 5ent odeveserverdadeiraparan=k+ 1. Hip teseindutiva:k2<2kparato dosinteirosk 5. Deve-semostrarque:(k+ 1)2<2k+1parato dosinteirosk e-seque:(k+ 1)2=k2+ 2k+ 1<2k+ 2k+ 1p elahip e-setamb mque2k+ 1<2kparak candoestasdesigualdadesjuntas,temos;(k+ 1)2<2k+ 2k+ 1<2k+ nciaa1, a2, a3.

10 De nidacomoa1= 3ak= 7ak 1, inteirosk 2 Provep orindu omatem ticaquean= 3 7n 1parato dososinteirosn :Prova(p orindu omatem tica):(a)Passobase:Paran= 1,an=a1= 3 71 1= 3 1 = verdadeiro.(b)Passoindutivo:seaa rma o verdadeiraparan=k, k 1ent odeveserverdadeiraparan=k+ 1. Hip teseindutiva:ak= 3 7k 1parato dosinteirosk 1. Deve-semostrarque:ak+1= 3 7(k+1) 1= 3 7kparato dosinteirosk e-seque:ak+1= 7ak, inteirosk 2= 7 (3 7k 1)Hip teseindutiva= 3 nciaa1, a2, a3, ..de nidacomoa1= 1a2= 3ak=ak 2+ 2ak 1, inteirosk 3 Provep orindu omatem ticaquean mparparato dososinteirosn :Prova(p orindu omatem ticaforte):9(a)Passobase:Apropriedade verdadeiraparan= 1en= 2,j quea1= 1ea2= 3,ques o mpares.(b)Passoindutivo:Sek >2eapropriedade verdadeiraparato dosi,1 i < k,ent odeveserverdadeiraparan=k. Hip teseindutiva:Sejak >2uminteiroesup onhaqueai mparparato dososinteirosi,1 i < k. Deve-semostrarqueak e-sep elade ni odea1, a2, a3.