Prove por indução matemática a seguinte proposição:
(a) p(n): 1 + 3 + 6 + ... + n(n+1)/2 = n(n+1)(n+2)/6
Alguém poderia ser didático? Não quero só a resposta, tenho interesse em entender como é feito.
DanJR:
Em qual parte, Guto, tens mais dúvidas?
Olá Dan, eu sou programador e cai de paraquedas nesse tema, indução matemática é utilizada por vários algoritmos para várias finalidades. Eu sei os conceitos e resolver proposições mais simples. Porém esse é um exemplo do livro e mesmo resolvido eu não consegui entende-lo. Se fosse possível eu gostaria da resolução junto de um breve explicação do porque cada coisa ocorre. Ficaria grato.
Soluções para a tarefa
Respondido por
3
Olá!
Façamos uma indução em n.
PASSO BASE: a fórmula é verdadeira para
Verifiquemos:
PASSO INDUTIVO: se a fórmula é verdadeira para
, então é verdadeira para 
; segundo o Princípio da Indução Finita.
- Hipótese de indução:
- Devemos mostrar que:
![\\ \displaystyle \mathsf{1 + 3 + 6 + ... + \frac{k(k + 1)}{2} + \frac{(k + 1)(k + 2)}{2} = \frac{(k + 1)[(k + 1) + 1][(k + 1) + 2]}{6}} \\\\\\ \mathsf{1 + 3 + 6 + ... + \frac{k(k + 1)}{2} + \frac{(k + 1)(k + 2)}{2} = \frac{(k + 1)(k + 2)(k + 3)}{6}}](https://tex.z-dn.net/?f=%5C%5C+%5Cdisplaystyle+%5Cmathsf%7B1+%2B+3+%2B+6+%2B+...+%2B+%5Cfrac%7Bk%28k+%2B+1%29%7D%7B2%7D+%2B+%5Cfrac%7B%28k+%2B+1%29%28k+%2B+2%29%7D%7B2%7D+%3D+%5Cfrac%7B%28k+%2B+1%29%5B%28k+%2B+1%29+%2B+1%5D%5B%28k+%2B+1%29+%2B+2%5D%7D%7B6%7D%7D+%5C%5C%5C%5C%5C%5C+%5Cmathsf%7B1+%2B+3+%2B+6+%2B+...+%2B+%5Cfrac%7Bk%28k+%2B+1%29%7D%7B2%7D+%2B+%5Cfrac%7B%28k+%2B+1%29%28k+%2B+2%29%7D%7B2%7D+%3D+%5Cfrac%7B%28k+%2B+1%29%28k+%2B+2%29%28k+%2B+3%29%7D%7B6%7D%7D "\\ \displaystyle \mathsf{1 + 3 + 6 + ... + \frac{k(k + 1)}{2} + \frac{(k + 1)(k + 2)}{2} = \frac{(k + 1)[(k + 1) + 1][(k + 1) + 2]}{6}} \\\\\\ \mathsf{1 + 3 + 6 + ... + \frac{k(k + 1)}{2} + \frac{(k + 1)(k + 2)}{2} = \frac{(k + 1)(k + 2)(k + 3)}{6}}")
Segue,
![\\ \displaystyle \underbrace{\mathsf{1 + 3 + 6 + ... + \frac{k(k + 1)}{2}}}_{\mathsf{hip\acute{o}tese \ indutiva}} + \mathsf{\frac{(k + 1)(k + 2)}{2} =} \\\\\\ \mathsf{\frac{k(k + 1)(k + 2)}{6} + \frac{(k + 1)(k + 2)}{2} =} \\\\\\ \mathsf{\frac{k(k + 1)(k + 2) + 3(k + 1)(k + 2)}{6} =} \\\\\\ \mathsf{\frac{(k + 1)(k + 2) \cdot \left [ k + 3 \right ]}{6} =} \\\\\\ \mathsf{\frac{(k + 1)(k + 2)(k + 3)}{6}} \\\\\\ \blacksquare](https://tex.z-dn.net/?f=%5C%5C+%5Cdisplaystyle+%5Cunderbrace%7B%5Cmathsf%7B1+%2B+3+%2B+6+%2B+...+%2B+%5Cfrac%7Bk%28k+%2B+1%29%7D%7B2%7D%7D%7D_%7B%5Cmathsf%7Bhip%5Cacute%7Bo%7Dtese+%5C+indutiva%7D%7D+%2B+%5Cmathsf%7B%5Cfrac%7B%28k+%2B+1%29%28k+%2B+2%29%7D%7B2%7D+%3D%7D+%5C%5C%5C%5C%5C%5C+%5Cmathsf%7B%5Cfrac%7Bk%28k+%2B+1%29%28k+%2B+2%29%7D%7B6%7D+%2B+%5Cfrac%7B%28k+%2B+1%29%28k+%2B+2%29%7D%7B2%7D+%3D%7D+%5C%5C%5C%5C%5C%5C+%5Cmathsf%7B%5Cfrac%7Bk%28k+%2B+1%29%28k+%2B+2%29+%2B+3%28k+%2B+1%29%28k+%2B+2%29%7D%7B6%7D+%3D%7D+%5C%5C%5C%5C%5C%5C+%5Cmathsf%7B%5Cfrac%7B%28k+%2B+1%29%28k+%2B+2%29+%5Ccdot+%5Cleft+%5B+k+%2B+3+%5Cright+%5D%7D%7B6%7D+%3D%7D+%5C%5C%5C%5C%5C%5C+%5Cmathsf%7B%5Cfrac%7B%28k+%2B+1%29%28k+%2B+2%29%28k+%2B+3%29%7D%7B6%7D%7D+%5C%5C%5C%5C%5C%5C+%5Cblacksquare "\\ \displaystyle \underbrace{\mathsf{1 + 3 + 6 + ... + \frac{k(k + 1)}{2}}}_{\mathsf{hip\acute{o}tese \ indutiva}} + \mathsf{\frac{(k + 1)(k + 2)}{2} =} \\\\\\ \mathsf{\frac{k(k + 1)(k + 2)}{6} + \frac{(k + 1)(k + 2)}{2} =} \\\\\\ \mathsf{\frac{k(k + 1)(k + 2) + 3(k + 1)(k + 2)}{6} =} \\\\\\ \mathsf{\frac{(k + 1)(k + 2) \cdot \left [ k + 3 \right ]}{6} =} \\\\\\ \mathsf{\frac{(k + 1)(k + 2)(k + 3)}{6}} \\\\\\ \blacksquare")
Que é o que queríamos demonstrar!
Guto, a ideia da indução é a seguinte: você tem uma fórmula e deve verificar se ele é verdadeira para um elemento mínimo (geralmente, é o UM), por conseguinte, você deve verificar se a fórmula é verdadeira para o segundo menor elemento, depois pelo terceiro menor e assim sucessivamente. Num determinado momento, depois de cansar de testar diversos valores acabamos acreditando que a fórmula é verdadeira para todos os números, mas verificações sucessivas não são consideradas como prova...
Assim, fazemos uso do PIF que é uma generalização; nele você considera (por hipótese) que a fórmula é verdadeira para um determinado número (k) e também é verdadeira (tese) para o número seguinte (k + 1). Foi isso que fiz acima!
Espero ter sido claro, caso contrário, comente qualquer dúvida!
Att,
Daniel.
Façamos uma indução em n.
PASSO BASE: a fórmula é verdadeira para
Verifiquemos:
PASSO INDUTIVO: se a fórmula é verdadeira para
- Hipótese de indução:
- Devemos mostrar que:
Segue,
Que é o que queríamos demonstrar!
Guto, a ideia da indução é a seguinte: você tem uma fórmula e deve verificar se ele é verdadeira para um elemento mínimo (geralmente, é o UM), por conseguinte, você deve verificar se a fórmula é verdadeira para o segundo menor elemento, depois pelo terceiro menor e assim sucessivamente. Num determinado momento, depois de cansar de testar diversos valores acabamos acreditando que a fórmula é verdadeira para todos os números, mas verificações sucessivas não são consideradas como prova...
Assim, fazemos uso do PIF que é uma generalização; nele você considera (por hipótese) que a fórmula é verdadeira para um determinado número (k) e também é verdadeira (tese) para o número seguinte (k + 1). Foi isso que fiz acima!
Espero ter sido claro, caso contrário, comente qualquer dúvida!
Att,
Daniel.
Cara, você simplesmente tirou TODAS minhas dúvidas relacionadas ao exercício. Espero que você seja abençoado da melhor forma possível e que continue compartilhando esse seu conhecimento f0d4st1c0. Grande abraço!
Que bom, e, obrigado.
Perguntas interessantes