Indução Matemática: Provas e Aplicações em Conjuntos e Números Naturais

1 Usando o princípio da indução prove que a 1 2 n nn 12 b 1 3 5 2n 1 n2 c i1n ii 1 nn 1n 23 2 Seja card X o número de elementos do conjunto finito X Prove que se X é finito e Y X então card Y card X 3 Dados m e n naturais com n m então existe q ℕ tal que qm n q 1m 4 Dados n m então existe q ℕ tal que n qm ou qm r n com r m 5 Não existe x ℕ tal que n x n 1 6 Se A ℕ é um subconjunto não vazio e limitado superiormente então A possui um elemento máximo 7 Dado ϕ A B bijetiva temos que f B B é injetiva sobrejetiva se e somente se ϕ1 f ϕ A A é injetiva sobrejetiva 1 a Prova Suponha que n 1 então 1 1112 Logo a igualdade vale para n 1 Passo indutivo Suponha que para n k vale 1 2 k kk 12 Então para k 1 vale 1 2 k k 1 k 1k 22 De fato temos 1 2 k k 1 kk 12 k 1 por hipótese de indução k2 k 2k 22 k2 3k 22 k 1k 22 Portanto 1 2 n nn 12 n ℕ b Prova seja n 1 então 2 1 1 1 12 Logo para n 1 vale a igualdade Passo indutivo Suponha que para n k vale 1 3 5 2k 1 k2 Então para k 1 vale 1 3 5 2k 1 2k 1 k 12 De fato 1 3 5 2k 1 2k 1 k2 2k 1 por hipótese indutiva k 1 k 1 k 12 Portanto 1 3 5 2n 1 n2 n ℕ c Prova Para n 1 temos i11 i i 1 1 1 1 2 1 1 1 1 23 Logo vale a igualdade para n 1 Passo indutivo Suponha que para n k vale i1k i i 1 k k 1 k 23 Então para n k 1 i1k1 i i 1 k 1 k 2 k 33 De fato i1k1 i i 1 2 6 k k 1 k 1 k 2 k k 1 k 23 k 1 k 2 por hipótese de indução k2 k k 2 3 k 1 k 23 k3 2k2 k2 2k 3k2 9k 63 k3 6k2 11k 63 k 1 k 2 k 33 Portanto i1n i i 1 n n 1 n 23 n ℕ 2 Prova Seja X um conjunto finito então temos das possibilidades X ou X Se X temos duas possibilidades para o conjunto Y X i Y Se Y então card Y 0 Como X considerando card X m com m N Temos card Y 0 m card X Logo card Y card X ii Y Suponha Y Por hipótese X é finito e Y X logo Y é finito pois todo subconjunto de um conjunto finito é finito Como X Y e ainda são finitos então existem bijeções f In X e g Im Y com Iλ p N p λ τ Daí segue card X n e card Y m Agora suponha que m n Como Y X a função h Y In é a restrição de f¹ X In Como f¹ é uma bijeção então h f¹Y Y f¹Y In é uma bijeção Como g Im Y é bijeção podemos estender a representação ou seja ℓ h g Im f¹Y In é bijeção pois é composta de duas bijeções Logo ℓ é uma bijeção de Im em f¹Y e portanto f¹Y m Considerando f¹Y In então card In card f¹Y isto é n m Contradição Pois supomos m n Portanto m n ou seja card Y card X Agora se X como Y X então Y Logo card Y 0 card X Portanto card Y card X 3 Prova Dados m n IN com n m Temos i se n é múltiplo de m então existe q IN tal que n qm ii se n não é múltiplo de m então n está entre dois múltiplos consecutivos de m isto é existe q IN tal que qm n q 1m 4 Prova Dados m n IN com n m Temos i se n é múltiplo de m existe q IN tal que n qm ii se n não é múltiplo de m n está situado entre dois múltiplos consecutivos de m Então existe q IN tal que qm n q 1m 0 n qm m Tome r n qm IN Então de obtemos 0 r m com n qm r Logo se n m então ou n qm para algum q IN ou existem q r IN tais que n qm r Onde 0 r m 5 Prova Suponha que dado n IN exista x IN tal que n x n 1 1 sabemos que x n então existe p IN tal que x n p Substituindo em 1 n x n 1 n n p n 1 n n n n p n n 1 0 p 1 Absurdo Pois p IN Portanto não existe x IN tal que n x n 1 6 Prova Considere o seguinte conjunto X x N x a a A Afirmação 1 X De fato como A N e A e A é limitado superiormente então existe x N tal que x a a A Logo x X Pelo Princípio da Boa Ordenação o conjunto X possui um elemento mínimo digamos x₀ Afirmação 2 x₀ 1 Caso contrário isto é se x₀ 1 Sabemos que 1 n n N como x₀ X e x₀ a a A então x₀ 1 Como x₀ 1 existe n N tal que x₀ n 1 como n x₀ então n X Pois x₀ é o menor elemento de X Logo existe a A tal que a n Mas se a n então a n 1 x₀ Contradição Pois x₀ a a A Logo n A e n a a A Portanto n é o elemento máximo de A 7 o ℓ A B bijetiva f B B é injetiva ℓ¹ f ℓ A A injetiva Prova Sejam ℓ¹ f ℓa₁ ℓ¹ f ℓa₂ com a₁ a₂ A Então ℓ¹fℓa₁ ℓ¹fℓa₂ Como f e ℓ são injetivas então fℓ é injetiva Pois composta de funções injetivas é injetiva Então a₁ a₂ Portanto ℓ¹ f ℓ é injetiva Suponha que ℓ¹ f ℓ é injetiva Então se a₁ a₂ A com ℓ¹fℓa₁ ℓ¹fℓa₂ implica que a₁ a₂ Temos Lo lo1 f1e1a1 lo lo1 f1e1a1 f1 e1a1 f1 e1a1 Como l é injetiva então la1 la2 Pois a1 a2 Portanto f é injetiva l A B bijetiva f B B sobrejetiva l1 f l A A sobrejetiva Prova Como l é sobrejetiva b1 B existe a A tal que l1a1 b1 como f é sobrejetiva b1 B b B tal que fb1 b1 Logo l1 f1 e1a l1 fb l1b a Logo l1 o f o l é sobrejetora Se l1 o f o l é sobrejetiva a A a A tal que l1f1 e1a1 a f1e1a1 e1a Como l é sobrejetiva segue que l é sobrejetiva