Questão 66750

Em uma aula de Lógica e Matemática Discreta, um professor quer demonstrar a seus alunos de um curso de computação a importância da Prova por Indução como uma ferramenta para verificar a correção de algoritmos e propriedades de estruturas de dados. Ele sente que os alunos veem a indução apenas como um truque para provar somatórios, sem entender sua conexão com a recursão e a computação. Para criar essa ponte, ele apresenta um trecho de um livro de algoritmos: "A Prova por Indução é um método poderoso para provar que uma propriedade $P(n)$ é válida para todos os inteiros $n$ a partir de um ponto inicial. Ela consiste em dois passos: o **Caso Base**, onde provamos que $P(n_0)$ é verdadeiro para um valor inicial $n_0$; e o **Passo Indutivo**, onde assumimos que $P(k)$ é verdadeiro para um $k$ arbitrário (a Hipótese de Indução) e, a partir dessa suposição, provamos que $P(k+1)$ também deve ser verdadeiro. A lógica da indução espelha a lógica da recursão: o caso base da indução corresponde ao caso base da recursão, e o passo indutivo corresponde ao passo recursivo, que assume que o problema já foi resolvido para um tamanho menor." O professor então propõe à turma que usem a Prova por Indução para provar que a soma dos $n$ primeiros números ímpares é igual a $n^2$. Ou seja, provar que $P(n): 1 + 3 + 5 + ... + (2n-1) = n^2$ para todo $n \ge 1$.

Avaliando a estrutura de uma Prova por Indução para esta propriedade, analise os seguintes passos.

I. **Caso Base:** Para $n=1$, o lado esquerdo da equação é 1, e o lado direito é $1^2 = 1$. Como $1=1$, a propriedade $P(1)$ é verdadeira.

II. **Hipótese de Indução:** Assumimos que a propriedade é verdadeira para um inteiro arbitrário $k \ge 1$. Ou seja, assumimos que $P(k): 1 + 3 + 5 + ... + (2k-1) = k^2$.

III. **Passo Indutivo:** Queremos provar $P(k+1)$, ou seja, que $1 + 3 + 5 + ... + (2k-1) + (2(k+1)-1) = (k+1)^2$. Começando pelo lado esquerdo, usamos a Hipótese de Indução para substituir a soma até $(2k-1)$ por $k^2$. A expressão se torna $k^2 + (2(k+1)-1) = k^2 + 2k + 2 - 1 = k^2 + 2k + 1$. Fatorando essa expressão, obtemos $(k+1)^2$, que é exatamente o lado direito de $P(k+1)$.

É correto o que se afirma em: