Grande prova de teta na função polinomial

Isso não é lição de casa. Eu tenho a solução, mas não é o que estou recebendo. Sei que existem várias soluções para o problema, mas quero ter certeza de que não estou perdendo nada.

A questão é a seguinte:

Prove que 2 - 4n + 7 = Θ ( ). forneça os valores das constantes e mostre seu trabalho.$n^2$$n^2$

Aqui está como eu abordei o problema:

A partir da definição de Θ (g (n)):

0 ≤ C ₁ ≤ 2 - 4n + 7 ≤ C ₂$n^2$$n^2$$n^2$

Divida a desigualdade pela maior ordem n-termo. (Esta é a única maneira que sei resolver essas equações.)

0 ≤ C ₁ ≤ 2 - (4 / n - 7 / ) ≤ C ₂$n^2$

Divida o problema em duas partes: LHS e RHS.

Começamos com o RHS:

Encontre C ₂ constante que satisfará

0 ≤ 2 - (4 / n - 7 / ) ≤ C ₂$n^2$

n = 1, (2 - (4/1 - 7/1 )) = 5$1^2$

n = 2, (2 - (4/2 - 7/2 )) = 7/4$2^2$

n = 3, (2 - (4/3 - 7/9)) = 13/9

Escolhemos C ₂ como 2, n≥2 para satisfazer o RHS.

LHS: tentamos encontrar uma constante que satisfaça

0 ≤ C ₁ ≤ 2 - (4 / n - 7 / )$n^2$

Acima, sabemos que depois de n = 2, a equação se aproxima de 2 à medida que n cresce, portanto, se escolhermos uma constante menor que 2, ela deverá satisfazer o LHS.

Nós escolhemos C ₁ para ser 1. Para n, escolhendo 1 iria satisfazer o lado esquerdo, mas desde que o RHS precisa n≥2, nós ficar com ela.

Portanto, as constantes que provam 2 - 4n + 7 = Θ ( ) são$n^2$$n^2$

C ₁ = 1, C ₂ = 2, n≥2

A solução fornecida para esse problema escolhe n≥4, mas não sei por que. Parece que n≥2 funcionaria bem. Estou errado em algum lugar?

Se eu não estiver errado, se eu tivesse escolhido C ₁ como também 2, isso também não satisfaria o lado esquerdo, uma vez que a desigualdade permite que seja ≤?

Sua solução está boa. Existem várias maneiras de provar esse fato, todas válidas / corretas. Portanto, sua abordagem é válida e é possível que a solução da sua classe também seja válida: isso não é uma contradição.

Deixe-me dar um conselho para estruturar sua prova no futuro, no entanto. No argumento que você esboçou na pergunta, você está "trabalhando de trás para frente": parte da afirmação que deseja que fosse verdadeira (que ) e então você tenta derivar o que precisa ser verdadeiro sobre para que seu desejo seja verdadeiro. A experiência provou que esse tipo de raciocínio é propenso a erros: é fácil para você cometer um erro ao longo do caminho. Também é difícil para outros verificarem.$c_1 n^2 \le 2 n^2 -4n + 7 \le c_2 n^2$$c_1,c_2$

Quando você escreve sua prova, sugiro que você faça o raciocínio na direção oposta. Comece pelo que você sabe que é verdade e, em seguida, deduza as implicações disso, terminando com a conclusão de que$c_1 n^2 \le 2 n^2 -4n + 7 \le c_2 n^2$. Isso combina melhor com o modo como as pessoas pensam e facilita para o leitor entender o que está acontecendo. E o objetivo de uma prova é comunicar uma idéia ao leitor; portanto, a prova deve ser estruturada para facilitar a vida do leitor: para tornar o mais fácil possível para o leitor verificar se o raciocínio da prova é correto e válido. É como um bom livro; boa escrita é escolhida para tornar a vida boa para o leitor. As provas são da mesma maneira. E, finalmente, isso também será benéfico para você: na minha experiência, se você seguir essa abordagem, é menos provável que cometa um erro sutil na sua prova.

Portanto, um esboço de prova melhor seria mostrar que vale para todo (porque tal e tal) e mostrar que vale para todo (porque blá-de-blá) e, em seguida, conclua que . Sei que esse tipo de prova é mais difícil de escrever, porque você precisa saber o valor de a ser usado antes de começar a escrever esse estilo de prova. Mas você sabe o que? Isso está ok. Você pode fazer um cálculo lateral, em papel de rascunho, para descobrir qual valor de usar. Não nos mostre esse cálculo lateral; basta descobrir qual o valor de$n^2 \le 2n^2 - 4n + 7$$n\ge 2$$2n^2 - 4n + 7 \le 2n^2$$n\ge 2$$2n^2 - 4n + 7 \in \Theta(n^2)$$c_1,c_2$$c_1,c_2$$c_1,c_2$seria bom fazer e, em seguida, iniciar a prova com você puxando magicamente do nada, e demonstrar que sua escolha é válida. Esse estilo de prova será melhor para você e melhor para o leitor.$c_1=1,c_2=2$