1. Encontre o menor inteiro n₀ para o qual n! ³ 2ⁿ. Prove que esta relação é válida para n ³ n₀.
   
   
2. Prove que para n ³ 0 e inteiro, n² + 3n é divisível por 2 e n³ + 3n² + 2n é divisível por 6.
   
   
3. 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)ⁿ
   
   
4. 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)
   
   
5. 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.
   
   
6. 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.
   
   
7. 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?
   
   
8. 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¹⁰⁰.
   
   
9. 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
   
   
10. 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.
    
    
11. 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.
    
    
12. 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.
    
    
13. 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.

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