Indução Forte

A indução forte é uma variação da indução matemática clássica, que pode ser chamada de indução fraca. Geralmente, a indução forte é utilizada quando não podemos demonstrar facilmente utilizando a indução fraca. Essencialmente,  elas diferem no passo de indução. Em uma demonstração de indução fraca, no passo indutivo temos que mostrar que toda vez que P(n-1) é verdadeira, P(n) também será verdadeira. Observe que na indução fraca, utilizamos apenas uma instância da hipótese de indução. Em uma demonstração de indução forte, no passo indutivo temos que mostrar que toda vez que P(k) é verdadeiro para todo k <= n-1 então P(n) também será verdadeiro. Observe na indução forte, podemos aplicar várias instâncias da hipótese de indução e/ou não restringe a aplicação da hipótese de indução em uma única instância da hipótese indutiva.

Vamos observar essas mudanças em uma demonstração.

Exemplo:
Mostre que P(n) é valida para n >= 8
P(n) = é possível obter qualquer valor n centavos ou mais usando  apenas moedas de 3 ou 5 centavos 

Caso Base

P(8),P(9),P(10) é verdadeiro

8 = 3+5

9 = 3+3+3

10 = 5+5

Hipótese de Indução

P(k) é verdadeira para todo 8<=k<=n-1em que n-1>=10.

Passo de Indução

Vamos mostrar que P(n) é verdadeiro para n>=11.

Por hipótese de indução, temos que P(n-3) é verdadeiro, por que n-3>=8. Logo,

n-3 = 3a+5b , a  N e b  N  

Assim, temos

n-3+3 = 3(a+1)+5b

n = 3(a+1)+5b

Para obter n centavos usando moedas de 3 ou 5, basta saber como obter n-3 centavos usando moedas de 3 ou 5 e adicionar uma moeda de 3.

#include <stdio.h>
int main(){
 int n;
 while(1){   
 printf("Entre com um valor maior que 8:");
 scanf("%d",&n);
 if(n<8) break;
 int i;
 int a[n+1]; //quantidade de 3's
 int b[n+1]; //quantidade de 5's
 a[8] = 1;
 b[8] = 1;
 a[9] = 3;
 b[9] = 0;
 a[10] = 0;
 b[10] = 2;
 for(i=11;i<=n;i++){
    a[i] = a[i-3]+1;
    b[i] = b[i-3];
 }
 printf("%d=3*%d + 5*%d\n",n,a[n],b[n]);
 }
 return 0;
}

Saída

Entre com um valor maior que 8:8
8=3*1 + 5*1
Entre com um valor maior que 8:9
9=3*3 + 5*0
Entre com um valor maior que 8:10
10=3*0 + 5*2
Entre com um valor maior que 8:11
11=3*2 + 5*1
Entre com um valor maior que 8:12
12=3*4 + 5*0
Entre com um valor maior que 8:13
13=3*1 + 5*2
Entre com um valor maior que 8:14
14=3*3 + 5*1
Entre com um valor maior que 8:15
15=3*5 + 5*0
Entre com um valor maior que 8:16
16=3*2 + 5*2
Entre com um valor maior que 8:17
17=3*4 + 5*1
Entre com um valor maior que 8:18
18=3*6 + 5*0