1. Dê quantos significados você puder para A Þ B.
   
   
2. Explique o que s ao as técnicas de prova direta, por força bruta, por contradição. Dê um exemplo de cada. Esta técnica pode ser usada para uma prova por indução ? Como e onde ? O que é contra-positivo.
   
   
3. Prove por indução matemática:
   1² - 2² + 3² - 4² + ... + (-1)^k-1 k² = (-1)^k-1 k(k+1)/2
   
   
4. Prove por indução matemática:
   7ⁿ - 2ⁿ
   é múltiplo de 5 para qualquer n inteiro e maior ou igual a 1.
   
   
5. Encontre o menor inteiro n₀ para o qual n! ³ 2ⁿ. Prove que esta relação é válida para n ³ n₀.
   
   
6. Prove que para n ³ 0 e inteiro, n² + 3n é divisível por 2 e n³ + 3n² + 2n é divisível por 6.
   
   
7. Prove por indução matemática simples:
   1. Para todo n > 1 e inteiro,

      1 n+1

      +

      1 n+2

      + ... +

      1 2n

      >

      13 24

   2. Para todo n ³ 0 e inteiro,

      12 + 22 + 32 + ... + n2 =

      n(n+1)(2n+1) 6

   3. Sejam a, b e n inteiros positivos. Prove por indução que:
      2^n-1 ( aⁿ + bⁿ ) ³ (a + b)ⁿ
   
   
8. Seja a série de números de Fibonacci F(0),F(1),F(2),... definidos da seguinte forma:
   F(0)=0 e F(1) = 1
   F(n) = F(n-1) + F(n-2) para n ³ 2
   Prove por indução matemática simples os ``teoremas'' abaixo para todo n ³ 0:
   1. F(0) + F(1) + F(2) + ... + F(n)   =   F(n+2) - 1
   2. F(3n) é par
   3. F(5n) é divisível por 5
   4. F(1) + F(3) + F(5) + ... + F(2n-1)   =   F(2n)
   5. F(0) - F(1) + F(2) - F(3) ... - F(2n-1) + F(2n)   =   F(2n-1) - 1
   6. F²(0) + F²(1) + F²(2) + ... + F²(n)   =   F(n).F(n+1)
   7. F(n-1).F(n+1) - F²(n)   =   (-1)ⁿ
   8. F²(n) + F²(n-1)   =   F(2n-1)
   9. F(n+1).F(n) + F(n).F(n-1)   =   F(2n)
   10. F(2) + F(4) + F(6) + ... + F(2n)   =   F(2n+1) - 1
   11. F²(n+1) - F²(n)   =   F(n-1).F(n+2)
   
   
9. Prove que um número em sua representação decimal (base 10) é divisível por 3 se e somente se a soma dos seus dígitos também é. Tente provar este mesmo teorema para as base 8 e 7.
   
   
10. Prove que dada uma região (convexa) as (sub)regiões definidas por retas que cortam esta região (inicial) podem ser coloridas (de modo que regiões adjacentes, ou seja que são dividas por uma reta, tenham cores diferentes) com 2 cores.
    
    
11. Seja N={ 1, 2, ..., n}. Enumere todas as sequências crescentes dos elementos de N que existem, começando com 1 e terminando com n ? (As sequências podem ter qualquer tamanho.) Quantas são?
    
    
12. Seja X₁ = { 0, 1 } e para i ³ 2 defina X_i como o conjunto de subconjuntos de X_i-1. Encontre uma fórmula em função de n, f(n), para exprimir a cardinalidade de X_n, i.e. |X_n|. Prove, por indução matemática, que esta fórmula está correta. Determine o menor valor de n para que |X_n| > 10¹⁰⁰.
    
    
13. Prove por indução matemática que se n e m são inteiros tais que 1 £ m £ n
    n² - m(n+1) + 2n + m² £ n² + n
    
    
    ALGORITMOS E PROVAS POR INDUÇÃO
    
    
14. Prove por indução matemática que o número de números inteiros de K dígitos diferentes 1,2,...,m é m.(m-1). .... . (m-k+1). Utilize sua prova para propor um algoritmo que enumere todos estes números.
    
    
15. Considere o problema de encontrar os dois maiores elementos I={i₁, i₂, ..., i_n }.
    Teorema 1  (K): Sabe-se encontrar os dois maiores elementos de I^K={i₁, i₂, ..., i_K }.
    
    1. Prove este teorema por indução SIMPLES.
    2. Apresente um algoritmo correspondente à sua prova no item anterior.
    3. Prove este teorema por indução FORTE.
    4. Apresente um algoritmo correspondente à sua prova no item anterior.
    5. Mostre, sucintamente, como o seus algoritmos executam sobre I = { 12, 9, 19, 3, 18, 21, 7,17}, onde n=8.
    
    
16. Considere a série 1,2,3,4,5,10,20,40,80, ... que depois do quinto termo se torna uma série geométrica. Prove, por indução matemática FORTE, que todo número inteiro positivo pode ser escrito como uma soma de elementos DISTINTOS dessa série. Utilize a sua prova para escrever um algoritmo que, para qualquer número inteiro maior que zero, determine elementos (todos diferentes) desta série cuja soma é igual ao seu valor.
    
    
17. Considere o problema de se encontrar o máximo divisor comum (MDC) entre um par de inteiros.
    1. Sabendo-se que o MDC entre dois inteiros p e q, p>q, é igual ao MDC entre q e o resto da divisão de p por q, prove o teorema abaixo por INDUÇÃO FORTE.
       
       Teorema(N): Sabe-se encontrar o MDC entre todo par de números menores ou iguais a N.
       
       
    2. Apresente o algoritmo correspondente à sua prova.
    
    
18. Suponha que temos a sequencia a₁, a₂, ... para todo n>1 onde a_n+1 = 2.a_n + a_n-1.
    
    Prove por indução matemática que se a₁ e a₂ são inteiros, então todos os termos da sequência são inteiros.
    
    
19. A lei da comutatividade da adição diz que x + y = y + x. A lei da comutatividade geral da adição diz que a soma de x₁, x₂, ..., x_n é a mesma para a soma realizada em qualquer ordem.
    
    Prove a lei da comutatividade geral da adição por indução matemática.
    
    
20. Considere o conjunto de permutações de 1,2,3,...,n. Uma permutação pode ser denotada por pⁱ=p₁ⁱ,p₂ⁱ,...,p_nⁱ.
    
    Determine o número de permutações onde p_jⁱ ¹ j para todo j.
    
    
21. Uma celebridade em um grupo é uma pessoa que todos conhecem e que não conhece ninguém. Assuma que todas as possíveis perguntas ``i conhece j ?'' são feitas e que as respostas estejam disponíveis em uma matriz onde seus elementos, conhece[i,j], assumem o valor 1, se i conhece j, e 0, caso contrário (a diagonal não é usada). Deseja-se determinar se em um dado grupo de pessoas existe ou não uma celebridade e, em caso afirmativo, determinar quem é a celebridade.
    1. Enuncie o teorema que atesta que sabe-se resolver este problema.
    2. Prove este teorema por indução (simples).
    3. Escreva o algoritmo correspondente à sua prova para o teorema.

This document was translated from L^AT_EX by H^EV^EA.