61
edits
Changes
m
→Extra
==Extra==
Nesta sessão serão tratados algumas demonstrações sobre indução e recursão contidas na pagina 240, cujo Extra 1, 2, 3 e 4 são implentações na linguagem de C++ como forma de uma abordagem alternativa como sugestão do Professor Umberto Rivieccio da disciplina de FMC II.
*Exemplo 1
Use o princípio da indução matemática para provar que <math>1 + 5 + 5^2 +5^3 +...+5n = 5n+1 -1/4 </math> para todo <math> n /ge 0</math>
Seja P(n) a afirmação <math>1+5^2+5^3+...+5n = 5n+1 -1/div 4</math>
'''Passo base:''' P(0) <math>1= 50+1 -1/div 4</math>, (perceba que a soma no lado esquerdo de p(0) inicia e termina com o primeiro termo 1, consequentemente é apenas o primeiro termo 1). P(0) é verdadeiro pois ambos os lados são iguais a 1.
'''Passo indutivo:''' <math>P(k)/cdotP(k+1)</math>: suponha para qualquer k, P(k) é verdadeiro; isto é,
<math>1+5+5^2+5^3+...+ 5k = 5/cdotk+1 -1/div 4</math>
Precisamos mostrar que a próxima afirmação P(k+1), é verdadeira:
<math>1+5+5^2 +5^3 +...+5/cdotk+1 = 5/cdotk+2 -1/div 4</math>
Para fazer isso, iniciamos com p(k) e adicionamos o próximo termo, <math>5/cdotk+1</math>, em ambos os lados, depois mostramos que essa é a afirmação p(k+1).
<math>1+5^2+5^3+...+5k = 5/cdotk+1 -1/div 4</math>
---------------<math>+5/cdotk+1 = 5/cdotk+1 </math>--------
<math>1+5^2+5^3+...+5k+5k+1 = 5k+1 -1 +4.5k+1 /div 4</math>
<math>= (1+4)5k+1 -1 /div 4</math>
<math>= 5/cdot 5k+1 -1/div4</math>
<math>= 5k+2 -1 /div 4</math>
Isto é, <math>p(k+1)</math>. Portanto uma afirmação verdadeira p(k, é seguida por outra afirmação verdadeira <math>p(k+1)</math>, por isso <math>p(k)/cdotp(k+1)</math> é verdadeira. Assim, pelo princípio da indução matemática , p(n) é verdadeiro para todo <math>n/ge 0</math>.
Nota: alternativamente, a prova de <math>p(k)/cdot p(k+1)</math> pode ser escrita dessa forma. Começamos escrevendo o lado esquerdo da equação que é <math>p(k+1)</math>. Então mostramos que pode ser reescrita para dar o lado direito de <math>p(k+1)</math>. Perceba que a suposição que p(k) é verdadeira está sendo usada em substituição do primeiro passo.
<math>+5+5^2+5^3 + ...+ 5k +5/cdotk+1 = 5/cdotk+1 -1 /div 4 + 5/cdotk+1</math>
<math> = 5k+1 -1 + 4/cdot5k+1</math>
<math>= (1+4) 5k+1 -1/div 4</math>
<math>=5/cdot 5k+1-1/div 4</math>
<math>=5k+2-1/div 4</math>
*Exemplo 2
Prove que :
<math>/sum limits_{k=1}^n (2k+3)$= n(n+4) para todo n/ge1</math>
Seja <math>p(n)= 5+7+9+...+(2n+3)= n/cdot(n+4)</math>
'''Passo base:''' p(1) afirma que <math>2/cdot 1+3=1(1+4)</math>, é verdadeiro, já que ambos os lados são iguais a 5.
'''Passo indutivo:''' <math>p(k)/cdotp(k+1)</math>: suponha que p(k) é verdadeiro, isto é: <math>5+7+9+...+(2k+3 )=k(k+4)</math>
Adicionamos (2k+3) a ambos os lados e simplificamos :
<math>5+7+9+...+(2k+3)+(2k+5) = k/cdot(k+4)+(2k+5)</math>
<math>= k^2 + 6k + 5</math>
<math>= (k+1)/cdot(k+5)</math>
==Conclusão==