Iteração, indução e recursão

Uma definição recursiva de f nos naturais é um par base+passo: o valor em um ou poucos pontos iniciais, escrito sem citar f, e uma regra que escreve f(n) só em argumentos menores.

Provas de P(n), desdobramento, Horner e crivo deste tópico — e o termo geral de uma sequência, as relações de recorrência e a indução na derivação — partem desse par.

As páginas se agrupam em quatro blocos. O primeiro cobre todo n≥n₀ com P(n₀) e a implicação P(k)⇒P(k+1); a indução forte alarga o que o passo cita a P(n₀),⋯,P(k).

O segundo avalia a função determinada pela recorrência: desdobrar aplica a regra até os valores iniciais; iterar aplica a mesma regra na ordem crescente, com acumulador.

O terceiro avalia pₙ(x) só com adições e multiplicações. No formato padrão as potências xᵏ se produzem à parte; no encadeado cada passo multiplica o valor corrente por x e soma o coeficiente.

O quarto lista os primos em {2,…,N}: risca os múltiplos de cada primo já encontrado, com parada em √N.

Indução matemática prova ∀n≥n₀ P(n) por base e passo. Recursão e iteração define f, desdobra f(n) e itera a regra num acumulador.

Dois valores iniciais para f(n)=f(n−1)+f(n−2) estão em Recursão e iteração. Duas bases P(n₀) e P(n₀+1), quando o passo cita P(k) e P(k−1), estão em Indução matemática.

O laço que acumula 1·2···n está em Recursão e iteração. O laço p←p·x+aₖ e a conta n multiplicações mais n adições estão em Avaliação de polinômios.

Usar "n é primo ou produto de primos" como P(n) está em Indução matemática. Justificar que 1 não é primo e crivar até 60 está em Primos e crivo.